证明一个排列中的任意两个元素对换，该排列的奇偶性发生改变

求证: 一个排列中的任意两个元素对换, 排列改变奇偶性。

证明: 设有排列 $a_1{a}_2{a}_3...a_{l-1}{a}_l{a}_{l+1}...a_{m-1}{a}_m{a}_{m+1...}{a}_n$

          交换 $a_l$ 和 $a_m$ 以后求得交换前后的排列的奇偶性

          设交换前排列的逆序数为 $\tau ={\sum }_{i=1}^n{t}_i$

          设在 $a_{l+1}...a_{m-1}$ 中有 $k$ 个元素, 交换 $a_l$ 与 $a_m$ 以后的新排列为

          $a_1{a}_2{a}_3...a_{l-1}{a}_m{a}_{l+1}...a_{m-1}{a}_l{a}_{m+1...}{a}_n$

          设在 $a_{l+1}...a_{m-1}$ 这 $k$ 个元素中有 $A$ 个元素比 $a_l$ 大, 则就有 $k-A$ 个元素比 $a_l$ 小,

          交换位置以后 ${\tau }_{a_l}={\tau }_{a_l}+A$, $k-A$ 个比 $a_l$ 小的元素的逆序数都相应的减1,

          即 $\tau =\tau +A-(k-A)\to {\tau }^{{}^{\prime }}=\tau +2A-k$

          设在 $a_{l+1}...a_{m-1}$ 这 $k$ 个元素中有 $B$ 个元素比 $a_m$ 大, 则就有 $k-B$ 个元素比 $a_m$ 小,
          交换位置以后 ${\tau }_{a_m}={\tau }_{a_m}-B$, $k-B$ 个比 $a_m$ 小的元素的逆序数都相应的加1,

          即 ${\tau }^{{}^{\prime }}=\tau -B+(k-B)\to {\tau }^{{}^{\prime \prime }}={\tau }^{{}^{\prime }}+k-2B=2(A-B)+\tau$

          若 $a_m>a_l$ 则 $t_{a_m}=t_{a_m}-1$;

          若 $a_m<a_l$ 则 $t_{a_m}=t_{a_m}+1$;

          即有新的排列式的逆序数 ${\tau }^{{}^{\prime \prime \prime }}=\tau +2(A-B)\pm 1$

          其中 $2(A-B)\pm 1$ 为奇数, 因此 ${\tau }^{{}^{\prime \prime \prime }}$ 与 $\tau$ 的奇偶性相反, 交换前后的两个排列的奇偶性发生了改变, 证毕.