置换群

置换

一个有限集合到自身的双射，称为的一个置换，集合上的置换可以表示为 即，将映射为，其中是的一个排列

逆序和逆序数

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

对换

把排列中任意两个数字和交换，其余数保持不动，就得到一个新排列，对排列进行的这样的变换叫做对换

• 每一个对换都改变排列的奇偶性

置换群

集合上的所有置换关于置换的乘法满足封闭性，结合律，有单位元，有逆元，因此构成一个群，这个群的任意一个子群叫做置换群

循环置换

不相交的置换

如果两个循环置换不含有相同元素，则称它们是不相交的

Burnside引理

设和为有限集合，是一些从到的映射组成的集合，是上的置换群，且中的映射在中的置换作用下封闭，表示作用在上产生的所有等价类的集合，则：

set A;
set B;
set X; {{a1->b1,a2->b1,a3->b2...},...} // X可以用来表示，不考虑本质不同的方案的集合
set G; // G可以用来表示各种等价操作（翻转/对称/旋转）
set ans=X/G; // 本质不同的方案的集合
set X^g; // 对于某一种等价操作g，经过这种g操作后不变的x