台湾 || 语言: 大陆简体港澳繁體台灣正體

Polya定理

雪花台灣 2019-04-27 01:12

Polya定理給出了以置換作為等價關係的條件下，等價類的計數方法，形象的說，這個就是求出了本質不同的染色方案數。這篇文章就是整理一下Polya定理的證明過程。

一些定義與記號

為置換群；

$G_x={gin G|gcdot x=x}$ ；

$X^g={xin X|gcdot x=x}$ ；

的軌道(orbit)為；

為置換所包含的循環個數。

軌道-穩定集定理(Orbit-stabilizer theorem)

定理內容為。

考慮映射，通過這個映射可以在的左陪集的集合和軌道間建立一個雙射，唯一對應，因為中的任意元素作用於的結果均為。

結合拉格朗日定理，故有 $|Gcdot x|=[G:G_x]=frac{|G|}{|G_x|}$ ，即。

Burnside引理

等價類個數為不動點個數的平均值，即 $|X/G|=frac{1}{|G|}sum_{gin G}|X^g|$ 。

對右側的 $sum_{gin G}|X^g|$ 改變求和方式，

$sum_{gin G}|X^g|=|{(g,x)in G imes X|gcdot x = x}|=sum_{xin X}|G_x|$ 。

根據軌道-穩定集定理，

$sum_{xin X}|G_x|=sum_{xin X}frac{|G|}{|Gcdot x|}=|G|sum_{xin X}frac{1}{|Gcdot x|}$ 。

將按照等價類劃分再求和，軌道實際上就是所在等價類，

$sum_{xin X}frac{1}{|Gcdot x|}=sum_{Ain X/G}sum_{xin A}frac{1}{|A|}=sum_{Ain X/G}1=|X/G|$ 。

所以 $|G||X/G|=sum_{xin X}|G_x|=sum_{gin G}|X^g|$ 。

Polya定理

Burnside引理已經給出了等價類個數的表達式，Polya定理進一步具體到染色問題上，給出了本質不同的染色方案數的表達式。

對於有種顏色的染色問題， $|X^g|=m^{c(g)}$ 。

考慮它的組合意義，表示的是在置換的作用下，保持不變的染色方案數。將分解為不相交的個循環的乘積，若要某個染色方案不變，則在這個染色方案中，的每個循環對應的元素都要染相同的顏色。一個循環可選種顏色，共有個循環，所以總共有 $m^{c(g)}$ 種方案，故 $|X^g|=m^{c(g)}$ 。

將這個等式代入Burnside引理中，得到總的染色方案數為 $frac{1}{|G|}sum_{gin G}m^{c(g)}$ 。

推薦閱讀：

相关文章