波利亚计数定理

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

其中 ${\displaystyle G=a_1,a_2,...,a_g,c(a_k)}$ 为置换${\displaystyle a_k}$的循环指标（Cycle index）数目。

设对n个对象用m种颜色：${\displaystyle b_1,b_2,\cdots <!--\; \cdots \; -->,b_m}$着色。设

${\displaystyle m^{c(p_i)}=(b_1+b_2+\cdots <!--\; \cdots \; -->+b_m{)}^{c_1(p_i)}(b_1^2+b_2^2+\cdots <!--\; \cdots \; -->+b_m^2{)}^{c_2(p_i)}\cdots <!--\; \cdots \; -->(b_1^n+b_2^n+\cdots <!--\; \cdots \; -->+b_m^n{)}^{c_n(p_i)}}$，其中${\displaystyle c_j(p_i)}$表示置换群中第i个置换循环长度为j的个数。

设${\displaystyle S_k=(b_1^k+b_2^k+\cdots <!--\; \cdots \; -->+b_m^k),k=1,2\cdots <!--\; \cdots \; -->,n}$，则波利亚计数定理的母函数形式为：

${\displaystyle P(G)=\frac{1}{\mid <!--\; \mid \; -->G\mid <!--\; \mid \; -->}\underset{j=1}{\overset{g}{\sum <!--\; \sum \; -->}}{\mathrm{\Pi <!--\; \Pi \; -->}}_{k=1}^n{S}_k^{c_k(p_j)}}$

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

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

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

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

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

${\displaystyle \frac{1}{12}\left(4^4+8\times <!--\; \times \; -->4^2+3\times <!--\; \times \; -->4^2\right)=36}$