定理 2.2 对换的传递性

定理 2.2.

自然排列 $12\cdots n$ 可以与任意 $n$ 阶排列 $i_1{i}_2\cdots i_n$ 经过一系列对换相互转换,且所作对换的个数与排列 $i_1{i}_2\cdots i_n$ 具有相同的奇偶性.

\begin{proof} 先来看由自然排列 $12\cdots n$ 到任意 $n$ 阶排列的转换. 对 $n$ 用数学归纳法. 当 $n=1$ 时,一阶排列只有自然排列,命题成立. $n=2$ 时,二阶排列有两个,即自然排列 12 和排列 21,命题显然成立. 假设对 $n-1$ 的情形命题成立, 即 $n-1$ 阶自然排列 $12\cdots \left(n-1\right)$ 可经一系列对换变为任意的 $n-1$ 阶排列. 设 $i_1{i}_2\cdots i_n$ 是任一 $n$ 阶排列,若 $i_n=n$ ,则 $i_1{i}_2\cdots i_{n-1}$ 是一个 $n-1$ 阶排列,结论由归纳法得到; 若 $i_n=j\ne n$ ,作对换 $\left(j,n\right)$, 归结到 $i_n=n$ 的情形,结论成立. \end{proof}

由于对换可逆, 任一 $n$ 阶排列可经 (同样的) 一系列对换变为 $n$ 阶自然排列. 因为自然排列 $12\cdots n$ 是偶排列, 由 推论 2.1 知, 两者相互转换所作的对换的个数与排列 $i_1{i}_2\cdots i_n$ 具有相同的奇偶性.