波利亚计数定理
维基百科,自由的 encyclopedia
波利亚计数定理(英语:Pólya enumeration theorem,简称PET)用来研究不同着色方案的计数问题,它是组合数学中的一个重要的计数公式,是伯恩赛德引理的一般化,由波利亚·哲尔吉在1937年的论文[1]中提出并被广泛应用,该结果首先由John Howard Redfield在1927年发表,但当时很少有人能理解,十年后由波利亚独立重新发现。对于含n个对象的置换群G,用t种颜色着色的不同方案数为:
此条目或其章节极大或完全地依赖于某个单一的来源。 (2015年3月5日) |
其中 为置换的循环指标(Cycle index)数目。