【专题】Polya 计数定理

References:

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

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

——————

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

Burnside 定理:

GX 的置换群,而 CX 中对 G 封闭的着色集合。
C 中非等价着色数 N(G, C) 由下式给出:

 |G| N(G, C) = \sum_{f\in g}|C(f)|

Polya 定理:

f 是集合 X 的置换。假如我们用 k 种颜色对 X 着色,则对 f 不变的着色数与 f 的循环数 r 有关:

 |C(f)| = k^r

。。。

——————

证明:

引理 1:

对于每一种着色 cc 的稳定核 G(c) 是置换群,而且对 G 中的任意置换 fg
g<em>c = f</em>c 当且仅当 f^{-1} * g 属于 G(c)

推论 2:

cC 中的一种着色,那么与 c 等价的着色数等于 G 中置换个数,除以 c 的稳定核中置换的个数。

 N(c) = |{f*c: f\in G}| = \frac{|G|}{|G(c)|}

Burnside 定理:

。。考察。。所有满足 f*c = c 的二元组 (f, c)。。双计数。。
枚举 f 。。得到 \sum_{f\in g}|C(f)|。。(通过置换 f 不变的着色几何)
枚举 c 。。得到 \sum_{c\in C}|G(c)|。。(c 关于置换群 G 的稳定核)
根据推论 2 有:

 |G(c)| N(c) = |G|


\sum_{c\in C} \frac{1}{N(c)} = N(G,C)

(因为每个非等价着色对左式的贡献为 1。)

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