排列

castelu

定义1　由$1$，$2$，$\cdots$，$n$组成的一个有序组称为一个$n$级排列。

　　显然$12 \cdots n$也是一个$n$级排列，这个排列具有自然顺序，就是按递增的顺序排起来的；其他的排列都或多或少地破坏自然顺序

定义2　在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序，一个排列中逆序的总数就称为这个排列的逆序数。

　　排列$j_1j_2 \cdots j_n$的逆序数记为
$$\tau(j_1j_2 \cdots j_n)。$$

定义3　逆序数为偶数的排列称为偶排列；逆序数为奇数的排列称为奇排列。

　　应该指出，我们同样可以考虑由任意$n$个不同的自然数所组成的排列，一般地也称为$n$级排列。对这样一般的$n$级排列，同样可以定义上面这些概念。
　　把一个排列中某两个数的位置互换，而其余的数不动，就得到另一个排列。这样一个变换称为一个对换。
　　关于排列的奇偶性，我们有下面的基本事实。

定理1　对换改变排列的奇偶性。

　　这就是说，经过一次对换，奇排列变成偶排列，偶排列变成奇排列。

推论　在全部$n$级排列中，奇、偶排列的个数相等，各有$\frac{n!}{2}$个。

定理2　任意一个$n$级排列与排列$12 \cdots n$都可以经过一系列对换互变，并且所作对换的个数与这个排列有相同的奇偶性。