如果没有学过正经的带群论的 \(Polya\)，那这一篇文章也许是一个简单的入门；如果学过正经的 \(Polya\)，这一篇也可能提供一个感性理解的方法（因为除了不用群论也没有什么好处）。
Burnside
一道组合题一般会说
两个图等价当且仅当可以通过重编号使之全等
两个环等价当且仅当可以通过旋转使之重合
先考虑一个简单题：
求环排列数 \(\pi_n\)
这时的要求就是上面第二个。
一个 \(\text{naive}\) 的想法是环排列不多于排列，\(\pi_n\le n!\) 。
不等式成立的原因是有一些情况被重复数了，那一个更 \(\text{naive}\) 的想法是我知道每种情况被数了多少次不就可以了。
比如用 \([1,2,3]\) 表示一个环排列，不考虑重复时，长为 \(3\) 的环排列有 \([1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]\)。
容易知道 \(\pi_3=2\)，因为 \([1,2,3]\) 旋转一次变成 \([2,3,1]\)，再转一次变成 \([3,1,2]\)。
采用一种均摊的思想，可以认为之前 \(6\) 种环排列，每种对应了有效的 \(\frac13\) 种。
因为我们有 \(3\) 种旋转（不转，转一次，转两次，再多就还原了），任意环排列对每种旋转都会得到看上去不同，但本质相同的环排列。
类似的，\(\pi_n\) 中每个看上去不同的环排列对应的 \(n\) 种旋转都会得到看起来不同，但本质相同的环排列，可以视作对应有效的 \(\frac1n\) 种。
于是我们知道 \(\pi_n=\frac1n\times n!=(n-1)!\)（任意排列对应看上去不同的环排列，但只有有效的 \(\frac1n\) 种）。
刚刚的问题其实有两种计算方法，一种是计算每种排列对应有效的几种，另一种是找到每个变换方式下和不变的情况下看上去也一样的排列数（这是因为看去来一样，本质也相同的排列应该被计数多次，更困难的例子将给出示范）。
在环排列的问题中，只有不旋转的情况下所有排列和不变的情况看上去也完全等价（用群论的说法，所有环排列都是“不旋转”这一变换方式的不动点，为了方便，后文将借用这一说法）。
于是 \(\pi_n=\frac1n\times n!\)，虽然表达式一样，但含义稍有区别。这里 \(n\) 表示所有变换方式，\(n!\) 表示不旋转的变换方式下的不动点（这样没有施加任何操作的变换方式在群论中被称为恒等置换），其他情况下均没有不动点。为了组合意义更明确，可以写成 \(\pi_n=\frac1n\times(n!+\sum_{1\le k<n}0)\)。
第一种方法的复杂度显然是 \(O(n!)\)，因为需要枚举所有方案数；第二种方法则只需要枚举所有变换方法，然后求解每种方法下的不动点数。
再看一个更困难的例子
用 \(3\) 种颜色给一个正五边形的顶点染色，两种方案本质相同当且仅当可以通过旋转、翻折重叠。
类比上面环排列的做法，第一步找到所有可能的变换方式（用群论中说得，叫作置换），有 \(5\) 种旋转，翻折与否。
不妨用 \(R_0,R_1,R_2,R_3,R_4\) 表示旋转次数，加 \(F\) 表示翻折，比如 \(FR_2\) 表示先旋转两次再翻折。
不难发现只有这 \(10\) 种本质不同的变换方式（这个只能枚举，但通常比直接计算答案简单得多）。
第二步，求解所有置换下的不动点数。
显然 \(R_0\) 是恒等置换，所有可能的情况都是不动点，共 \(3^5\) 个。
\(R_1,R_2,R_3,R_4\) 则必须要只用一种颜色才行，都只有 \(3\) 个不动点。
\(FR_0\) 的不动点要求左右对称，有 \(3^3\) 个不动点。
\(FR_1,FR_2,FR_3,FR_4\) 要困难一点，画个图可以知道都只有 \(3^3\) 个不动点。
所以答案是 \(\frac{1}{10}\times(3^5+3\times4+3^3+3^3\times4)=39\)。
如果颜色数为 \(k\)，我们就得到更一般的公式 \(\frac{k^5+5k^3+4k}{10}\)（数论知识告诉我们这一定是一个整数，这增强了我们对该方法的信心）。
这个流程就是 \(\text{Burnside}\) 引理，更数学地写出
\[F=\frac{1}{|G|}\sum_{\sigma\in G}Z_\sigma \]其中 \(G\) 表示所有置换构成的集合，也就是一共有多少种不同的变换方法，\(Z_\sigma\) 表示置换 \(\sigma\) 下的不动点个数。
\(\text{Burnside}\) 引理比 \(Polya\) 定理更本质，在某些情况下也更有用。
Polya 定理
虽然 \(\text{Burnside}\) 已经十分强大，但我们在判断每种置换下有多少个不动点时仍会遇到困难，这时 \(Polya\) 定理考虑了一种特殊的情况：
用 \(m\) 种颜色给 \(n\) 个点的排列染色
此时的置换可以一般化为排列之间的映射，比如上例中 \(FR_2\) 可以表示为 \([1,2,3,4,5]\to[4,3,2,1,5]\)。
我们不容易从中看出规律，因为之后我们可以知道 \(5\) 是比较特殊的。
从 \(6\) 来看更容易找到规律，以 \(R_2\) 为例，\([1,2,3,4,5,6]\to[3,4,5,6,1,2]\)，可以直观地发现长为 \(2\) 的循环节，只需要每个循环节中任意染色即可。
把循环节的概念推广，任何环形的置换都可以叫做循环（这里和群论中是一样的），比如 \([1,4]\to[4,1],[2,3,5]\to[3,5,2]\) 都是循环，但 \([1,2,3]\to[2,1,3]\) 就不是一个循环，而是 \([1,2]\to[2,1],[3]\to[3]\) 两个循环组合而成的。
显然，置换全部可以写成有限个循环的组合（每个数跳到自己对应的数上，因为每个数对应的数不同且一定有数对应自己，所以每个数都属于且仅属于一个循环，所以循环数不多于数的总数）。
要做到变换之后看起来一样，只需要每个循环内相同，比如之前的例子 \([1,2,3,4,5,6]\to[3,4,5,6,1,2]\) 就有两个循环 \([1,3,5]\to[3,5,1],[2,4,6]\to[4,6,2]\)，可以看到这和朴素的循环节思想是一致的。因此，假如置换 \(\sigma\) 由 \(k\) 个循环节组成，就有 \(Z_\sigma=m^k\)。
用给五边形染色的例子，\(FR_2\) 表示成 \(3\) 个循环 \([1,4]\to[4,1],[2,3]\to[3,2],[5]\to[5]\)，所以有 \(3^3\) 个不动点。ss
求解出每个置换对应的循环数再带入 \(\text{Burnside}\) 引理中就有 \(\text{Polya}\) 定理
\[F=\frac{1}{|G|}\sum_{\sigma\in G}m^{|\sigma|} \]其中 \(|\sigma|\) 表示 \(\sigma\) 的循环数。
标签：FR,排列,置换,不用,循环,群论,不动点,Polya,sigma From： https://www.cnblogs.com/efX-bk/p/18251693