（OI相关）置换群：Burnside引理与Polya定理

“于镜中倒映现实，于眼前窥见虚伪。”

更新日志

：

写了一半才发现，自己不会群论基本上理解不了这个玩意儿，所以这篇文章先鸽着，等把群论的学习结束了之后再来。

正好今天就开幕了，多项式的学习也正式踏上行程，事情很多，人也很忙，没时间闲着了。

关于群论

群论（）是离散数学与抽象数学的一个极大分支，与域论，环论同级。本文重点介绍在信息学竞赛（）中用于计数问题的置换群定理中的珀利亚（）定理与伯恩赛德（）引理。

对于数学领域方面的群论，笔者之后会重新写一篇文章~~相对浅显~~地介绍。

置换与置换群

对于一个长度为的全排列，存在一个映射与该序列一一对应。得到一个函数满足，则将称为排列的置换。

如果有，则称该置换为循环置换。

任何一个置换都可以拆分成若干个循环置换。

用图论理解置换

将每一组置换表示为，如果我们将排列转换为一张有个结点的图，并对于每一个映射连接一条有向边，则该图一定会以若干个环的形式出现。

而任意一个环都是一个循环置换。

对于一个排列，其所有的置换方式所组成的集合被称为的置换群，置换群的子群也是置换群。

思考以下问题：

圆环染色

有一个六元环（有个结点的圆环），用红绿蓝给该圆环染色，通过翻转或旋转重叠的方案算同一种，一共有多少种方案。

这是一个类似于圆排列的问题，但涉及到了翻转的问题，意味着对称的染色方法也是不能被记录进答案的。

对于每个置换的不动点，其个数的平均值即不同方案数。