波利亞計數定理

波利亚计数定理(英語: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,将正四面体的转动群按转动轴分类情况如下:

  1. 不动旋转:A、B、C、D共有一个(1)4循环;
  2. 以顶点与对对面的中心连线为轴,逆时针旋转±120。存在如下置换所对应的旋转:置换(BCD)与置换(BDC)、置换(ACD)与置换(ADC)、置换(ABD)与置换(ADB),(ABC)及(ACB),共计8个(1)1(3)1循环。
  3. 以正四面体的3对对边之中点联线为旋转轴旋转180度,(AB)(CD),(AC)(BD),(AD)(BC),共有3个(2)2循环

根据波利亚计数定理可得:

 

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

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

参考文献

  1. ^ G. Pólya. Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Mathematica. 1937, 68 (1): 145–254. doi:10.1007/BF02546665

延伸閱讀