对换对排列奇偶性的影响

前置知识：

• 【定义】排列及其逆序数

---

定义1（对换）　在排列中，将任意两个元素对调，其余的元素不动，这种作出新排列的手续叫做 对换。将相邻两个元素对换叫做 相邻对换。

下面讨论对换对排列奇偶性的影响。

首先考虑相对简单的相邻对换。经过相邻对换，对换元素前后的逆序数不会改变；同时，因为排列中的元素各不相同，所以无论对换元素谁大谁小，总会令排列的逆序数 $\pm 1$，使奇偶性改变。

接着考虑一般对换。不妨设对换元素之间相隔 $m$ 个其他元素，此时将左侧元素移动到右侧元素的右边需要 $m+1$ 次相邻对换，而将右侧元素移动到原来左侧元素的位置需要 $m$ 次相邻对换。因为每次相邻对换均会改变排列奇偶性，因此一般对换经过 $2m+1$ 次相邻对换后也会改变排列奇偶性。

于是得到定理及证明如下：

定理1　一个排列中的任意两个元素对换，排列改变奇偶性。

证明：仍不妨设元素为从 $1$ 开始自然数（从小到大为标准次序）。先证明对换的情形。

设排列为 $a_1\cdots a_{n}ab{b}_1\cdots b_m$，对换 $a$ 与 $b$，变为 $a_1\cdots a_{n}ba{b}_1\cdots b_m$。显然，$a_1,\cdots ,a_n$、$b_1,\cdots ,b_m$ 这些元素的逆序数经过对换并不会改变，而 $a,b$ 两元素的逆序数改变为：当 $a<b$ 时，经过对换后 $a$ 的逆序数增加 $1$ 而 $b$ 不变；当 $a>b$ 时，经过对换后 $a$ 的逆序数不变而 $b$ 的逆序数减少 $1$。所以排列 $a_1\cdots a_{n}ab{b}_1\cdots b_m$ 与排列 $a_1\cdots a_{n}ba{b}_1\cdots b_m$ 的奇偶性不同。

再证一般对换的情形。

设排列为 $a_1\cdots a_{n}a{c}_1\cdots c_{l}b{b}_1\cdots b_m$，把它作 $m$ 次相邻对换，变成 $a_1\cdots a_{n}ab{c}_1\cdots c_l{b}_1\cdots b_m$，再作 $m+1$ 次相邻对换，变成 $a_1\cdots a_{n}b{c}_1\cdots c_{l}a{b}_1\cdots b_m$。总之，经过 $2m+1$ 次相邻对换，排列 $a_1\cdots a_{n}a{c}_1\cdots c_{l}b{b}_1\cdots b_m$ 变成排列 $a_1\cdots a_{n}ab{c}_1\cdots c_l{b}_1\cdots b_m$，所以这两个排列的奇偶性相反。

进而得到推论及证明如下：

推论　奇排列对换称标准排列的对换次数为奇数，偶排列对换成标准排列的对换次数为偶数。

证明：由定理 1 知对换的次数就是排列奇偶性的变化次数，而标准排列是偶排列（逆序数为 $0$），因此知推论成立。