波利亞計數定理

波利亞計數定理（英語：Pólya enumeration theorem，簡稱PET）用來研究不同着色方案的計數問題，它是組合數學中的一個重要的計數公式，是伯恩賽德引理的一般化，由波利亞·哲爾吉在1937年的論文中提出並被廣泛應用，該結果首先由John Howard Redfield在1927年發表，但當時很少有人能理解，十年後由波利亞獨立重新發現。對於含n個對象的置換群G，用t種顏色着色的不同方案數為：

$l={\frac {1}{|G|}}\sum _{g\in G}t^{c(a_{g})}$

其中 $G={a_{1},a_{2},...,a_{g}},c(a_{k})$ 為置換$a_{k}$的循環指標（Cycle index）數目。

波利亞計數定理的母函數形式

設對$n$個對象用$m$種顏色：$b_{1},b_{2},\cdots ,b_{m}$着色。設

$m^{c(p_{i})}=(b_{1}+b_{2}+\cdots +b_{m})^{c_{1}(p_{i})}(b_{1}^{2}+b_{2}^{2}+\cdots +b_{m}^{2})^{c_{2}(p_{i})}\cdots (b_{1}^{n}+b_{2}^{n}+\cdots +b_{m}^{n})^{c_{n}(p_{i})}$，其中$c_{j}(p_{i})$表示置換群中第$i$個置換循環長度為$j$的個數。

設$S_{k}=(b_{1}^{k}+b_{2}^{k}+\cdots +b_{m}^{k}),k=1,2\cdots ,n$，則波利亞計數定理的母函數形式為：

$P(G)={\frac {1}{\mid G\mid }}\sum _{j=1}^{g}\Pi _{k=1}^{n}S_{k}^{c_{k}(p_{j})}$

波利亞計數定理只是給出計數，但沒有給出相應的方案，而母函數形式的波利亞計數定理可以給出相應的方案。

示例

示例1

使用兩種顏色對正方體的六個面的面染色，不同的染色方案數有：

${\frac {1}{24}}\left(2^{6}+6\times 2^{3}+3\times 2^{4}+6\times 2^{3}+8\times 2^{2}\right)\ =10$

示例2

問題描述：

甲烷CH4的4個鍵任意用H(氫),Cl(氯),CH3(甲基), C2H5(乙基) 連接，有多少種方案？ 

問題解答：

甲烷的結構為正四面體，設四面體的四個頂點分別為A、B、C、D，將正四面體的轉動群按轉動軸分類情況如下：

1. 不動旋轉：A、B、C、D共有一個(1)⁴循環；
2. 以頂點與對對面的中心連線為軸，逆時針旋轉±120。存在如下置換所對應的旋轉：置換(BCD)與置換(BDC)、置換(ACD)與置換(ADC)、置換(ABD)與置換(ADB)，(ABC)及(ACB)，共計8個(1)¹(3)¹循環。
3. 以正四面體的3對對邊之中點聯線為旋轉軸旋轉180度，(AB)(CD)，(AC)(BD)，(AD)(BC),共有3個(2)²循環

根據波利亞計數定理可得:

${\frac {1}{12}}\left(4^{4}+8\times 4^{2}+3\times 4^{2}\right)\ =36$

波利亞計數定理與伯恩賽德引理的比較

• 波利亞計數定理中的群G是作用在n個對象上的置換群。
• 伯恩賽德引理中的群G是對這n個對象染色後的方案集合上的置換群。
• 兩個群之間存在一定的聯繫，群G的元素，相應的在染色方案上也誘導出一個屬於G的置換。

延伸閱讀

• 蕭文強. 波利亚计数定理. 大連理工大學出版社. 2011. ISBN 9787561161487.