本文主要是介绍组合数学常用内容——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引理的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
