题目

求下列各排列的逆序数(1) 654123;(2) 13...(2n-1)24...(2n).

求下列各排列的逆序数

(1) 654123;

(2) $13\cdots(2n-1)24\cdots(2n)$.

题目解答

(1) 对于排列 $654123$，计算逆序数：

(2) 对于排列 $1, 3, \cdots, (2n-1), 2, 4, \cdots, (2n)$，计算逆序数：

奇数与偶数之间形成逆序，每个奇数 $2k-1$（$k=1,2,\cdots,n$）与偶数 $2, 4, \cdots, (2k-2)$ 形成 $k-1$ 个逆序
总逆序数：$\sum_{k=1}^{n} (k-1) = \frac{(n-1)n}{2}$
答案： $\boxed{\frac{n(n-1)}{2}}$

本题考查排列逆序数的计算。解题思路是根据逆序数的定义，即一个排列中所有逆序的总数，通过依次分析排列中每个数后面比它小的数的个数，将这些个数相加，即可得到该排列的逆序数。

（1）计算排列 $654123$ 的逆序数

（2）计算排列 $13\cdots(2n - 1)24\cdots(2n)$ 的逆序数

先分析奇数部分 $1,3,\cdots,(2n - 1)$ 与偶数部分 $2,4,\cdots,(2n)$ 之间的逆序情况。
- 对于奇数 $1$，它后面比 $1$ 小的偶数个数为 $0$ 个。
- 对于奇数 $3$，它后面比 $3$ 小的偶数有 $2$，共 $1$ 个。
- 对于奇数 $5$，它后面比 $5$ 小的偶数有 $2$、$4$，共 $2$ 个。
- 一般地，对于奇数 $2k - 1$（$k = 1,2,\cdots,n$），它后面比 $2k - 1$ 小的偶数有 $2,4,\cdots,(2k - 2)$，共 $k - 1$ 个。
所以该排列的逆序数 $N$ 为所有奇数产生的逆序数之和，即 $N=\sum_{k = 1}^{n}(k - 1)$。
根据等差数列求和公式 $S_n=\frac{n(a_1 + a_n)}{2}$（其中 $n$ 为项数，$a_1$ 为首项，$a_n$ 为末项），对于数列 $0,1,2,\cdots,n - 1$，$n$ 项，$a_1 = 0$，$a_n=n - 1$，则 $N=\frac{n(0+(n - 1))}{2}=\frac{n(n - 1)}{2}$。