资源描述：
《组合数学课件--第四章第三节 波利亚polya定理》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第4章Burnside引理与Polya定理4.1群的概念14.2置换群14.3循环、奇循环与偶循环14.4Burnside引理24.5Polya定理34.6举例34.7母函数形式的Polya定理*4.8图的计数*4.9Polya定理的若干推广*14.5波利亚(Polya)定理Burnside引理.设G={a1,a2,...,ag},是N={1,2,...,n}上的置换群,G在N上可引出不同的等价类,其不同的等价类的个数为：在用Burnside引理解决染色方案数问题时，元素是染色方案数：实例24.5波利亚(Polya)定理p4=(c1)(c2)(c6c5c4
2、c3)(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)34.5波利亚(Polya)定理Burnside引理.设G={a1,a2,...,ag},是N={1,2,..
3、.,n}上的置换群,G在N上可引出不同的等价类,其不同的等价类的个数为：在用Burnside引理解决染色方案数问题时，元素是染色方案数：例如：对4个方格用两种颜色染色，方案数是16；如果对6个方格用4种颜色进行染色，方案数是4096；实例44.5.1例子,一个正方形分成四个格子,如图所示,用两种颜色对4个格子着色,问能得到多少种不同的图像?经过旋转能够吻合的,算是同一方案。2134图4.5.1当图按反时针方向旋转0度、90度,180度,270度时,得到4个元素的又一种排列,可以看作是4个元素的一种置换,(a)旋转0度为不动置换(b)旋转90度时,1被4取代
4、,2被1取代,3被2取代,4被3取代,4.5波利亚(Polya)定理52134图4.9(c)旋转180度时,1与3互换，2与4互换(d)旋转270度时,4被1取代,1被2取代,2被3取代,3被4取代,这四种置换分别对应16种染色方案的四种置换。4.5波利亚(Polya)定理6四个元素的4种置换分别为：这四个置换构成一个置换群，设这个群为4个元素1,2,3,4用两种颜色进行染色，染色方案共有16种，这16种方案在旋转下也形成一个群G，4.5波利亚(Polya)定理实例7对群与G进行比较(1)(2)对中循环节数与G中的一阶循环个数进行比较：用两种颜色进行染色：
5、24=16。4.5波利亚(Polya)定理84转换成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)定理91转换成2，2转换成3，3转换成4，4转换成1；四个方格的颜色必须都相等，共有两种21；(1)(2)对中循环节数与G中的一阶循环个数进行比较：对群与G进行比较设中循环节数为4.5波利亚(Polya)定理10对群与G进行比较(1)(2)对中循环节数与G中的一阶循环个数进行比较：设中循环节数为11
6、4.5波利亚定理设有n个对象,是这n个对象的置换群,今用m种颜色涂染这n个对象,每个对象涂一种颜色,问有多少种染色方案?一种染色方案在群的作用下变为另一种方案,则这两种方案当作是同一种方案。定理4.12(Polya定理)设是n个对象的一个置换群,用m种颜色涂染这n个对象,则不同染色的方案数为:12n个对象可用1,2,...,n编有序号,故可当作(1,2,...,n)的一个置换群.Polya定理中的群是作用在n个对象上的置换群,Burnside定理中的G群是在这n个对象上用m种颜色进行染色后的方案集合上的置换群,是定义在n个文字上的置换群；G是定义在mn个文
7、字上的置换群。4.5波利亚定理13定理的证明:假定n个对象用m种颜色进行涂色所得的方案集合为S,显然,S=mn.每一种变换对应于n个对象的一个置换每一种变换也对应于mn个对象的一个置换两个置换群是在同样的变化下得到的：4.5波利亚定理14对于每一种mn个对象的一个置换ai中的1阶循环也就是染色方案在变换下还是自身，对应着n个对象的一个置换中每个循环节中涂同样染色的方案数按Burnside引理，G分成不同的等价类的个数为：4.5波利亚定理154.6应用举例例4.6.1长为n的透明方格，用红、蓝、黄、绿4种颜色进行染色，试问有多少种不同的方案？问题相当于用
8、4种颜色构成长为n的字符串，如果从左向右看与从右向左看是一样的，则
