【專題】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