题目
2.按自然数从小到大为标准次序，求下列各排列的逆序数：(1)1234; (2)4132;(3)3421; (4)2413;(5)13 ... (2n-1)24 ... (2n); (6)13 ... (2n-1)(2n)(2n-2) ... 2.
2.按自然数从小到大为标准次序，求下列各排列的逆序数：
(1)1234; (2)4132;
(3)3421; (4)2413;
(5)13$ \cdots$ (2n-1)24$ \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}
(1) & 0 \\
(2) & 4 \\
(3) & 5 \\
(4) & 3 \\
(5) & \frac{(n-1)n}{2} \\
(6) & n(n-1) \\
\end{array}
}
$$
解析
逆序数是排列中所有逆序对的总数，即一个较大的数排在较小数前面的情况。解题核心思路是逐个元素向后遍历，统计其右侧比它小的元素个数。对于一般情况的排列，需分块分析，如奇数部分和偶数部分的分布规律。
(1) 1234
每个元素右侧均无更小的数，逆序数为0。
(2) 4132
- 4 后有1、3、2 → 3个逆序
- 1 后无更小数 → 0
- 3 后有2 → 1个逆序
- 2 后无更小数 → 0
总逆序数：3 + 0 + 1 = 4
(3) 3421
- 3 后有2、1 → 2个逆序
- 4 后有2、1 → 2个逆序
- 2 后有1 → 1个逆序
- 1 后无更小数 → 0
总逆序数：2 + 2 + 1 = 5
(4) 2413
- 2 后有1 → 1个逆序
- 4 后有1、3 → 2个逆序
- 1 后无更小数 → 0
- 3 后无更小数 → 0
总逆序数：1 + 2 = 3
(5) 奇数部分接偶数部分
- 奇数部分内部无逆序
- 偶数部分内部无逆序
- 奇数与偶数之间：第k个奇数（2k−1）后有k−1个偶数比它小
总逆序数：
$\sum_{k=1}^{n-1} (k-1) = \frac{(n-1)n}{2}$
(6) 奇数部分接递减偶数部分
- 奇数与偶数之间：第k个奇数（2k−1）后有k−1个偶数比它小
- 偶数部分内部：完全逆序，逆序数为$\frac{n(n-1)}{2}$
总逆序数：
$\frac{(n-1)n}{2} + \frac{n(n-1)}{2} = n(n-1)$