波利亚计数定理

波利亚计数定理（英语：Pólya enumeration theorem，简称PET）用来研究不同着色方案的计数问题，它是组合数学中的一个重要的计数公式，是伯恩赛德引理的一般化，由乔治·波利亚在1937年的论文中提出并被广泛应用，该结果首先由John Howard Redfield在1927年发表，但当时很少有人能理解，十年后由波利亚独立重新发现。对于含n个对象的置换群G，用t种颜色着色的不同方案数为：

其中 G=a1,a2,...,ag,c(ak){\displaystyle G={a_{1},a_{2},...,a_{g}},c(a_{k})} 为置换ak{\displaystyle a_{k}}的循环指标（Cycle index）数目。

波利亚计数定理的母函数形式

设对n个对象用m种颜色：b1,b2,⋯ ⋯ -->,bn{\displaystyle b_{1},b_{2},\cdots ,b_{n}}着色。设

mc(pi)=(b1+b2+⋯ ⋯ -->+bm)c1(pi)(b12+b22+⋯ ⋯ -->+bm2)c2(pi)⋯ ⋯ -->(b1n+b2n+⋯ ⋯ -->+bmn)cn(pi){\displaystyle 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})}}，其中cj(pi){\displaystyle c_{j}(p_{i})}表示置换群中第i个置换循环长度为j的个数。

设Sk=(b1k+b2k+⋯ ⋯ -->+bmk),k=1,2⋯ ⋯ -->,n{\displaystyle S_{k}=(b_{1}^{k}+b_{2}^{k}+\cdots +b_{m}^{k}),k=1,2\cdots ,n}，则波利亚计数定理的母函数形式为：

P(G)=1∣ ∣ -->G∣ ∣ -->∑ ∑ -->j=1gΠ Π -->k=1nSkck(pj){\displaystyle P(G)={\frac {1}{\mid G\mid }}\sum _{j=1}^{g}\Pi _{k=1}^{n}S_{k}^{c_{k}(p_{j})}}

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

示例

示例1

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

示例2

问题描述：

甲烷CH4的4个键任意用H(氢),Cl(氯),CH3(甲基), C2H5(乙基) 连接，有多少种方案？ 

问题解答：

甲烷的结构为正四面体，设四面体的四个顶点分别为A、B、C、D，将正四面体的转动群按转动轴分类情况如下：

不动旋转：A、B、C、D共有一个(1)循环；

以顶点与对对面的中心连线为轴，逆时针旋转±120。存在如下置换所对应的旋转：置换(BCD)与置换(BDC)、置换(ACD)与置换(ADC)、置换(ABD)与置换(ADB)，(ABC)及(ACB)，共计8个(1)(3)循环。

以正四面体的3对对边之中点联线为旋转轴旋转180度，(AB)(CD)，(AC)(BD)，(AD)(BC),共有3个(2)循环

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

112(44+8× × -->42+3× × -->42) =36{\displaystyle {\frac {1}{12}}\left(4^{4}+8\times 4^{2}+3\times 4^{2}\right)\ =36}

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

波利亚计数定理中的群G是作用在n个对象上的置换群。

伯恩赛德引理中的群G是对这n个对象染色后的方案集合上的置换群。

两个群之间存在一定的联系，群G的元素，相应的在染色方案上也诱导出一个属于G的置换

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。