置换和排列

置换¶

一个有限集合 \(S\) 到自身的双射（即一一对应）称为 \(S\) 的一个置换。集合 \(S=\{a_1,a_2,\dots,a_n\}\) 上的置换可以表示为

\[ f=\begin{pmatrix}a_1,a_2,\dots,a_n\\ a_{p_1},a_{p_2},\dots,a_{p_n} \end{pmatrix} \]

意为将 \(a_i\) 映射为 \(a_{p_i}\)，其中 \(p_1,p_2,\dots,p_n\) 是 \(1,2,\dots,n\) 的一个排列。显然 \(S\) 上所有置换的数量为 \(n!\)。

乘法¶

对于两个置换 \(f=\begin{pmatrix}a_1,a_2,\dots,a_n\\a_{p_1},a_{p_2},\dots,a_{p_n}\end{pmatrix}\) 和 \(g=\begin{pmatrix}a_{p_1},a_{p_2},\dots,a_{p_n}\\a_{q_1},a_{q_2},\dots,a_{q_n}\end{pmatrix}\)，\(f\) 和 \(g\) 的乘积记为 \(f\circ g\)，其值为

\[ f\circ g=\begin{pmatrix}a_1,a_2,\dots,a_n\\ a_{q_1},a_{q_2},\dots,a_{q_n}\end{pmatrix} \]

简单来说就是先后经过 \(f\) 的映射，再经过 \(g\) 的映射。

排列¶

设 \(I=\{1,2,\cdots,n\}\) 是前 \(n\) 个正整数构成的集合，\(\sigma\) 是 \(I\) 的一个置换。记：

\[ \sigma(1)=i_1\quad\sigma(2)=i_2\quad\cdots\quad\sigma(n)=i_n \]

于是 \(i_1,i_2,\cdots,i_n\) 仍然为 \(1,2,\cdots,n\) 这 \(n\) 个数，只是顺序有所不同。

由 \(1,2,\cdots,n\) 组成的一个有序组，称为 \(1,2,\cdots,n\) 的一个排列。例如把前文 \(i_1,i_2,\cdots,i_n\) 叫做 \(1,2,\cdots,n\) 的一个排列。

前 \(n\) 个正整数 \(1,2,\cdots,n\) 的不同排列共有 \(n!\) 个。

逆序和逆序数¶

在一个排列中，如果某一个较大的数排在某一个较小的数前面，就说这两个数构成一个反序或逆序。

在一个排列里出现的反序的总个数，叫做这个排列的反序数或逆序数。

一个排列的反序数可能是偶数也可能是奇数。有偶数个反序的排列叫做一个偶排列，有奇数个反序的排列叫做一个奇排列。

对换¶

如果把 \(1,2,\cdots,n\) 的排列中，任意两个数 \(i\) 和 \(j\) 交换，其余数保持不动，就得到一个新排列。对于排列施加这样一个变换叫做一个对换，用 \((i,j)\) 表示。

定理：设 \(i_1i_2\cdots i_n\) 和 \(j_1j_2\cdots j_n\) 是 \(n\) 个数码的任意两个排列，那么总可以通过一系列对换，由 \(i_1i_2\cdots i_n\) 得出 \(j_1j_2\cdots j_n\)。

定理：每一个对换都改变排列的奇偶性。

定理：当 \(n\) 至少为 \(2\) 时，\(n\) 个数码的奇排列与偶排列个数相等，各为 \(\frac{n!}{q}\) 个。

逆序数的计算方法¶

逆序数的编程计算方法，可以使用归并排序，时间复杂度为 \(O(n\log n)\)。