组合数学第四章

1、第四章. Burnside引理与Polya定理,第一节群的概念,群G，运算：封闭，结合率，单位元，逆元。 交换群。 有限群G的阶G。 子群。,第二节置换群,n个元素的置换群的元素p= ，其 中a1, a2, , an是1，2，n的某个排列。交换两列看作同一元素。,置换群,乘法：设P1= , P2= ， P1P2= = ， P2P1= = 。 P1P2P2P1，因此置换群不是交换群。,置换群,逆元素：p= ，p-1=,例1,例1等边三角形三个顶点记为1,2,3,绕中心逆时针旋转120度,240度,沿三条中线翻转180度,三角形仍与自身重合,但顶点换了位置.这些变换分别记为P1= ， P2= ,P

2、3= ,P4= ,P5= , P6= . P1, P2, P3, P4, P5, P6构成一个 群。例如P2P4=P6.,第三节循环、奇循环与偶循环,记(a1a2am)= ,称为m阶循环。 例如 =(132), =(132)(45), =(154)(2)(3)=(154). 不相交的循环：两循环无公共元，如(132)和(45)。 不相交的循环乘积可交换，如(132)(45)=(45)(132)。,定理1,定理1任一置换可表示成若干不相交的循环之积，并且若不记次序，表示法唯一。 证明：对任一置换从1开始搜索1a1a2ak1，得到一个循环(1a1a2ak), 若它包含1到n的全部文字，则搜索停止，

3、否则在余下的文字中任取一开始搜索，如此下去，直到包含全部文字为止。 2阶循环(i, j)称为对换或换位。,定理2,定理2任一循环可表示成若干对换之积。 证明：(a1a2am)=(a1a2)(a1a3)(a1am)。 注：以上表示法不唯一。如(132)=(13)(12)=(13)(12)(13)(31)。但其奇偶性唯一。 若一个置换可分解成奇数个对换的乘积，则称为奇置换，否则称为偶置换。,例1,例1以下两表格不可能用相邻位置的与0对换互相转化。 证明：两个表格的转化相当于对换的乘积 (1 15)(2 14)(3 13)(4 12)(5 11)(6 10)(7 9)(8)(0)，这是一个奇置换。但

4、相邻位置的置换把0换回到原来位置必然经过偶数次对换。,定理3,定理3Sn的全体偶置换构成一个n!/2阶子群，记为An，称为交代群。 证明：偶置换一一对应于奇置换，并且满足群的条件。,第四节Burnside引理,讨论对称图形的着色问题。,一共轭类,Sn中任意置换p可分解为不相交的循环乘积p=(a1a2ak1)(b1b2bk2)(h1h2hkl), 其中k1+k2+kl=n. 设其中k阶循环出现的次数为ck, Sn中的置换可按格式(1)c_1(2)c_2(n)c_n的不同而分类. 如(1)(23)(4567)的格式为(1)1(2)1(3)0(4)1(5)0(6)0(7)0, (1234)(5)(6

5、7)有相同的格式,显然k=1nkck=n, Sn中有相同格式的置换全体称为与该格式相应的共轭类.,定理1,定理1Sn中属于(1)c_1(2)c_2(n)c_n共轭类的元素个数为 . 证明：(1)c_1(2)c_2(n)c_n的格式为()() () ()()(),一个置换可与一个排列对应,但有一定的重复度.,二k不动置换类,设G是1, 2, ,n的置换群,即G是Sn的子群.记G中使k不动的置换全体为Zk,则Zk是G的子群.例如G=e, (1 2), (3 4), (1 2)(3 4), 则Z1= Z2=e, (3 4) ,Z3= Z4=e, (1 2) . A4=e,(123),(124),(1

6、32),(134),(142),(143),(234), (243),(12)(34),(13)(24),(14)(23), Z1=e, (234), (243), Z2=e, (134), (143), Z3=e, (124), (142), Z4=e, (123), (132)。,三等价类,k在G下的轨道构成一个等价类(两个数在同一类中当且仅当它们两个相差G中元素的作用).记这个轨道中的全体数的集合为Ek,例如G=e, (1 2), (3 4), (1 2)(3 4), 则E1=E2=1,2, E3=E4=3,4.,定理2,定理2EkZk=G，k=1, 2, , n。 证明：设G=g1,

7、, gl, 则G=l=#g1(k), , gl(k), 但g1(k), ,gl(k)中有相同的元素,记其中不同的为g1(k),gm(k), ml, 从而Ek=g1(k), ,gm(k),Ek= m,设gp(k)的重复度是jp, 1pm, j1+jm=l, gp(k)=gq(k) 当且仅当gp-1 gq在Zk中.所以与gp(k)重复的数一一对应于Zk的元素，即jp=Zk,对所有p, 故EkZk=G。,四Burnside引理,设G=g1, , gl, 把gp分解为不相交的循环乘积，记c1(gp)为gp中1阶循环的个数，即gp:NN的不动点个数, 例如G=e, (1 2), (3 4), (1 2)

