References:

Polya 定理再小结
组合数学 原书第 5 版
除数函数的渐近上界？ by vfleaking

。。统计在某个置换群作用下。。计算不等价的着色方案数的问题。。。
。。可以通过 Burnside 定理。。转化为枚举每一个置换。。。统计在该置换作用下等价的着色方案数的问题。。
。。而 Polya 定理则是巧妙的利用同一循环内着色必须相同这个事实，进一步简化后者的计算。。。

——————

习题：
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=2823#overview

Burnside 定理：

设 是 的置换群，而 是 中对 封闭的着色集合。
则 中非等价着色数 由下式给出：

Polya 定理：

设 是集合 的置换。假如我们用 种颜色对 着色，则对 不变的着色数与 的循环数 有关：

——————

证明：

引理 1：

对于每一种着色 ， 的稳定核 是置换群，而且对 中的任意置换 与 。
当且仅当 属于 。

推论 2：

设 为 中的一种着色，那么与 等价的着色数等于 中置换个数，除以 的稳定核中置换的个数。

Burnside 定理：

。。考察。。所有满足 的二元组 。。双计数。。
枚举 f 。。得到 。。（通过置换 不变的着色几何）
枚举 c 。。得到 。。（c 关于置换群 的稳定核）
根据推论 2 有：

ゆっくり読んでください ...