波利亞計數定理(英語:Pólya enumeration theorem,簡稱PET)用來研究不同着色方案的計數問題,它是組合數學中的一個重要的計數公式,是伯恩賽德引理的一般化,由波利亞·哲爾吉在1937年的論文[1]中提出並被廣泛應用,該結果首先由John Howard Redfield在1927年發表,但當時很少有人能理解,十年後由波利亞獨立重新發現。對於含n個對象的置換群G,用t種顏色着色的不同方案數為:
![{\displaystyle l={\frac {1}{|G|}}\sum _{g\in G}t^{c(a_{g})}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9142090f9fb4eb68ec6b15e0015a50dab9f0a510)
其中
為置換
的循環指標(Cycle index)數目。
波利亞計數定理的母函數形式
設對
個對象用
種顏色:
着色。設
,其中
表示置換群中第
個置換循環長度為
的個數。
設
,則波利亞計數定理的母函數形式為:
波利亞計數定理只是給出計數,但沒有給出相應的方案,而母函數形式的波利亞計數定理可以給出相應的方案。
示例
示例1
使用兩種顏色對正方體的六個面的面染色,不同的染色方案數有:
![{\displaystyle {\frac {1}{24}}\left(2^{6}+6\times 2^{3}+3\times 2^{4}+6\times 2^{3}+8\times 2^{2}\right)\ =10}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1207912adf25d2242b55335671fd3e08740b3a28)
示例2
問題描述:
甲烷CH4的4個鍵任意用H(氫),Cl(氯),CH3(甲基), C2H5(乙基) 連接,有多少種方案?
問題解答:
甲烷的結構為正四面體,設四面體的四個頂點分別為A、B、C、D,將正四面體的轉動群按轉動軸分類情況如下:
- 不動旋轉:A、B、C、D共有一個(1)4循環;
- 以頂點與對對面的中心連線為軸,逆時針旋轉±120。存在如下置換所對應的旋轉:置換(BCD)與置換(BDC)、置換(ACD)與置換(ADC)、置換(ABD)與置換(ADB),(ABC)及(ACB),共計8個(1)1(3)1循環。
- 以正四面體的3對對邊之中點聯線為旋轉軸旋轉180度,(AB)(CD),(AC)(BD),(AD)(BC),共有3個(2)2循環
根據波利亞計數定理可得:
波利亞計數定理與伯恩賽德引理的比較
- 波利亞計數定理中的群G是作用在n個對象上的置換群。
- 伯恩賽德引理中的群G是對這n個對象染色後的方案集合上的置換群。
- 兩個群之間存在一定的聯繫,群G的元素,相應的在染色方案上也誘導出一個屬於G的置換。
參考文獻
- ^ G. Pólya. Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Mathematica. 1937, 68 (1): 145–254. doi:10.1007/BF02546665
延伸閱讀