组合数学幻灯片64

1、24-24-2 26.46.4PolyaPolya定理定理BurnsideBurnside引理可用来解决诸如上节例引理可用来解决诸如上节例5 5这类问题，这类问题，即用即用m m种色对无标号物体着色的计数问题。然而当种色对无标号物体着色的计数问题。然而当m m较大较大时，计算量将大增，如对上节例时，计算量将大增，如对上节例5 5，若用，若用5 5种颜色着色，种颜色着色，则对应的图像将有则对应的图像将有5 53 3=125=125个，即个，即M M将有将有125125个元素。显然个元素。显然计算量很大。本节将介绍的计算量很大。本节将介绍的PlyaPlya计数定理，将计数定理，将大大减大大减少计算

2、量。少计算量。 24-24-3 3PlyaPlya定理可用着色模型来描述。定理可用着色模型来描述。设有设有n n个着色对象，用个着色对象，用m m种色对这种色对这n n个对象的一种着个对象的一种着色称为一种色称为一种着色方案着色方案。例如上节例。例如上节例5 5中若小三角形编号中若小三角形编号为为1 1、2 2、3(3(如图如图(a)(a)所示所示),),则则1 1、2 2、3 3为着色对象。为着色对象。1 1着着黑色，黑色，2 2与与3 3着白色着白色( (如图如图(b)(b)所示所示) )为一种着色方案。为一种着色方案。BurnBurnsideside引理所使用的群是作用在着色对象上的，对

3、象引理所使用的群是作用在着色对象上的，对象集比方案集小得多，且与颜色数无关。集比方案集小得多，且与颜色数无关。 24-24-4 4设设G是着色对象上的置换群。是着色对象上的置换群。若一种着色方案能由若一种着色方案能由另一着色方案通过另一着色方案通过G G中置换而中置换而导出，则称两着色方案在导出，则称两着色方案在本质上是相同的本质上是相同的。例如，图中例如，图中(b)(b)与与(c)(c)两个着色方案在本质上是相两个着色方案在本质上是相同的。这是因为同的。这是因为(c)(c)图所示的着色方案图所示的着色方案“2 2着黑，着黑，3 3与与1 1着着白色白色” ” 是是(b)(b)图所示的着色方案

4、图所示的着色方案“1 1着黑，着黑，2 2与与3 3着白色着白色”通过置换通过置换(123)(123)而得，该置换将而得，该置换将“1”1” 变为变为“2”2”，对应，对应的将的将“1 1着黑着黑”变为变为“2 2着黑着黑”。实际上，若考虑着色模。实际上，若考虑着色模型，则型，则BurnsideBurnside引理中述及的同一等价类中所有元素引理中述及的同一等价类中所有元素( (着色方案着色方案) )在本质上是相同的，而处于不同等价类中两在本质上是相同的，而处于不同等价类中两个着色方案在本质上是不同的，因而不同个着色方案在本质上是不同的，因而不同的等价类个数的等价类个数即为本质上不同的着色方案

