题目

(2)求排列246...(2n)135...(2n-1)的逆序数.

(2)求排列$246\cdots(2n)135\cdots(2n-1)$的逆序数.

题目解答

答案

排列 $246\cdots(2n)135\cdots(2n-1)$ 中，偶数部分为 $2, 4, 6, \ldots, 2n$，奇数部分为 $1, 3, 5, \ldots, 2n-1$。每个偶数 $2k$（$k=1,2,\ldots,n$）在奇数部分有 $k$ 个小于它的数（即 $1, 3, 5, \ldots, 2k-1$），贡献逆序数 $k$。所有偶数的总逆序数为： \[ 1 + 2 + \cdots + n = \frac{n(n+1)}{2} \] 奇数部分内部有序，无逆序。因此，排列的逆序数为 $\boxed{\frac{n(n+1)}{2}}$。

解析

考查要点：排列的逆序数计算，重点在于分析不同部分元素之间的逆序关系。

解题核心思路：

  1. 分解排列结构：排列分为前半部分的偶数序列和后半部分的奇数序列，两部分内部均有序，无内部逆序。
  2. 跨部分逆序分析：每个偶数在奇数序列中存在若干比它小的奇数，需计算这些逆序对的总数。
  3. 等差数列求和：将每个偶数的逆序贡献累加，转化为等差数列求和公式。

破题关键点：

  • 偶数与奇数的比较：明确每个偶数 $2k$ 对应奇数序列中有 $k$ 个比它小的奇数。
  • 总逆序数的累加：通过等差数列求和公式快速计算总逆序数。

排列 $246\cdots(2n)135\cdots(2n-1)$ 的结构如下：

  • 前 $n$ 个元素：偶数序列 $2, 4, 6, \ldots, 2n$，内部有序，无逆序。
  • 后 $n$ 个元素：奇数序列 $1, 3, 5, \ldots, 2n-1$，内部有序，无逆序。

逆序数仅存在于偶数与奇数之间。具体分析如下：

  1. 偶数 $2k$ 的逆序贡献：

    • 偶数 $2k$ 在奇数序列中，比它小的奇数有 $1, 3, 5, \ldots, 2k-1$，共 $k$ 个。
    • 因此，$2k$ 贡献 $k$ 个逆序数。

  2. 总逆序数计算：

    • 所有偶数的逆序贡献之和为 $1 + 2 + 3 + \cdots + n$。
    • 利用等差数列求和公式：
      $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$