5._排列及其逆序数

1. 排列及其逆序数

为了解决$n$阶行列式计算的问题，需要引入一个概念：逆序数。

什么叫做顺序？按照规则排列的数叫做顺序，比如 $1,2,3,4,5$ 是从小到大排列的，他是顺序的， 再比如 $5,4,3,2,1$ 是从大到小排列的，他也是顺序的，但是 $1,2,3,5,4$ 则不是顺序的，因为 $1,2,3,5$是从小到大，而$5,4$由从大到小，此时就不是顺序了。

从概念上说，$1,2,3,4,5$和$5,4,3,2,1$都是顺序的，但是显然前者更符合我们常规的从小到大的认识，因此一般我们把从 $1,2, \cdots, n$ 称为一个顺序排列。

全排列

定义1 将 $1,2, \cdots, n$ 这 $n$ 个不同的数排成一列，称为 $n$ 阶全排列，也简称为全排列。 根据高中排列组合知识，一个全排列共有$n!$的可能性。

比如$(1,2,3)$ 这三个数共有$3!=6$ 种情况，即 $1,2,3$ $1,3,2$ $2,1,3$ $2,3,1$ $3,1,2$ $3,2,1$ 共 $3* 2* 1=6$ 种。

定义2 在一个全排列中，如果一对数的排列顺序与自然顺序相反，即排在左边的数比排在它右边的数大，那么它们就称为一个逆序，一个排列中逆序的总数就称为这个排列的逆序数.

例 求3421各排列的逆序数 解：3的逆序数 0 （因为3的前面比他大的数为零个） 4的逆序数 0 （因为4的前面比他大的数为零个） 2的逆序数 2 （因为2的前面比他大的数为4和2共两个） 1 的逆序数 3 （因为1的前面比他大的数为2，4和3共三个） 所以，总的逆序数为：$0+0+2+3=5$

排列 $i_1 i_2 \cdots i_n$ 的逆序数记为 $\tau\left(i_1 i_2 \cdots i_n\right)$.

例 求$\tau (42153)$ 解：如下图

从而 $42153$ 的逆序数为 $\tau(42153)=5$.

奇排列与偶排列

定义3 逆序数为偶数的排列，称为偶排列；逆序数为奇数的排列，称为奇排列. 例如， $\tau(213)=1$ ，所以 213 是一个奇排列；而 $\tau(312)=2$ ，所以 312 是一个偶排列。 定义4 只交换排列中某两个数的位置，其它的数保持不动而得到一个新排列的变换，称为一个对换. 若交换的是相邻位置的两个元素，则称该对换为相邻对换. 例如，经过2、1对换，排列 42153就变成了排列 41253，这个对换是相邻对换； 经过 $2 、 5$ 对换，排列 42153 就变成了排列 45123 ，这个对换不是相邻对换.

定理1 对换改变排列的奇偶性. 显然， $a, b$ 与其它数构成的逆序在排列(1-1)和排列(1-2)中是一样的，不同的只是 $a, b$ 的次序. 当 $a<b$ 时， $a b$ 原来是标准序，对换后 $b a$ 构成一个逆序， 于是排列(1-2)的逆序数是排列(1-1)的逆序数增加1； 当 $a>b$ 时， $a b$ 原来是逆序，对换后 $b a$ 是标准序， 于是排列(1-2)的逆序数是排列(1-1)的逆序数减少 1 . 所以无论增加还是减少1，相邻对换都改变了排列的奇偶性. 对于不相邻的对换，不妨假设原排列为 $\cdots a i_1 \cdots i_s b \cdots$ ， 经过 $a, b$ 对换后变为排列 $\cdots b i_1 \cdots i_s a \cdots$, 这个改变过程实际上就是通过先将 $a$ 依次与其后面相邻的元素作 $s+1$ 次相邻对换变为 $\cdots i_1 \cdots i_s b a \cdots$, 再通过将 $b$ 依次与前面相邻的元素作 $s$ 次相邻对换变而得到. 一共进行了 $2 s+1$ 次相邻对换，所以改变了排列的奇偶性.

定理2 在 $n$ 阶排列中，偶排列和奇排列各占一半，即各有 $\frac{n !}{2}$ 个. *证明 记 $P_n\left(S_n 、 T_n\right)$ 为所有 $n$ 阶 (奇、偶) 排列构成的集合，则 $P_n=S_n \cup T_n$ 并且 $S_n \cap T_n=\varnothing$ ， 于是有 $\left|S_n\right| \leq\left|T_n\right| 、\left|T_n\right| \leq\left|S_n\right|$ ， 所以 $\left|S_n\right|=\left|T_n\right|=\frac{1}{2}\left|P_n\right|=\frac{1}{2} n !$ 。