1.2.2　对换

把一个排列中某两个数的位置互换，而其余的数不动，就得到另一个排列.这样一个变换称为一个对换（如果对相邻位置的两个数进行对换，称为施行了一次相邻对换）.显然，如果连续施行相同的对换，那么排列就还原为原来的排列.

例如，一次相邻对换，逆序数由11变成12，奇排列变成偶排列；

一次不相邻对换，逆序数由6变成11，偶排列变成奇排列.

结果表明，经过一次对换（相邻或不相邻），都会改变排列的奇偶性.此结果具有一般性.

定理1　每一次对换改变排列的奇偶性.

证明　（1）首先考虑一个特殊情形就是被对换的两个数是相邻的.设给定的排列为对i，j施行相邻对换变成　　…，j，i，….

比较这两个排列的逆序数.除i，j这两个数码外，其他数码的位置没有改变，因此这些数码所构成的逆序数没有改变.同时i，j这两个数码和其他数码构成的逆序数也没有改变.若给定的排列…，i，j，…中，i<j，那么经过一次相邻对换后i和j就构成一个逆序，因而后一个排列…，j，i，…的逆序数就比前一个排列…，i，j，…增多了一个.若给定的排列…，i，j，…中，i>j，那么经过一次相邻对换后，i和j就构成一个逆序，因而后一个排列…，j，i，…的逆序数就比前一个排列…，i，j，…减少了一个.无论哪一种情形，排列的奇偶性都发生改变.

（2）对于一般情形，假定i和j之间有s个数码，我们用k1，k2，…，ks来代表，这时给定的排列为

…，i，k1，k2，…，ks，j，….　　（1.2）

先让i向右移动，依次与k1，k2，…，ks交换.这样，经过s次相邻对换以后，排列（1.2）变为

…，k1，k2，…，ks，i，j，….　　（1.3）

再让j向左移动，依次与i，ks，…，k2，k1交换.经过s+1次相邻对换以后，排列（1.3）变为

…，j，k1，k2，…，ks，i，….　　（1.4）

（1.4）正是由（1.2）施行一次对换i和j数码而得到的排列.因此，对（1.2）中的数码i和j施行对换相当于连续施行2s+1次相邻对换.由第一种情形，施行一次相邻对换排列的奇偶性改变，由于2s+1是一个奇数，所以（1.2）和（1.4）的奇偶性相反.

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

定理2　n≥2时，n个数码的奇排列与偶排列的个数相等，均等于个.

证明　设n个数码的奇排列共有p个，而n个数码的偶排列共有q个，对这p个奇排列施行同一个对换（交换第i和第j个位置的数码），得到p个偶排列，有p≤q.同理，对这q个偶排列施行同一个对换（交换第i和第j个位置的数码），得到q个奇排列，有q≤p.因而有p=q.