8、(3 4)，c1(e)=4, c1(1 2)=2, c1(3 4)=2, c1(1 2)(3 4)=0。,Burnside引理,Burnside引理：设G是N=1, 2, , n的置换群，G在N上的不同等价类的个数为 m= c1(g1)+ c1(g2)+ c1(gl)/ G。,Burnside引理,证明：对上面的G作如下表格,Burnside引理,若元素gi作用在整数j上使j不动，则在第i行第j列格子中填1，否则填0。这样第i行数字之和是c1(gi)，第j列数字之和是Zj。对所有格子中的数sij求和可以得到 i,jsij=,j=1ni=1l,sij =,j=1nZj =i=1l,j=1nsij

9、 =i=1l c1(gi)。,Burnside引理,若把N=1, 2, , n分解成m个不同的等价类，比如N= E1 E2 Em,两个数j和k属于同一等价类意味着Ej=Ek, 从而由定理2, Zj=Zk。故 i=1l c1(gi) =i=1lj=1nsij =j=1nZj=k=1mjEkZj =k=1mEkZk=mG。,例1,例1一个正方形分成4个小正方形格子，用两种颜色着色，如果经旋转能重合的方案算同一种，问能得到多少种不同的方案？,例1,解：每格有两种颜色，共有16种方案，如P321图，这16种方案分别记为c1, c2, , c16，当绕中心逆时针转动90度、180度、270度时得到另外一

10、种排列，可以看成是16种图像的置换。故群G有以下4个元素,例1,1 不动置换p1= (c1)(c2) (c16), 2 逆时针转动90度 p2=(c1)(c2)(c3c4c5c6)(c7c8c9c10)(c11c12)(c13c14c15c16), 3 逆时针转动180度 p3= (c1)(c2)(c3c5) (c4c6) (c7c9) (c8c10)(c11)(c12)(c13c15)(c14c16), 4 逆时针转动270度 p4= (c1)(c2) (c6c5 c4c3) (c10c9c8c7)(c11c12)(c16c15c14c13). 所以c1(p1) =16, c1(p2) =2

11、, c1(p3) =4, c1(p4) =2. 不同的等价类个数 m= c1(p1)+ c1(p2)+ c1(p3)+ c1(g4)/ G=6。共有6种不同的图像。,第五节Polya定理,主要用于研究m种颜色的不同着色方案的计数。 设有n个对象，G*是这n个对象上的置换群。现用m种颜色着色，每个对象涂一种颜色，问有多少种染色方案？一种方案在G*的作用下变成另一种，则这两种方案作为同一种看待。,定理(Polya),定理(Polya)设G*是n个对象上的置换群, 用m种颜色着色，不同的着色方案数为 ， 其中G*=a1*, ,ag*, c(a*k)表示置换ak*的循环节数。,定理(Polya),在上

12、一节的例1中，G*作用于着色前的4个对象上（4个小方格），G*的元素p1*= (1)(2)(3)(4)(不动元), p2*= (1234)(旋转90度), p3*= (13)(24)(旋转180度), p4*= (1432)(旋转270度)。若用两种颜色着色，由Polya定理，方案数l=(24+21+22+21)/4=6，与用Burnside引理的结果相同，但Burnside引理的G作用于着色后的16个对象上。,定理(Polya),Polya定理的证明：设n个对象用m种颜色着色所得的方案集合为S，则S=mn, G*中的元素ak*在n个对象上的置换对应了S中mn个着色方案的一个置换ak，把ak构

13、成的群记为G, 则G=G*。,定理(Polya),设a*是G*中的置换并且写成c(a*)个不相交的循环乘积a*=()()(), 若每个循环中的元素均涂以同样颜色，则在S中这种着色方案在aG (与a*对应)的作用下不变，即它属于a的不动点。,定理(Polya),另一方面，若a*的某个循环中有不同颜色，则必然有两个相邻元素着色不同，从而在a的作用下必然得到不同的着色方案。因此我们证明了a的作用下不变的着色方案数(或a的不动点数)c1(a)应等于对a*的每个循环涂以同样颜色的方案数mc(a), 带入Burnside引理即可。,第六节例子,例1等边三角形用红蓝绿对顶点着色，有几种方案？绕中心旋转及沿中

14、线翻转重合的算同一种方案。 解：G=(v1) (v2) (v3), (v1v2v3), (v1v3v2), (v1)(v2v3), (v2)(v1v3), (v3)(v1v2) v1 方案数 =(33+2*3+3*32)/6=10. V2 v3,例2,例2甲烷CH4, 若4个H键用H、Cl、CH3、C2H3取代， H 问有几种不同化学结构？ H C H H,例2,解：相当于用4种颜色对正四面体4个顶点着色，求方案数。使正4面体重合的刚体运动有3类：沿过顶点的中垂线旋转正负120度（共8个）；沿对棱的中点连线翻转180度（共3个）；不动变换。 V1 V2 V3 V4,例2,所以G=(v1)(v2

15、)(v3)(v4), (v1)(v2v3v4), (v1)(v2v4 v3), (v2)(v1v3v4), (v2)(v1v4v3), (v3)(v1v2v4), (v3)(v1v4v2), (v4)(v1v2v3), (v4)(v1v3v2), (v1v4)(v2v3), (v1v3)(v2v4), (v1v2)(v3v4)。 所以 =(44+11*42)/12=36.,例3,例3正六面体6个用红、蓝着色，有多少种方案？旋转重合的算同一种方案。 解：使正六面体重合的刚体运动有5类：绕对面中心连线旋转正负90度(共3*2种)；旋转180度(共3种)；绕对棱中点连线旋转180度(共6种)；绕对角

