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

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