【專題】Polya 計數定理

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 有:


(因為每個非等價著色對左式的貢獻為 1。)

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