16、线旋转正负120度(共4*2种)；不动变换。,例3,以1, 2, 3, 4, 5, 6分别记正六面体的上, 下, 左, 右, 前, 后六个面, 则G=(1)(2)(3)(4)(5)(6), (1)(2)(3546)(类似的有6个),(1)(2)(34)(56)(类似的有3个),(12)(35)(46)(类似的有6个), (253)(164) (类似的有8个)。 所以 =(26+6*23+3*24+6*23+8*22)/24=10.,例4,例4用红、蓝两种颜色着色正六面体8个顶点，有多少种方案？旋转重合的算同一种方案。 1 4 2 3 5 8 6 7,例4,解：旋转运动同上，关于顶点的运动群为

17、G=(1)(2)(3)(4)(5)(6)(7)(8),(1234)(5678)(类似的有6个),(13)(24)(57)(68)(类似的有3个), (15)(26)(37)( 48)(类似的有6个),(183)(257)(4)(6) (类似的有8个)。所以 =(28+6*22+17*24)/24=23.,例5,例5骰子的六个面有1至6个点，有多少种不同方案？ 解：方法一，用Burnside引理。问题相当于对六个面用6种颜色着色，每个面颜色不同。这样的方案共6！种，记为s1, ,s6!, 六面体的变换群中，除单位元外，任何一个变换都没有不动点(即把某si变成si)，所以c1(e)=6!, c1(

18、a)=0, 若ae。由Burnside引理，不同的方案数l= c1(g1)+ c1(g2)+ c1(g24)/ G=30.,例5,方法二，用Polya定理+容斥原理 用m种颜色对六个面着色,不同的方案数记为nm,则nm=(m6+3m4+12m3+8m2)/24, n1=1, n2=10, n3=57, n4=240, n5=800, n6=2226.令li为用i种颜色对六个面着色,所得到的不少于i种颜色的方案数,则l1=n1=1, l2=n2-C(2,1)l1=10-2=8, l3= n3- C(3,2) l2-C(3,1) l1=30, l6= n6- C(6,5) l5- C(6,4) l

19、4-C(6,1) l1=30.,例6,例6在正六面体的每个面上作任意一条对角线,有多少种方案? 解：每个面有2种做法,六个面共26种方案,记为s1, ,s26。,例6,在六面体群的作用下，单位元有26个不动点;绕对面中心连线旋转正负90度无不动点;旋转180度有3*24个不动点(3对对面;上,下面各2种方案;前后方案相同,左右方案也相同,各有2种方案.由乘法原理);绕对棱中点连线旋转180度有6*23个不动点(共6对对棱;上下,前左,后右重合各2种);绕对角线旋转正负120度各有4*22个不动点(共4条对角线,下前左面重合,上后右面重合,各有2种方案).由Burnside引理,方案数 l =

20、c1(g1)+ c1(g2)+ c1(g24)/ G =(26+3*24+6*23+4*22+4*22)/24=8。,第七节母函数型的Polya定理,不仅可以计数，还可以列举状态。 例如，用b, g, r三色涂染3个相同的球，所有方案可以写成(b+g+r) (b+g+r) (b+g+r) =b3+g3+r3+3b2g+3b2r+3g2b+3g2r+3r2b+3r2g+6bgr.,母函数型的Polya定理,把以上方法用于Polya定理 设n个对象用m种颜色b1, b2, ,bm着色。在Polya定理中 一项来自于把aj表达为不相交的循环时，每个循环中的元素着同一种颜色（有m种选择）。,母函数型的

21、Polya定理,因而，若不仅要计数还要列举状态，则应该把其中的每个k阶循环代之以b1k+b2k+bmk, 所以 应该以 (b1+b2+bm)c_1(a_j)(b12+b22+bm2)c_2(a_j) (b1n+b2n+bmn)c_n(a_j)来取代。因而有 P=s1 c_1(a_1)s2 c_2(a_1)sn c_n(a_1)+ + s1 c_1(a_g)s2 c_2(a_g)sn c_n(a_g)/ G, 其中sk=b1k+b2k+bmk.,例1,例1由三种不同颜色的珠子，沿圆周装成四个珠子的项链，有哪些方案？ 解：G=(1)(2)(3)(4), (2)(4)(13), (1)(3)(24), (1234), (1432),(14)(23), (12)(34), (13)(24), 其格式为14一个,1221一个,22三个,41二个, 方案数l=(34+2*33+3*32+2*3)/8=21.,例1,具体方案为P=(b1+b2+b3)4+2(b1+b2+b3)2(b12+b22+b32)+3(b12+b22+b32)2+2(b14+b24+b34)/8, 其中b12b2b3的系数是2，即由2颗b1色、1颗b2色、1颗b3色的方案有2种。,例2,例2由