题目

求下列各排列的逆序数：(1) 135...(2n-1)246...(2n);(2) 13...(2n-1)(2n)(2n-2)...42;(3) 已知排列 x_1x_2... x_(n-1)x_n 的逆序数是 k，求排列 x_nx_(n-1)... x_2x_1 的逆序数.

求下列各排列的逆序数： (1) $135\cdots(2n-1)246\cdots(2n)$; (2) $13\cdots(2n-1)(2n)(2n-2)\cdots42$; (3) 已知排列 $x_1x_2\cdots x_{n-1}x_n$ 的逆序数是 $k$，求排列 $x_nx_{n-1}\cdots x_2x_1$ 的逆序数.

题目解答

答案

(1) 排列 $1, 3, 5, \ldots, (2n-1), 2, 4, 6, \ldots, (2n)$ 中，奇数与偶数之间的逆序数为 $\sum_{k=1}^{n} (k-1) = \frac{n(n-1)}{2}$，偶数间无逆序。
答案： $\boxed{\frac{n(n-1)}{2}}$

(2) 排列 $1, 3, \ldots, (2n-1), (2n), (2n-2), \ldots, 4, 2$ 中，奇数与偶数之间的逆序数为 $\frac{n(n-1)}{2}$，偶数间逆序数为 $\frac{n(n-1)}{2}$。
答案： $\boxed{n(n-1)}$

(3) 原排列逆序数为 $k$，共 $\binom{n}{2} = \frac{n(n-1)}{2}$ 个数对，新排列逆序数为 $\frac{n(n-1)}{2} - k$。
答案： $\boxed{\frac{n(n-1)}{2} - k}$

解析

逆序数是排列中较大数出现在较小数前面的次数总和。本题三个小题分别考查不同排列结构的逆序数计算方法：

  1. 奇数与偶数分段排列：奇数部分和偶数部分内部有序，逆序仅存在于奇数与偶数之间。
  2. 奇数升序+偶数降序排列：奇数部分内部无逆序，偶数部分降序导致内部逆序，奇数与偶数之间也存在逆序。
  3. 原排列与逆排列的关系：利用总排列数对数与原排列逆序数的关系直接推导。

第（1）题

排列结构为奇数升序后接偶数升序：

  • 奇数部分内部：无逆序。
  • 偶数部分内部：无逆序。
  • 奇数与偶数之间：每个奇数 $2k-1$ 后面有 $k-1$ 个比它小的偶数，总逆序数为 $\sum_{k=1}^{n} (k-1) = \frac{n(n-1)}{2}$。

第（2）题

排列结构为奇数升序后接偶数降序：

  • 奇数部分内部：无逆序。
  • 偶数部分内部：降序排列，逆序数为 $\sum_{k=1}^{n-1} k = \frac{n(n-1)}{2}$。
  • 奇数与偶数之间：每个奇数 $2k-1$ 后面有 $n-k$ 个比它小的偶数，总逆序数为 $\sum_{k=1}^{n} (n-k) = \frac{n(n-1)}{2}$。
  • 总逆序数：$\frac{n(n-1)}{2} + \frac{n(n-1)}{2} = n(n-1)$。

第（3）题

原排列逆序数为 $k$，总排列数对数为 $\binom{n}{2} = \frac{n(n-1)}{2}$：

  • 逆排列的逆序数：原排列的正序数对变为逆序数对，即 $\frac{n(n-1)}{2} - k$。