置换和排列

置换

一个有限集合 到自身的双射（即一一对应）称为 的一个置换。集合 上的置换可以表示为

意为将 映射为 ，其中 是 的一个排列。显然 上所有置换的数量为 。

乘法

对于两个置换 和 ， 和 的乘积记为 ，其值为

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

排列

设 是前 个正整数构成的集合， 是 的一个置换。记：

于是 仍然为 这 个数，只是顺序有所不同。

由 组成的一个有序组，称为 的一个排列。例如把前文 叫做 的一个排列。

前 个正整数 的不同排列共有 个。

逆序和逆序数

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

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

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

对换

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

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

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

定理：当 至少为 时， 个数码的奇排列与偶排列个数相等，各为 个。

逆序数的计算方法

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