1.2 全排列和对换

排列与逆序数

把 $n$ 个元素按照某种顺序不重不漏地排成一列，称作这 $n$ 个元素的全排列，也称 $n$ 元排列。各种各样的顺序放在一起，所有 $n$ 元排列构成的集合记为 $S_{n}$ ， $S_{n}$ 所含的元素个数即为 $n$ 元排列的个数，记为 $| S_{n} |$ 。

也就是说 $| S_{n} | = A_{n}^{n} = n!$

在某个 $n$ 元排列中，如果存在一个大数排在一个小数前面，就称这一对数构成一个逆序。

比如，在 6 元排列 $142365$ 中， $(4, 2)$ 、 $(4, 3)$ 和 $(6, 5)$ 各是一个逆序。

一个排列中，逆序的总数称为逆序数，上述排列的逆序数记作 $t (142365) = 3$ 。再比如，有 $t (32514) = 5$ 。

逆序数为奇数的排列，称作奇排列；逆序数为偶数的排列，称为偶排列。我们在意的不是逆序数本身，而是逆序数的奇偶。

例

\begin{aligned} t (n, n - 1, \dots, 1) = C_{n}^{2} \\ t (1, 3, 5, \dots, 2 n - 1, 2, 4, 6, \dots, 2 n) = 1 + 2 + 3 + \dots + (n - 1) = \frac{1}{2} n (n - 1) \end{aligned}

定理：排列中对换两数的位置，排列的奇偶性改变。

先考虑最简单的，相邻两个数的对换。

(x_{1} x_{2} \dots x_{n}) a b (y_{1} y_{2} \dots y_{m}) \to (x_{1} x_{2} \dots x_{n}) b a (y_{1} y_{2} \dots y_{m})

所有这些逆序： $(x_{i}, a), (x_{i}, b), (a, y_{i}), (b, y_{i})$ 该在还是在，本来没有的也不会多出来 —— 因为他们的相对前后位置不会改变。所以我们只需要考虑 $a, b$ 的大小。剩下的事就很简单了：

{\begin{cases} a > b & t^{'} = t + 1 \\ a < b & t^{'} = t - 1 \end{cases}

也就是说相邻两个数对换，排列的奇偶性会改变。

下面考虑更一般的情况：

(x_{1} x_{2} \dots x_{n}) a \underset{k 个 元 素}{\underset{⏟}{z_{1} z_{2} \dots z_{k}}} b (y_{1} y_{2} \dots y_{m})

我们将其视为多次相邻对换：

\begin{aligned} (x_{1} x_{2} \dots x_{n}) a z_{1} z_{2} \dots z_{k} b (y_{1} y_{2} \dots y_{m}) \\ (1) ⟶ & (x_{1} x_{2} \dots x_{n}) z_{1} a z_{2} \dots z_{k} b (y_{1} y_{2} \dots y_{m}) \\ (2) ⟶ & (x_{1} x_{2} \dots x_{n}) z_{1} z_{2} a \dots z_{k} b (y_{1} y_{2} \dots y_{m}) \\ ⋮ \\ (k) ⟶ & (x_{1} x_{2} \dots x_{n}) z_{1} z_{2} \dots z_{k} a b (y_{1} y_{2} \dots y_{m}) \\ (k + 1) ⟶ & (x_{1} x_{2} \dots x_{n}) z_{1} z_{2} \dots z_{k} b a (y_{1} y_{2} \dots y_{m}) \\ (k + 1 + 1) ⟶ & (x_{1} x_{2} \dots x_{n}) z_{1} z_{2} \dots b z_{k} a (y_{1} y_{2} \dots y_{m}) \\ ⋮ \\ (k + 1 + k) ⟶ & (x_{1} x_{2} \dots x_{n}) b z_{1} z_{2} \dots z_{k} a (y_{1} y_{2} \dots y_{m}) \end{aligned}

也就是总共挪了 $2 k + 1$ 次。显然， $2 k + 1$ 次加一或减一，最后逆序数必然会改变奇偶。

推论：对于任意的 $S_{n}$ ，其中的奇排列和偶排列的数量必然相等。

因为把其中所有的排列的前两个数对换，奇排列都变成了偶排列，偶排列都变成了奇排列，而且所有的排列依然不重不漏。显然二者的数量相同。