按自然数从小到大为标准次序,求下列各排列的逆序数.(1) 2134;(2) 4132;(3) 3421;(4) 4213;(5) 13...(2n-1)24...(2n);(6) (13...(2n-1)(2n)(2n-2)...2).
按自然数从小到大为标准次序,求下列各排列的逆序数. (1) 2134; (2) 4132; (3) 3421; (4) 4213; (5) $13\cdots(2n-1)24\cdots(2n)$; (6) $(13\cdots(2n-1)(2n)(2n-2)\cdots2)$.
题目解答
答案
我们来逐题分析并计算每个排列的逆序数。
定义回顾:
在一个排列中,若前面的数比后面的数大,则这对数构成一个逆序。
逆序数就是这个排列中所有逆序对的个数。
(1)排列:2134
我们逐个数检查其后面比它小的数的个数:
- 2 后面有 1,构成一个逆序;
- 1 后面没有比它小的数;
- 3 后面没有比它小的数;
- 4 后面没有数。
逆序数:1
(2)排列:4132
逐个检查:
- 4 后面有 1、3、2,都比 4 小,构成 3 个逆序;
- 1 后面没有比它小的数;
- 3 后面有 2,构成 1 个逆序;
- 2 后面没有数。
逆序数:3 + 1 = 4
(3)排列:3421
逐个检查:
- 3 后面有 2、1,构成 2 个逆序;
- 4 后面有 2、1,构成 2 个逆序;
- 2 后面有 1,构成 1 个逆序;
- 1 后面没有数。
逆序数:2 + 2 + 1 = 5
(4)排列:4213
逐个检查:
- 4 后面有 2、1、3,都比 4 小,构成 3 个逆序;
- 2 后面有 1,构成 1 个逆序;
- 1 后面没有比它小的数;
- 3 后面没有数。
逆序数:3 + 1 = 4
(5)排列:$1\ 3\ \cdots\ (2n-1)\ 2\ 4\ \cdots\ 2n$
这是一个奇数在前、偶数在后的排列,例如当 $n = 3$ 时,排列为:1 3 5 2 4 6
我们来分析一般情况:
- 前 $n$ 个数是奇数:1, 3, 5, ..., $2n-1$
- 后 $n$ 个数是偶数:2, 4, 6, ..., $2n$
现在我们来计算奇数后面比它小的偶数的个数:
对于每个奇数 $2k-1$,它后面有 $n - k$ 个偶数比它小(因为偶数从小到大排列,比 $2k-1$ 小的偶数是 $2, 4, ..., 2(k-1)$,共 $k-1$ 个,所以比它大的偶数是 $n - (k-1) = n - k + 1$)
不过更简单的方法是:
每个奇数后面有 $n$ 个偶数,其中比它小的偶数有 $k-1$ 个,所以比它大的偶数是 $n - (k-1) = n - k + 1$
所以总逆序数是:
$\sum_{k=1}^{n} (n - k + 1) = \sum_{i=1}^{n} i = \frac{n(n+1)}{2}$
逆序数:$\boxed{\frac{n(n+1)}{2}}$
(6)排列:$(1\ 3\ \cdots\ (2n-1)\ (2n)\ (2n-2)\ \cdots\ 2)$
这个排列是:
- 前 $n$ 个数是奇数:1, 3, 5, ..., $2n-1$
- 后 $n$ 个数是偶数,但按从大到小排列:$2n, 2n-2, ..., 2$
我们来分析逆序数:
- 奇数部分:1, 3, 5, ..., $2n-1$,这部分是升序,没有逆序;
- 偶数部分:$2n, 2n-2, ..., 2$,这部分是降序,每一对都构成逆序,共有 $\frac{n(n-1)}{2}$ 个;
- 奇数与偶数之间:每个奇数 $2k-1$ 后面有 $n$ 个偶数,其中比它大的偶数有 $n - k$ 个(因为偶数从大到小排列,前 $k$ 个偶数小于等于 $2k-1$)
所以奇偶之间的逆序数是:
$\sum_{k=1}^{n} (n - k) = \sum_{i=0}^{n-1} i = \frac{(n-1)n}{2}$
偶数内部逆序数是:$\frac{n(n-1)}{2}$
所以总逆序数是:
$\frac{(n-1)n}{2} + \frac{n(n-1)}{2} = n(n-1)$
逆序数:$\boxed{n(n-1)}$
总结答案:
题号 | 排列 | 逆序数 |
---|---|---|
(1) | 2134 | 1 |
(2) | 4132 | 4 |
(3) | 3421 | 5 |
(4) | 4213 | 4 |
(5) | $1\ 3\ \cdots\ (2n-1)\ 2\ 4\ \cdots\ 2n$ | $\boxed{\frac{n(n+1)}{2}}$ |
(6) | $1\ 3\ \cdots\ (2n-1)\ 2n\ (2n-2)\ \cdots\ 2$ | $\boxed{n(n-1)}$ |
如有需要,我也可以画出逆序对的详细分析图。