Burnside & Pólya
（详细内容请参阅《组合数学》或2008年cyx的论文，这里只写一些我学习的时候理解困难的几个点，觉得我SB的请轻鄙视……如果有觉得不科学的地方欢迎留言）
Burnside：
我们要证明的是：$$N(G,C)=frac{1}{|G|} sum_{f in G}|C(f)|$$
难点一：非等价着色数=等价类数目（$N(G,C)$），这其实是从等价类的定义来的。。。因为一个等价类表示着一种与众不同的染色方案，当然有多少个等价类就有多少种非等价染色方案啦……（我是SB没想到QAQ）
证明主要是这样一个过程：（UOJ群神犇_数学迷：算两次，即同一个量以两种方法计算得到一个式子的方法）
难点二：我们的式子是：$$sum_{f in G} |C(f)| = sum_{c in C} |G(c)| $$
（我以二分图的模型来解释或许好理解一些？）
我们现在有 n 种染色方式（其中有一些是等价的），m 种置换。对于某种染色$c$和置换$f$，如果我们有 $f*c=c$，我们就连一条边 $c->f$
所以左边的点的度数和=右边的点的度数和=总边数
接下来，因为有（这个大概也算个难点吧……）$$ (与c等价的着色数)=frac{|G|}{|G(c)|} $$
所以：$$ |G(c)|=frac{|G|}{(与c等价的着色数)} $$
因此我们可以对刚刚的右边的式子变形，得到：$$ sum_{c in C} |G(c)|=|G| sum_{c in C} frac{1}{(与c等价的着色数)}$$
难点三：这里我们发现：每一种着色方式我们都加了$frac{1}{(与c等价的着色数)}$，我们可以按等价类分开，等价类中的每一种着色方式都加了$$frac{1}{这个等价类的大小}$$所以每个等价类的贡献就是1，所以刚刚的右边的式子等于$$|G|*N(G,C)$$
得证。
Pólya：
了解了Burnside定理以后，我们对于等价类计数就有了这样一个方法：枚举染色方式（枚举每一格的染色方式）和置换方式，找到每个置换方式的不动点数目……然而这个复杂度比较高，所以我们可以拿Pólya来优化一下~
Pólya的做法是：只考虑染色的种类以及置换的方式，然后直接用【循环分解】的方式计算出每个置换的不动点数目，这样就少枚举了一维，降低了复杂度。（枚举每个置换，循环分解是O(p)的，p是格子数）
（然而刚刚的bb其实是不完整的，不过先这样理解好了。。。复杂一点的我也不会TAT）
刚刚说到直接用循环分解的方式计算出每个置换的不动点数目，这是怎么回事呢？我们发现，在这个置换下不动的染色方案，每一个循环一定是染了相同的颜色，所以这个置换方式下不动点数目就是 $(颜色数)^{(循环数)}$
不过我刚刚说的只是限于一种简单的情况……更多更完整的问题……还是看书吧T_T我这么弱……是吧……