题目

2.按自然数从小到大为标准次序，求下列排列的逆序数：(1)1234; (2)4132;(3)3421; (4)2413;(5)13 ... (2n-1)... (2n);(6)13 ... (2n-1)(2n)(2n-2)... 2.

2.按自然数从小到大为标准次序，求下列排列的逆序数： (1)1234; (2)4132; (3)3421; (4)2413; (5)13$ \cdots$ (2n-1)$\cdots$ (2n); (6)13$ \cdots$ (2n-1)(2n)(2n-2)$\cdots$ 2.

题目解答

答案

(1) 1234：无逆序，逆序数为 $0$。 (2) 4132：逆序数为 $4$（41, 43, 42, 32）。 (3) 3421：逆序数为 $5$（32, 31, 42, 41, 21）。 (4) 2413：逆序数为 $3$（21, 41, 43）。 (5) 13... (2n-1)24... (2n)：逆序数为 $\frac{(n-1)n}{2}$。 (6) 13... (2n-1)(2n)(2n-2)... 2：逆序数为 $n(n-1)$。 \[ \boxed{ \begin{array}{cccccc} \text{(1) } 0, & \text{(2) } 4, & \text{(3) } 5, & \text{(4) } 3, & \text{(5) } \frac{n(n-1)}{2}, & \text{(6) } n(n-1) \end{array} } \]

解析

逆序数是排列中所有逆序对的总数，即一个较大的数排在较小数前面的情况。解题核心是逐个元素向后遍历，统计每个元素右侧比它小的元素个数。对于复杂排列，需注意分段分析，如奇数段与偶数段的逆序贡献。

(1) 1234

排列本身是自然顺序，无逆序对，逆序数为 $0$。

(2) 4132

4 后有 1、3、2（3个逆序）
1 后无逆序
3 后有 2（1个逆序）
2 后无逆序
总逆序数：$3 + 0 + 1 = 4$。

(3) 3421

3 后有 2、1（2个逆序）
4 后有 2、1（2个逆序）
2 后有 1（1个逆序）
1 后无逆序
总逆序数：$2 + 2 + 1 = 5$。

(4) 2413

2 后有 1（1个逆序）
4 后有 1、3（2个逆序）
1 后无逆序
3 后无逆序
总逆序数：$1 + 2 = 3$。

(5) 13... (2n-1)24... (2n)

奇数段：每个奇数 $2k-1$ 后有 $k-1$ 个偶数比它小，总贡献 $\sum_{k=1}^{n} (k-1) = \frac{n(n-1)}{2}$。
偶数段：内部有序，无逆序。

(6) 13... (2n-1)(2n)(2n-2)... 2

奇数段：同上，贡献 $\frac{n(n-1)}{2}$。
偶数段：递减排列，每个偶数 $2k$ 后有 $k-1$ 个数比它小，总贡献 $\sum_{k=1}^{n} (k-1) = \frac{n(n-1)}{2}$。
总逆序数：$\frac{n(n-1)}{2} + \frac{n(n-1)}{2} = n(n-1)$。