本文主要是介绍组合数学常用内容——Polya定理+Burnside引理,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Burnside引理
设G是N{1,2,.....,n}上的置换群,G在N上可引出不同的等价类(在置换群中有置换的都等价),其不同的等价类的个数为LL=1/|G|*(c1(a1)+...c1(ai)...+c1(ag))c1表示置换ai作用过后不变的方案数,也就是置换中循环节长度是1的循环个数(N中的元素是组合方案的序号不是自然数!此置换群是关于所有着色图像(所有可能的情况)集合N的置换)Burnside应用关键:如何构造置换群(图形上来说一般为根据中心点,对称轴进行旋转和翻转)缺陷:置换是作用在所有方案上的,如果颜色数量过多,方案随之剧增,Burnside无能为力;
Polya定理
设G是n个对象的一个置换群(此置换群是关于所有被着色对象集合的置换),用m种颜色对这n个对象进行着色,则不同的染色方案数为ll=1/|G|*(m^c(a1)+...m^c(ai)+...m^c(an)) c表示ai置换的循环节数量当着色方案有具体限制条件时一般用Burnside引理而不用Polya定理
Polya定理的母函数形式
设N是n个对象的集合,G是N上的置换群,G={P1,P2,...,Pg},用m种颜色b1,b2,...bm对n个对象进行着色设Ck(P)为置换P中k循环,令Sk=b1^k+b2^k+...+bm^k,k=1,2,...n(Sk为每种颜色允许出现k次),则具体着色方案数的多项式为:P=1/|G|*∑(Pi∈G)(S1^c1(Pi)*S2^c2(Pi)*...*Sn^cn(Pi))展开并合并同类项之后,b1^i1*b2^i2*...*bm^im前的系数即为具体着色方案数。
常用多面体的置换群
正四面体(顶点数:4,棱数:6)
1、以顶点为目标的转动群:以顶点—面心为轴:(1)1 (3)1 8个置换群;以棱中—棱中为轴:(2)2 3个置换群;不动:(1)4 1个置换群;2、以棱为目标的转动群:以顶点—面心为轴:(3)2 8个置换群;以棱中—棱中为轴:(1)2 (2)2 3个置换群;不动:(1)6 1个置换群;3、以面为目标的转动群:以顶点—面心为轴:(1)1 (3)1 8个置换群;以棱中—棱中为轴:(2)2 3个置换群;不动:(1)4 1个置换群;
正六面体(顶点数:8,棱数:12)
1、以顶点为目标的转动群:以顶点—顶点为轴:(1)2 (3)2 8个置换群;以棱中—棱中为轴:(2)4 6个置换群;以面心—面心为轴:(4)2 6个置换群;(2)4 3个置换群;不动:(1)8 1个置换群;2、以棱为目标的转动群:以顶点—顶点为轴:(3)4 8个置换群;以棱中—棱中为轴:(1)2 (2)5 6个置换群;以面心—面心为轴:(4)3 6个置换群;(2)6 3个置换群;不动:(1)12 1个置换群;3、以面为目标的转动群:以顶点—顶点为轴:(3)2 8个置换群;以棱中—棱中为轴:(2)3 6个置换群;以面心—面心为轴:(1)2 (4)1 6个置换群;(1)2 (2)2 3个置换群;不动:(1)6 1个置换群;
正八面体(顶点数:6,棱数:12)
1、以顶点为目标的转动群:以顶点—
这篇关于组合数学常用内容——Polya定理+Burnside引理的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!