波利亞計數定理

Template:Onesource 波利亚计数定理（Template:Lang-en，简称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{\mathrm{\Pi }}_{k=1}^n{S}_k^{c_k(p_j)}$

波利亚计数定理只是给出计数，但没有给出相应的方案，而母函数形式的波利亚计数定理可以给出相应的方案。

示例

示例1

使用两种颜色对正方体的六个面的面染色，不同的染色方案数有：

$\frac{1}{24}(2^6+6\times 2^3+3\times 2^4+6\times 2^3+8\times 2^2)=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}(4^4+8\times 4^2+3\times 4^2)=36$

波利亚计数定理与伯恩赛德引理的比较

• 波利亚计数定理中的群G是作用在n个对象上的置换群。
• 伯恩赛德引理中的群G是对这n个对象染色后的方案集合上的置换群。
• 两个群之间存在一定的联系，群G的元素，相应的在染色方案上也诱导出一个属于G的置换。

延伸閱讀

• Template:Cite book