题目
按自然数从小到大为标准次序,求下列排列的逆序数:(1) 1234;(2) 4132;(3) 3421;(4) 2413;(5) 13...(2n-1)24...(2n);(6) 13...(2n-1)(2n)(2n-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)\cdots2$.
题目解答
答案
(1) 排列 $1234$ 无逆序,逆序数为 $0$。
(2) 排列 $4132$ 中,逆序对有 $(4,1)$、$(4,3)$、$(4,2)$、$(3,2)$,共 $4$ 个逆序。
(3) 排列 $3421$ 中,逆序对有 $(3,2)$、$(3,1)$、$(4,2)$、$(4,1)$、$(2,1)$,共 $5$ 个逆序。
(4) 排列 $2413$ 中,逆序对有 $(2,1)$、$(4,1)$、$(4,3)$,共 $3$ 个逆序。
(5) 排列 $13\cdots(2n-1)24\cdots(2n)$ 中,奇数与偶数间逆序数为 $\frac{n(n-1)}{2}$。
(6) 排列 $13\cdots(2n-1)(2n)(2n-2)\cdots2$ 中,奇数与偶数间逆序数为 $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$
在排列 $1234$ 中,任意两个数都满足从小到大的顺序,不存在逆序对,所以逆序数为 $0$。
(2) 排列 $4132$
- 对于数 $4$,它后面比它小的数有 $1$、$3$、$2$,构成逆序对 $(4,1)$、$(4,3)$、$(4,2)$。
- 对于数 $3,它后面比它小的数有 $2$,构成逆序对 $(3,2)$。
- 统计逆序对的数量,一共有 $4$ 个逆序对,所以逆序数为 $4$。
(3) 排列 $3421$
- 对于数 $3$,它后面比它小的数有 $2$、$1$,构成逆序对 $(3,2)$、$(3,1)$。
- 对于数 $4$,它后面比它小的数有 $2$、$1,构成逆序对 $(4,2)$、$(4,1)$。
- 对于数 $2$,它后面比它小的数有 $1$,构成逆序对 $(2,1)$。
- 统计逆序对数量,一共有 $5$ 个逆序对,所以逆序数为 $5$。
(4) 排列 $2413$
- 对于数 $2$,它后面比它小的数有 $1$,构成逆序对 $(2,1)$。
- 对于数 $4$,它后面比它小的数有 $1$、$3$,构成逆序对 $(4,1)$、$(4,3)$。
- 统计逆序对数量,一共有 $3$ 个逆序对,所以逆序数为 $3$。
(5) 排列 $13\cdots(2n - 1)24\cdots(2n)$
- 考虑奇数与偶数之间的逆序对。
- 对于奇数 $3$,它后面比它小的偶数有 $2$;对于奇数 $5$,它后面比它小的偶数有 $2$、$4$;以此类推,对于奇数 $2n - 1$,后面比它小的偶数有 $2$、$4$、$\cdots$、$2n$。
- 统计逆序对数量,从 $3$ 开始,每个奇数后面比它小的偶数个数依次为 $1$、$2$、$\cdots$、$n$。
- 逆序对总数为 $\sum_{i = 1}^{n}i=\frac{n(n + 1)}{2}$。
(6) 排列 $13\cdots(2n - 1)(2n)(2n - 2)\cdots2$
- 考虑奇数与偶数之间逆序对情况。
- 对于奇数 $3$,它后面比它小的偶数有 $2$、$2n - 2$;对于奇数 $5$,后面比它小的偶数有 $2$、$4$、$n - 2$;以此类推,对于奇数 $2n - 1$,后面比它小的偶数有 $2$、$4$、$\cdots$、$2n - 2$。
- 统计逆序对数量,从 $3$ 开始,每个奇数后面比它小的偶数个数依次为 $n - 1$、$n - 2$、$\cdots$、$1$。
- 逆序对总数为 $\sum_{i = 1}^{n - 1}(n - i)=n(n - 1)$。