《组合数学课件-第四章第三节波利亚Polya定理.ppt》由会员分享，可在线阅读，更多相关《组合数学课件-第四章第三节波利亚Polya定理.ppt（33页珍藏版）》请在三一办公上搜索。
1、1,第4章 Burnside引理与Polya定理,4.1 群的概念 1 4.2 置换群 1 4.3 循环、奇循环与偶循环 1 4.4 Burnside引理 2 4.5 Polya 定理 3 4.6 举例 3 4.7 母函数形式的Polya定理*4.8 图的计数*4.9 Polya定理的若干推广*,2,4.5 波利亚(Polya)定理,Burnside引理.设G=a1,a2,.,ag,是N=1,2,.,n上的置换群,G在N上可引出不同的等价类,其不同的等价类的个数为：,在用Burnside引理解决染色方案数问题时，元素是染色方案数：,实例,3,4.5 波利亚(Polya)定理,p4=(c1)(c
2、2)(c6c5c4c3)(c10c9c8c7)(c11c12)(c16c15c14c13),p1=(c1)(c2)(c3)(c4)(c5)(c6)(c7)(c8)(c9)(c10)(c11)(c12)(c13)(c14)(c15)(c16),p2=(c1)(c2)(c3c4c5c6)(c7c8c9c10)(c11c12)(c13c14c15c16),p3=(c1)(c2)(c3c5)(c4c6)(c7c9)(c8c10)(c11)(c12)(c13c15)(c14c16),4,4.5 波利亚(Polya)定理,Burnside引理.设G=a1,a2,.,ag,是N=1,2,.,n上的置换群,G
3、在N上可引出不同的等价类,其不同的等价类的个数为：,在用Burnside引理解决染色方案数问题时，元素是染色方案数：,例如：对4个方格用两种颜色染色，方案数是16；,如果对6个方格用4种颜色进行染色，方案数是4096；,实例,5,4.5.1 例子,一个正方形分成四个格子,如图所示,用两种颜色对4个格子着色,问能得到多少种不同的图像?经过旋转能够吻合的,算是同一方案。,2,1,3,4,图4.5.1,当图按反时针方向旋转0度、90度,180度,270度时,得到4个元素的又一种排列,可以看作是4个元素的一种置换,(a)旋转0度为不动置换,(b)旋转90度时,1被4取代,2被1取代,3被2取代,4被3
4、取代,4.5 波利亚(Polya)定理,6,2,1,3,4,图4.9,(c)旋转180度时,1与3互换，2与4互换,(d)旋转270度时,4被1取代,1被2取代,2被3取代,3被4取代,这四种置换分别对应16种染色方案的四种置换。,4.5 波利亚(Polya)定理,7,四个元素的4种置换分别为：,这四个置换构成一个置换群，设这个群为,4个元素1,2,3,4用两种颜色进行染色，染色方案共有16种，这16种方案在旋转下也形成一个群G，,4.5 波利亚(Polya)定理,实例,8,对群 与G进行比较,(1),(2)对 中循环节数与G中的一阶循环个数进行比较：,用两种颜色进行染色：,24=16。,4.
5、5 波利亚(Polya)定理,9,4转换成3，3转换成2，2转换成1，1转换成4；,四个方格的颜色必须都相等，共有两种21；,1转换成3，3转换成1，2转换成4，4转换成2；,只要1和3的颜色相等，2和4的颜色相等，,共有4种22；,4.5 波利亚(Polya)定理,10,1转换成2，2转换成3，3转换成4，4转换成1；,四个方格的颜色必须都相等，共有两种21；,(1),(2)对 中循环节数与G中的一阶循环个数进行比较：,对群 与G进行比较,设 中循环节数为,4.5 波利亚(Polya)定理,11,对群 与G进行比较,(1),(2)对 中循环节数与G中的一阶循环个数进行比较：,设 中循环节数为
6、,12,4.5 波利亚定理,设有n个对象,是这n个对象的置换群,今用m种颜色涂染这n个对象,每个对象涂一种颜色,问有多少种染色方案?一种染色方案在群 的作用下变为另一种方案,则这两种方案当作是同一种方案。,定理4.12(Polya定理)设 是n个对象的一个置换群,用m种颜色涂染这n个对象,则不同染色的方案数为:,13,n个对象可用1,2,.,n编有序号,故 可当作(1,2,.,n)的一个置换群.,Polya定理中的 群是作用在n个对象上的置换群,Burnside定理中的G群是在这n个对象上用m种颜色进行染色后的方案集合上的置换群,是定义在n个文字上的置换群；,G是定义在mn个文字上的置换群。,
7、4.5 波利亚定理,14,定理的证明:,假定n个对象用m种颜色进行涂色所得的方案集合为S,显然,S=mn.,每一种变换对应于n个对象的一个置换,每一种变换也对应于mn个对象的一个置换,两个置换群是在同样的变化下得到的：,4.5 波利亚定理,15,对于每一种mn个对象的一个置换ai中的1阶循环,也就是染色方案在变换下还是自身，,对应着n个对象的一个置换 中每个循环节中涂同样染色的方案数,按Burnside引理，G分成不同的等价类的个数为：,4.5 波利亚定理,16,4.6 应用举例,例4.6.1 长为n的透明方格，用红、蓝、黄、绿4种颜色进行染色，试问有多少种不同的方案？,问题相当于用4种颜色构
8、成长为n的字符串，,如果从左向右看与从右向左看是一样的，则认为是一个。,倒过来能够重合的算一种方案。,17,问题相当于对n个元素用4种颜色染色，在群G作用下能变成一样的染色方案为一个方案，,群G有两个元素，也就是两个置换,只有一种变换：翻转,4.6 应用举例,18,如果n为偶数,如果n为奇数,循环节个数为,4.6 应用举例,19,循环节个数为,4.6 应用举例,20,例4.6.2 如图v1v2v3是圆圈上3点的等边三角形，用红、蓝、绿3种颜色的珠子镶上，试问有几种不同的方案？刚体运动吻合的算一种。,v1,v3,v2,这个问题相当于圆圈上三点v1v2v3用三种颜色的染色问题,构造G群,4.6 应
9、用举例,21,解(1)绕三角形中心旋转0度，120度，240度,(2)还以各点为基点翻转,v1,v3,v2,22,例4.6.3 对正四面体的4个顶点用4种颜色着色，求置换等价意义下的不同方案数。,解:构造G群,1、绕各面的中垂线旋转0度、120度和240度。,(v1)(v2)(v3)(v4),(v1)(v2v3v4),(v1)(v2v4v3),4.6 应用举例,23,2、绕过两对边的中点旋转180度。,(v1 v2)(v3v4),(v1 v3)(v2v4),(v1 v4)(v2v3),24,(v1)(v2)(v3)(v4),(v1)(v2v3v4),(v1)(v2v4v3),(v2)(v1v3
10、v4),(v2)(v1v4v3),(v3)(v1v2v4),(v3)(v1v4v2),(v4)(v1v2v3),(v4)(v1v3v2),(v1 v2)(v3v4),(v1 v3)(v2v4),(v1 v4)(v2v3),4.6 应用举例,25,例4.6.2 用*和对33的格子进行布子,试问有多少种不同的布局,旋转翻转重合的算一种方案?,关于中心旋转0度，90度,180度;,(1)(2)(3)(4)(5)(6)(7)(8)(9),4.6 应用举例,26,关于两条对角线翻转;,关于中间行或中间列翻转;,共8种置换,4.6 应用举例,27,(1)(2)(3)(4)(5)(6)(7)(8)(9),4
11、.6 应用举例,*,28,第一章:,总复习,1、一一对应的应用、排列、组合、圆周排列,2、排列的生成算法、组合的生成算法。,3、允许重复的重合、不相邻的组合。,4、路径数问题。,29,第二章:,总复习,1、母函数在组合中的应用 在整数的分拆中的应用,2、指数型母函数在排列中的应用。,3、递推关系,4、球放入盒中的放法,30,第三章:,总复习,1、容斥原理,2、棋盘多项式,3、有禁区的排列,4、广义的容斥原理,5、鸽巢原理,31,第四章:,总复习,1、置换群,2、Burnside引理,3、Polya定理,32,对一个正五边形的5个顶点用2种颜色染色，旋转反转能够重叠的算一种方案。问有多少种不同的方案？,课堂作业,33,4.5 波利亚(Polya)定理,C1,C2,C3,C4,C5,C6,C7,C8,C9,C10,C11,C12,C13,C14,C15,C16,返回,2,1,3,4,
