定理 2.1 对换改奇偶性

定理 2.1.

对换改变排列的奇偶性.

\begin{proof} 当 $\left(i,j\right)$ 为相邻对换时,对换前后, $i,j$ 之外数字的位置都没有改变, 因此这些数字所构成的逆序数不变, $i,j$ 和其余数字所成的逆序数也不变,故只需考虑 $i,j$ 两者之间的逆序. 如果 $i$ 和 $j$ 原来并没有逆序 (即 $i<j$ ),那么在对换后的新排列中会得到一个新的逆序, 即增加了一个逆序数; 如果原来两者就是逆序 (即 $i>j$ ),那么现在就会变成顺序,即减少了一个逆序数. 在这两种情形中排列前后的奇偶性都发生了改变.

当 $\left(i,j\right)$ 为一般对换时,设 $i,j$ 之间有 $s$ 个数字 $k_1,k_2,\cdots ,k_s$ . 不失一般性, 设原排列为 \cdots i{k}_{1}{k}_{2}\cdots {k}_{s}j\cdots , \tag{2.1} 经对换 $\left(i,j\right)$ ,得到 \cdots j{k}_{1}{k}_{2}\cdots {k}_{s}i\cdots \tag{2.2}

用下面的方法可以将 (2.2) 看作由 (2.1) 经过一系列的相邻对换而得到: 先将 (2.1) 的 $i$ 向右依次与 $k_1,k_2,\cdots ,k_s$ 作 $s$ 次相邻对换得 $\cdots k_1{k}_2\cdots k_{s}ij\cdots$ ,再将 $j$ 向左依次与 $i,k_s,k_{s-1},\cdots ,k_1$ 作 $s+1$ 次相邻对换而得 (2.2),即 (2.2) 可由 (2.1) 经 $2s+1$ 次相邻对换而得. 由第一段论述知,每一个相邻对换都要改变排列的奇偶性,而 $2s+1$ 是一个奇数,所以 (2.1) 和 (2.2) 的奇偶性相反. \end{proof}

推论 2.1.

排列经过奇数次对换其奇偶性发生改变, 经过偶数次对换其奇偶性不变.

\begin{proof} 由上面的定理知此结论显然成立. \end{proof}

推论 2.2.

当 $n\ge 2$ 时,在 $n$ 阶排列中,奇偶排列数目相等,即各有 $\frac{n!}{2}$ 个.

\begin{proof} 任取对换 $\left(i,j\right)$ ,对所有的奇排列作 $\left(i,j\right)$ 对换,由上面的定理知上述排列将全部变为偶排列, 故奇排列个数不大于偶排列个数. 同理, 对所有的偶排列施行 $\left(i,j\right)$ 对换,可以知偶排列个数不大于奇排列个数. 于是,在 $n$ 阶排列中, 奇偶排列数目相等,即各有 $\frac{n!}{2}$ 个. \end{proof}