5、数。即为本质上不同的着色方案数。24-24-5 5定理定理6 6.1616 设设N N是是n n个对象的集合，个对象的集合，G=G=1 1,2 2, ,k k是是N N上上的置换群，用的置换群，用m m种颜色对种颜色对n n个对象着色，则本质上不同的个对象着色，则本质上不同的着色方案数为着色方案数为mmm|G|1t)c()c()c(k21 其中其中c(c(i i) )为置换为置换i i中所含的不相交的循环的个数。中所含的不相交的循环的个数。24-24-6 6着色方案的集合。因一个方案含着色方案的集合。因一个方案含n n个对象，而每个对象均可着个对象，而每个对象均可着m m种种色，故色，故S S

6、=m=mn n。不妨设。不妨设S=S=x x1 1,x,x2 2, , , 并设并设x xi i=(x=(xi1i1,x,xi2i2, ,x,xinin) )，其中，其中x xijijBB，表示在着色方案，表示在着色方案x xi i中，对中，对象象1 1着着x xi1i1色，对象色，对象2 2着着x xi2i2色，色，对象，对象n n着着x xinin色，色，i=1,2,i=1,2,m,mn n。对任意的对任意的j jG,G,j j是是N N上的一个置换，上的一个置换，j j将将N N中的元中的元k k变变为为j jk k，同时对应地将每个，同时对应地将每个x xi i中的中的x xikik变

7、为变为x xijkijk，从而将，从而将x xi i变为变为S S中的中的某个元某个元y y，这表明，这表明j j诱导诱导出出了一个了一个S S上上的置换的置换j j，此，此j j将将x xi i变为变为y y，即，即y=y=j j(x(xi i) )。记记G G* *= =1 1,2 2, ,k k。证明：证明： 设设N=N=1,2,1,2,n,n为为n n个对象的集合，个对象的集合，B B为颜色的集合，为颜色的集合，S S为为nmx24-24-7 7证明证明(续续1)由由G G是群，易知是群，易知G G* *也是群且为也是群且为S S上的一个置换群。显然有上的一个置换群。显然有| |G G

8、* *|=|=G G=k=k同时，同时，j j(x(xi i) )是由是由x xi i经经G G中置换中置换j j导出的，故导出的，故x xi i与与j j(x(xi i) )是本质是本质上相同的着色方案。而上相同的着色方案。而j j(x(xi i) )j jGG* *,j=1,2,j=1,2,k,k正是正是S S由由G G* *导出的含导出的含x xi i的等价的等价类，所以类，所以S S中本质上不同的着色方案中本质上不同的着色方案个数即为个数即为S S中由中由G G* *导出的不同的等价类个数。导出的不同的等价类个数。设设(x(xi i) )为置换为置换j j中中1-1-循环，即在置换循环

9、，即在置换j j下着色方案下着色方案x xi i不变，不变，即即j j(x(xi i)=x)=xi i。而。而j j(x(xi i)=x)=xi i等价于等价于j j的每个循环中的含于同一的每个循环中的含于同一循环中的所有对象着同色的一种着色，这又可视为以循环循环中的所有对象着同色的一种着色，这又可视为以循环24-24-8 8证明证明(续续2)为为“点点”，对，对j j的的c(c(j j) )个个“点点”( (循环循环) )的一种着色，从而的一种着色，从而j j中的中的1-1-循环个数循环个数( (设为设为c c1 1(j j)等于用等于用m m种色对种色对j j的的c(c(j j) )个循环

10、的着个循环的着色数，即色数，即 )c(jm )c(j1jm)(c 由定理由定理6.156.15得得。)(c)(c)(c |G|1tk12111* mmm|G|1)c()c()c(k21 24-24-9 9注注用用PlyaPlya定理解题，首先应建立作用在定理解题，首先应建立作用在n n个对象上的个对象上的置换群。在建立置换群的过程中，若对允许的诸如旋转、置换群。在建立置换群的过程中，若对允许的诸如旋转、翻转等等变换找完，则相应的置换构成的集合翻转等等变换找完，则相应的置换构成的集合G G一定对一定对置换的乘法置换的乘法封闭，故能构成有限群封闭，故能构成有限群S Sn n(n(n次对称群次对称群

11、) )的子的子群。群。24-24-1010例例1 1 一个正方形被均分为四个小方格，如图一个正方形被均分为四个小方格，如图(a)(a)所示。所示。用三种色对其四个小方格用三种色对其四个小方格着色，求其不同的着色方案数。着色，求其不同的着色方案数。经旋转或翻转能使之重合的方案算一种。经旋转或翻转能使之重合的方案算一种。24-24-1111解：解：将正方形中的一些点及区域赋以相应的记号将正方形中的一些点及区域赋以相应的记号, ,如图如图(b)(b)所示所示, ,使正方形重合的运动及使正方形重合的运动及对应的集合对应的集合1,2,3,41,2,3,4上的置换有：上的置换有：1)1) 不动，对应的置换

12、不动，对应的置换1 1=(1)(2)(3)(4)=(1)(2)(3)(4)，格式为，格式为(1)(1)4 4，有有c(c(1 1)=4)=4。2)2) 绕中心绕中心0 0逆时针转逆时针转9090，180180，270270，记相应的置，记相应的置换为换为2 2,3 3,4 4，即，即2 2=(1432),=(1432),3 3=(13)(24),=(13)(24),4 4=(1234)=(1234)格式分别为格式分别为(4)(4)1 1,(2),(2)2 2,(4),(4)1 1，有，有c(c(2 2)=1,c()=1,c(3 3)=2,c()=2,c(4 4)=1)=1。24-24-1212

13、3)3)绕轴绕轴ACAC、DBDB、EGEG、FHFH翻转，相应的置换依次记为翻转，相应的置换依次记为5 5,6 6,7 7,8 8，即，即5 5=(2)(4)(13),=(2)(4)(13),6 6=(1)(3)(24),=(1)(3)(24),7 7=(12)(34),=(12)(34),8 8=(14)(23)=(14)(23)。5 5，6 6的格式为的格式为(1)(1)2 2(2)(2)1 1，有，有c(c(5 5)=c()=c(6 6)=3;)=3;7,87,8的格式为的格式为(2)(2)2 2，有，有c(c(7 7)=c()=c(8 8)=2)=2。由由(1)(1)、(2)(2)、

14、(3)(3)得置换群得置换群G=G=1 1,2 2, ,，8 8。又。又颜色数颜色数m=3,m=3,由由PlyaPlya定理得：着色方案数为定理得：着色方案数为218168)33333333(81m|G|1t22332481i)c(i 24-24-1313例例2 2 用红用红(r)(r)、蓝、蓝(b)(b)、绿、绿(g)(g)三种色对正三角形的顶点三种色对正三角形的顶点及其中心着色，如下图及其中心着色，如下图。求不同的着色方案数。经旋转。求不同的着色方案数。经旋转或翻转能使之重合的方案算一种。或翻转能使之重合的方案算一种。 24-24-1414解解： 1)1) 不动，对应的置换为不动，对应的置

