波利亚计数定理 |
您所在的位置：网站首页 › 伯恩赛德引理 › 波利亚计数定理 |
波利亚计数定理
|
波利亚计数定理（英语：Pólya enumeration theorem，简称PET）用来研究不同着色方案的计数问题，它是组合数学中的一个重要的计数公式，是伯恩赛德引理的一般化，由波利亚·哲尔吉在1937年的论文[1]中提出并被广泛应用，该结果首先由John Howard Redfield在1927年发表，但当时很少有人能理解，十年后由波利亚独立重新发现。对于含n个对象的置换群G，用t种颜色着色的不同方案数为： l = 1 | G | ∑ g ∈ G t c ( a g ) {\displaystyle l={\frac {1}{|G|}}\sum _{g\in G}t^{c(a_{g})}} 此条目或其章节极大或完全地依赖于某个单一的来源。 (2015年3月5日)
其中 G = a 1 , a 2 , . . . , a g , c ( a k ) {\displaystyle G={a_{1},a_{2},...,a_{g}},c(a_{k})} 为置换 a k {\displaystyle a_{k}} 的循环指标（Cycle index）数目。 |
为置换
a
k
{\displaystyle a_{k}}
的循环指标（Cycle index）数目。
【本文地址】