置换和排列

置换

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

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

乘法

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

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

排列

是前 个正整数构成的集合, 的一个置换。记:

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

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

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

逆序和逆序数

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

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

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

对换

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

定理:设 个数码的任意两个排列,那么总可以通过一系列对换,由 得出

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

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

逆序数的计算方法

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