15、换为(1)(2)(3)(4)(1)(2)(3)(4)，格式为，格式为(1)(1)4 4；2)2) 绕中心绕中心4 4旋转旋转120120，对应的两个置换为，对应的两个置换为(123)(4)(123)(4)，(132)(4)(132)(4)，格式均为，格式均为(1)(1)1 1(3)(3)1 1；3)3) 绕中线绕中线1414、2424、3434翻转，对应的置换有三个，为翻转，对应的置换有三个，为(1)(4)(23)(1)(4)(23)，(2)(4)(13)(2)(4)(13)，(3)(4)(12)(3)(4)(12)，格式均为格式均为(1)(1)2 2(2)(2)1 1；将图中的将图中的“”标

16、号如右图所示。标号如右图所示。使正三角形重合的运动及对应的使正三角形重合的运动及对应的1 1，2 2，3 3，4 4上的置换有：上的置换有： 24-24-1515解解(续续)共共6 6个置换，构成一个个置换，构成一个6 6阶置换群，由阶置换群，由PlyaPlya定理得着色定理得着色方案数为方案数为t= (3t= (34 4+2+23 32 2+3+33 33 3)/6)/6180/6180/63030其中中心着红色的着色方案见下图。其中中心着红色的着色方案见下图。24-24-1616例例3 3 在一个正四面体的若干顶点上嵌上三种颜色的珠子，在一个正四面体的若干顶点上嵌上三种颜色的珠子，同色珠子

17、均相同，可得多少同色珠子均相同，可得多少种不同样式的四面体。经适种不同样式的四面体。经适当转动能使之重合的样式算一种。当转动能使之重合的样式算一种。 24-24-1717解：解：1)1) 不动，对应的置换为不动，对应的置换为(1)(2)(3)(4)(1)(2)(3)(4)，格式为，格式为(1)4(1)4。问题相当于对一个正问题相当于对一个正四面体的四个顶点用四种四面体的四个顶点用四种颜色着染，求其本质上不颜色着染，求其本质上不同的着色方案数，如图同的着色方案数，如图610610所示，使正四面体重合的所示，使正四面体重合的刚体运动及相应的顶点集刚体运动及相应的顶点集1,2,3,41,2,3,4上

18、的置换有：上的置换有：24-24-1818解解( (续续) )2)2) 以顶点及相对的底面三角形中心的连线以顶点及相对的底面三角形中心的连线( (如图如图610610的的AB)AB)为轴旋转为轴旋转120120。因有四条轴可选，对应。因有四条轴可选，对应8 8个个格式相同的置换，其中一个为格式相同的置换，其中一个为(1)(234),(1)(234),格式为格式为(1)(1)1 1(3)(3)1 1；3)3) 以两条不相交的棱的中点的连线以两条不相交的棱的中点的连线( (如图如图610610中的中的CD)CD)为轴旋转为轴旋转180180。因有三条轴可选，对应。因有三条轴可选，对应3 3个格式相

19、个格式相同的置换，其中一个为同的置换，其中一个为(14)(23),(14)(23),格式为格式为(2)(2)2 2共共1212个置换，构成一个个置换，构成一个1212阶置换群，由阶置换群，由PlyaPlya定理得不定理得不同样式的四面体为同样式的四面体为t t (4(44 4+8+84 42 2+3+34 42 2)/12)/12432/12432/12363624-24-1919例例4 4 1)1) 若有若有m m种颜色可用，求本质不同的着色方案。种颜色可用，求本质不同的着色方案。2)2) 若有若有3 3种颜色可用且涂在立方体面上的颜色最多出种颜色可用且涂在立方体面上的颜色最多出现两种，求本

20、质不同的着色方案数现两种，求本质不同的着色方案数。给一立方体的六个面着色。若一种着色图形在空间给一立方体的六个面着色。若一种着色图形在空间经适当旋转可得另一着色图形，则说两着色是本质相同经适当旋转可得另一着色图形，则说两着色是本质相同的。的。24-24-2020解：解： 1)1) 给立方体六个面标号给立方体六个面标号, ,如右图如右图所示。使立方体重合的旋转所示。使立方体重合的旋转及相应的面集及相应的面集1 1，2 2，3 3，4 4，5 5，6 6上的置换有：上的置换有：a)a) 不动，对应的置换为不动，对应的置换为(1)(2)(3)(4)(5)(6)(1)(2)(3)(4)(5)(6)，格

21、式为，格式为(1)(1)6 624-24-2121解解(续续1)b)b) 以对面中心的连线以对面中心的连线为 轴 转为 轴 转 9 09 0 ，180180，其中关于，其中关于ABAB轴轴( (如右图如右图) )对应的对应的置换为置换为(1)(2)(3456)(1)(2)(3456)，(1)(2)(3654)(1)(2)(3654)，(1)(2)(35)(46)(1)(2)(35)(46)因有三组对面可选，故此类置换共因有三组对面可选，故此类置换共9 9个，其中个，其中6 6个格个格式为式为(1)(1)2 2(4)(4)1 1，3 3个格式为个格式为(1)(1)2 2(2)(2)2 2。24-24-2222解解(续续2)共共2424个置换，构成一个个置换，构成一个2424阶群。由阶群。由PlyaPlya定理得着色方定