置换和排列

置换

一个有限集合到自身的双射（即一一对应）称为的一个置换。集合 $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_{p_i}$ ，其中 $p_1,p_2,\dots,p_n$ 是 $1,2,\dots,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}$ ，和的乘积记为 $g\circ f$ ，其值为

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

简单来说就是先经过的映射，再经过的映射。

排列

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

\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$ 这个数，只是顺序有所不同。

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

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

逆序和逆序数

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

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

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

对换

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

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

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

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

逆序数的计算方法

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