查看“波利亞計數定理”的源代码

{{onesource|time=2015-03-05T00:38:32+00:00}}
==波利亚计数定理==
'''波利亚计数定理'''（{{lang-en|Pólya enumeration theorem}}，简称{{lang|en|PET}}）用来研究不同着色方案的计数问题，它是[[组合数学]]中的一个重要的计数公式，是[[伯恩赛德引理]]的一般化，由乔治·波利亚在1937年的论文<ref>G. Pólya. Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Mathematica. 1937, 68 (1): 145–254. doi:10.1007/BF02546665</ref>中提出并被广泛应用，该结果首先由[[John Howard Redfield]]在1927年发表，但当时很少有人能理解，十年后由波利亚独立重新发现。对于含n个对象的置换[[群]]G，用t种颜色着色的不同方案数为：

:<math> l = \frac{1}{|G|}\sum_{g \in G} t^{c(a_g)}</math>

其中 <math> G={a_1,a_2,...,a_g},c(a_k) </math> 为置换<math> a_k </math>的[[循环指标]]（Cycle index）数目。
==波利亚计数定理的母函数形式==

设对n个对象用m种颜色：<math>b_1,b_2,\cdots,b_m</math>着色。设

<math>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)}</math>，其中<math>c_j(p_i)</math>表示置换群中第i个置换循环长度为j的个数。

设<math>S_k = (b_1^k + b_2^k + \cdots + b_m^k), k=1,2\cdots,n</math>，则波利亚计数定理的母函数形式为：

<math>P(G) = \frac{1}{\mid G\mid}\sum_{j = 1}^g\Pi _{k =1}^{n}S_k^{c_k(p_j)}</math>

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

==示例==

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

: <math> \frac{1}{24}\left(2^6+6\times 2^3 + 3\times 2^4 + 6\times 2^3+8\times 2^2\right)\ = 10 </math>

=== 示例2 ===

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

==== 问题解答： ====
甲烷的结构为正四面体，设四面体的四个顶点分别为A、B、C、D，将正四面体的转动群按转动轴分类情况如下：
# 不动旋转：A、B、C、D共有一个(1)<sup>4</sup>循环；
# 以顶点与对对面的中心连线为轴，逆时针旋转±120。存在如下置换所对应的旋转：置换(BCD)与置换(BDC)、置换(ACD)与置换(ADC)、置换(ABD)与置换(ADB)，(ABC)及(ACB)，共计8个(1)<sup>1</sup>(3)<sup>1</sup>循环。
# 以正四面体的3对对边之中点联线为旋转轴旋转180度，(AB)(CD)，(AC)(BD)，(AD)(BC),共有3个(2)<sup>2</sup>循环
根据波利亚计数定理可得:

<math>\frac{1}{12}\left(4^4+8\times 4^2 + 3\times 4^2 \right)\ = 36</math>
== 波利亚计数定理与伯恩赛德引理的比较 ==
* 波利亚计数定理中的群G是作用在n个对象上的置换群。
* 伯恩赛德引理中的群G是对这n个对象染色后的方案集合上的置换群。
* 两个群之间存在一定的联系，群G的元素，相应的在染色方案上也诱导出一个属于G的置换。

==参考文献==
<references/>

[[Category:组合数学]]