【专题】Polya 计数定理

References:

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

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

——————

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

Burnside 定理:

设 $$G$$ 是 $$X$$ 的置换群,而 $$C$$ 是 $$X$$ 中对 $$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:

对于每一种着色 $$c$$,$$c$$ 的稳定核 $$G(c)$$ 是置换群,而且对 $$G$$ 中的任意置换 $$f$$ 与 $$g$$。
$$gc = fc$$ 当且仅当 $$f^{-1} * g$$ 属于 $$G(c)$$。

推论 2:

设 $$c$$ 为 $$C$$ 中的一种着色,那么与 $$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。)


HOJ 2084. The Colored Cubes

inline LL f(DB x){
    return (pow(x, 6) + 3 * pow(x, 4) + 12 * pow(x, 3) + 8 * pow(x, 2)) / 24;
}

int main() {
    int n; while (cin >> n && n){
        cout << f(n) << endl;
    }
}

HOJ 2647. Megaminx

inline LL f(DB x){
    return (pow(x, 12) + 15 * pow(x, 6) + 44 * pow(x, 4)) / 60;
}

int main() {
    int n; while (cin >> n){
        cout << f(n) << endl;
    }
}

SGU 294.

SGU 208. Toral Tickets
http://acm.hust.edu.cn:8080/judge/problem/viewProblem.action?id=14886
http://acm.hust.edu.cn:8080/judge/problem/viewSource.action?id=631448

TJU 2795 The Queen’s New Necklaces

External link:

http://www.cnblogs.com/UESTC_Opera/archive/2010/10/05/1844361.html