波利亞計數定理
此條目或其章節極大或完全地依賴於某個單一的來源。 (2015年3月5日) |
波利亞計數定理(英語:Pólya enumeration theorem,簡稱PET)用來研究不同着色方案的計數問題,它是組合數學中的一個重要的計數公式,是伯恩賽德引理的一般化,由波利亞·哲爾吉在1937年的論文[1]中提出並被廣泛應用,該結果首先由John Howard Redfield在1927年發表,但當時很少有人能理解,十年後由波利亞獨立重新發現。對於含n個對象的置換群G,用t種顏色着色的不同方案數為:
其中 為置換的循環指標(Cycle index)數目。
波利亞計數定理的母函數形式
編輯設對 個對象用 種顏色: 着色。設
,其中 表示置換群中第 個置換循環長度為 的個數。
設 ,則波利亞計數定理的母函數形式為:
波利亞計數定理只是給出計數,但沒有給出相應的方案,而母函數形式的波利亞計數定理可以給出相應的方案。
示例
編輯示例1
編輯使用兩種顏色對正方體的六個面的面染色,不同的染色方案數有:
示例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
延伸閱讀
編輯- 蕭文強. 波利亚计数定理. 大連理工大學出版社. 2011. ISBN 9787561161487.