波利亚计数定理

✍ dations ◷ 2025-04-26 13:24:42 #组合数学

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

其中 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)数目。

设对n个对象用m种颜色: b 1 , b 2 , , b m {\displaystyle b_{1},b_{2},\cdots ,b_{m}} 着色。设

m c ( p i ) = ( b 1 + b 2 + + b m ) c 1 ( p i ) ( b 1 2 + b 2 2 + + b m 2 ) c 2 ( p i ) ( b 1 n + b 2 n + + b m n ) c n ( p i ) {\displaystyle 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})}} ,其中 c j ( p i ) {\displaystyle c_{j}(p_{i})} 表示置换群中第i个置换循环长度为j的个数。

S k = ( b 1 k + b 2 k + + b m k ) , k = 1 , 2 , n {\displaystyle S_{k}=(b_{1}^{k}+b_{2}^{k}+\cdots +b_{m}^{k}),k=1,2\cdots ,n} ,则波利亚计数定理的母函数形式为:

P ( G ) = 1 G j = 1 g Π k = 1 n S k c k ( p j ) {\displaystyle P(G)={\frac {1}{\mid G\mid }}\sum _{j=1}^{g}\Pi _{k=1}^{n}S_{k}^{c_{k}(p_{j})}}

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

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

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

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

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

1 12 ( 4 4 + 8 × 4 2 + 3 × 4 2 )   = 36 {\displaystyle {\frac {1}{12}}\left(4^{4}+8\times 4^{2}+3\times 4^{2}\right)\ =36}

相关

  • 甲烷生成产甲烷作用,又称甲烷生成,指合成甲烷是微生物代谢的重要的和广泛的形式。可以生成甲烷的微生物称作产甲烷菌(英语:Methanogen)。这些微生物都属于原核生物中的古菌域,这是在系统发
  • 国立台北护理健康大学国立台北护理健康大学,简称北护大、国北护、北护,是一所位于台湾台北市的国立科技大学,以教授健康科学课程为主。内江街校址为城区部,仅语言治疗与听力学系暨硕士班、健康事业管
  • 甲硫氨酸的再生甲硫氨酸(英语:Methionine,又称蛋氨酸),在所有后生动物中它是一种必需氨基酸。与半胱氨酸一起,甲硫氨酸是两个含硫蛋白原氨基酸之一。对人而言是唯一的含硫必需氨基酸,有L型及D型两
  • Belfast坐标:54°35′50″N 5°55′48″W / 54.5973°N 5.9301°W / 54.5973; -5.9301贝尔法斯特(英语:Belfast /ˈbɛlfɑːst, -fæst/;爱尔兰语:Béal Feirste)位于爱尔兰岛东北沿海的
  • 霉气霉气,又称衰气,晦气,是东亚传统宗教(如道教、日本神道、朝鲜巫教、民间信仰等)的中心观念,是指令人不洁与沾上厄运的原因。血污、死亡、疾病与性交、喝酒、食肉也是令人不洁的原因
  • 高等教育局高等教育局(葡文:Direcção dos Serviços do Ensino Superior, DSES)是澳门特别行政区政府社会文化司负责辅助、跟进及发展澳门特别行政区的高等教育的政府部门。前身是1992
  • 井上芳雄井上芳雄(いのうえ よしお、1979年7月6日 - ),日本音乐剧及电视剧演员、歌手。现为グランアーツ旗下艺人。日本福冈县出身。东京艺术大学毕业。妹妹为前宝冢歌剧团花组初辉よし
  • 1939式52-K 85毫米高射炮1939式52-K 85毫米高射炮(俄语:85-мм зенитная пушка обр. 1939 г. (52-К))是苏联在二战使用的主流大中口径野战高射炮。其优良的内外弹道性能,使其发展
  • 哈伊尔·萨勒哈伊尔·萨勒(印度尼西亚语旧拼写法:Chaerul Saleh,新拼写法:Khairul Saleh)(1916年9月13日-1967年8月2日)通常简称萨勒,是已故印度尼西亚政治家,曾担任印尼多个部长之职,还曾任副总理
  • 非累赘取样编码以下将探讨两类非累赘取样编码法:多项式预测器及多项式内插法多项式预测器所采取的方法是:测试下一个取样看看他是不是落在一个n次多项市所展开的范围内。最常被使用的是0次及