波利亞計數定理

维基百科,自由的百科全书
跳转至: 导航搜索

波利亚计数定理(Pólya enumeration theorem,PET)用来研究不同着色方案的计数问题,它是组合数学中的一个重要的计数公式,是伯恩赛德引理的一般化,由乔治·波利亚在1937年的论文[1]中提出并被广泛应用,该结果首先由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)数目。

示例[编辑]

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

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

参考文献[编辑]

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