组合数学四PPT课件

.,1,第四章.Burnside引理与Polya定理,.,2,第一节群的概念,群G，运算：封闭，结合率，单位元，逆元。交换群。有限群G的阶G。子群。,.,3,第二节置换群,n个元素的置换群的元素p=，其中a1,a2,an是1，2，n的某个排列。交换两列看作同一元素。,.,4,置换群,乘法：设P1=,P2=，P1P2=，P2P1=。P1P2P2P1，因此置换群不是交换群。,.,5,置换群,逆元素：p=，p-1=,.,6,例1,例1等边三角形三个顶点记为1,2,3,绕中心逆时针旋转120度,240度,沿三条中线翻转180度,三角形仍与自身重合,但顶点换了位置.这些变换分别记为P1=，P2=,P3=,P4=,P5=,P6=.P1,P2,P3,P4,P5,P6构成一个群。例如P2P4=P6.,.,7,第三节循环、奇循环与偶循环,记(a1a2am)=,称为m阶循环。例如=(132),=(132)(45),=(154)(2)(3)=(154).不相交的循环：两循环无公共元，如(132)和(45)。不相交的循环乘积可交换，如(132)(45)=(45)(132)。,.,8,定理1,定理1任一置换可表示成若干不相交的循环之积，并且若不记次序，表示法唯一。证明：对任一置换从1开始搜索1a1a2ak1，得到一个循环(1a1a2ak),若它包含1到n的全部文字，则搜索停止，否则在余下的文字中任取一开始搜索，如此下去，直到包含全部文字为止。2阶循环(i,j)称为对换或换位。,.,9,定理2,定理2任一循环可表示成若干对换之积。证明：(a1a2am)=(a1a2)(a1a3)(a1am)。注：以上表示法不唯一。如(132)=(13)(12)=(13)(12)(13)(31)。但其奇偶性唯一。若一个置换可分解成奇数个对换的乘积，则称为奇置换，否则称为偶置换。,.,10,例1,例1以下两表格不可能用相邻位置的与0对换互相转化。证明：两个表格的转化相当于对换的乘积(115)(214)(313)(412)(511)(610)(79)(8)(0)，这是一个奇置换。但相邻位置的置换把0换回到原来位置必然经过偶数次对换。,.,11,定理3,定理3Sn的全体偶置换构成一个n!/2阶子群，记为An，称为交代群。证明：偶置换一一对应于奇置换，并且满足群的条件。,.,12,第四节Burnside引理,讨论对称图形的着色问题。,.,13,一共轭类,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)(67)有相同的格式,显然k=1nkck=n,Sn中有相同格式的置换全体称为与该格式相应的共轭类.,.,14,定理1,定理1Sn中属于(1)c_1(2)c_2(n)c_n共轭类的元素个数为.证明：(1)c_1(2)c_2(n)c_n的格式为()()()()()(),一个置换可与一个排列对应,但有一定的重复度.,.,15,二k不动置换类,设G是1,2,n的置换群,即G是Sn的子群.记G中使k不动的置换全体为Zk,则Zk是G的子群.例如G=e,(12),(34),(12)(34),则Z1=Z2=e,(34),Z3=Z4=e,(12).A4=e,(123),(124),(132),(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)。,.,16,三等价类,k在G下的轨道构成一个等价类(两个数在同一类中当且仅当它们两个相差G中元素的作用).记这个轨道中的全体数的集合为Ek,例如G=e,(12),(34),(12)(34),则E1=E2=1,2,E3=E4=3,4.,.,17,定理2,定理2EkZk=G，k=1,2,n。证明：设G=g1,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-1gq在Zk中.所以与gp(k)重复的数一一对应于Zk的元素，即jp=Zk,对所有p,故EkZk=G。,.,18,四Burnside引理,设G=g1,gl,把gp分解为不相交的循环乘积，记c1(gp)为gp中1阶循环的个数，即gp:NN的不动点个数,例如G=e,(12),(34),(12)(34)，c1(e)=4,c1(12)=2,c1(34)=2,c1(12)(34)=0。,.,19,Burnside引理,Burnside引理：设G是N=1,2,n的置换群，G在N上的不同等价类的个数为m=c1(g1)+c1(g2)+c1(gl)/G。,.,20,Burnside引理,证明：对上面的G作如下表格,.,21,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=i=1lc1(gi)。,.,22,Burnside引理,若把N=1,2,n分解成m个不同的等价类，比如N=E1E2Em,两个数j和k属于同一等价类意味着Ej=Ek,从而由定理2,Zj=Zk。故i=1lc1(gi)=i=1lj=1nsij=j=1nZj=k=1mjEkZj=k=1mEkZk=mG。,.,23,例1,例1一个正方形分成4个小正方形格子，用两种颜色着色，如果经旋转能重合的方案算同一种，问能得到多少种不同的方案？,.,24,例1,解：每格有两种颜色，共有16种方案，如P321图，这16种方案分别记为c1,c2,c16，当绕中心逆时针转动90度、180度、270度时得到另外一种排列，可以看成是16种图像的置换。故群G有以下4个元素,.,25,例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)(c6c5c4c3)(c10c9c8c7)(c11c12)(c16c15c14c13).所以c1(p1)=16,c1(p2)=2,c1(p3)=4,c1(p4)=2.不同的等价类个数m=c1(p1)+c1(p2)+c1(p3)+c1(g4)/G=6。共有6种不同的图像。,.,26,第五节Polya定理,主要用于研究m种颜色的不同着色方案的计数。设有n个对象，G*是这n个对象上的置换群。现用m种颜色着色，每个对象涂一种颜色，问有多少种染色方案？一种方案在G*的作用下变成另一种，则这两种方案作为同一种看待。,.,27,定理(Polya),定理(Polya)设G*是n个对象上的置换群,用m种颜色着色，不同的着色方案数为，其中G*=a1*,ag*,c(a*k)表示置换ak*的循环节数。,.,28,定理(Polya),在上一节的例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个对象上。,.,29,定理(Polya),Polya定理的证明：设n个对象用m种颜色着色所得的方案集合为S，则S=mn,G*中的元素ak*在n个对象上的置换对应了S中mn个着色方案的一个置换ak，把ak构成的群记为G,则G=G*。,.,30,定理(Polya),设a*是G*中的置换并且写成c(a*)个不相交的循环乘积a*=()()(),若每个循环中的元素均涂以同样颜色，则在S中这种着色方案在aG(与a*对应)的作用下不变，即它属于a的不动点。,.,31,定理(Polya),另一方面，若a*的某个循环中有不同颜色，则必然有两个相邻元素着色不同，从而在a的作用下必然得到不同的着色方案。因此我们证明了a的作用下不变的着色方案数(或a的不动点数)c1(a)应等于对a*的每个循环涂以同样颜色的方案数mc(a),带入Burnside引理即可。,.,32,第六节例子,例1等边三角形用红蓝绿对顶点着色，有几种方案？绕中心旋转及沿中线翻转重合的算同一种方案。解：G=(v1)(v2)(v3),(v1v2v3),(v1v3v2),(v1)(v2v3),(v2)(v1v3),(v3)(v1v2)v1方案数=(33+2*3+3*32)/6=10.V2v3,.,33,例2,例2甲烷CH4,若4个H键用H、Cl、CH3、C2H3取代，H问有几种不同化学结构？HCHH,.,34,例2,解：相当于用4种颜色对正四面体4个顶点着色，求方案数。使正4面体重合的刚体运动有3类：沿过顶点的中垂线旋转正负120度（共8个）；沿对棱的中点连线翻转180度（共3个）；不动变换。V1V2V3V4,.,35,例2,所以G=(v1)(v2)(v3)(v4),(v1)(v2v3v4),(v1)(v2v4v3),(v2)(v1v3v4),(v2)(v1v4v3),(v3)(v1v2v4),(v3)(v1v4v2),(v4)(v1v2v3),(v4)(v1v3v2),(v1v4)(v2v3),(v1v3)(v2v4),(v1v2)(v3v4)。所以=(44+11*42)/12=36.,.,36,例3,例3正六面体6个用红、蓝着色，有多少种方案？旋转重合的算同一种方案。解：使正六面体重合的刚体运动有5类：绕对面中心连线旋转正负90度(共3*2种)；旋转180度(共3种)；绕对棱中点连线旋转180度(共6种)；绕对角线旋转正负120度(共4*2种)；不动变换。,.,37,例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.,.,38,例4,例4用红、蓝两种颜色着色正六面体8个顶点，有多少种方案？旋转重合的算同一种方案。14235867,.,39,例4,解：旋转运动同上，关于顶点的运动群为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.,.,40,例5,例5骰子的六个面有1至6个点，有多少种不同方案？解：方法一，用Burnside引理。问题相当于对六个面用6种颜色着色，每个面颜色不同。这样的方案共6！种，记为s1,s6!,六面体的变换群中，除单位元外，任何一个变换都没有不动点(即把某si变成si)，所以c1(e)=6!,c1(a)=0,若ae。由Burnside引理，不同的方案数l=c1(g1)+c1(g2)+c1(g24)/G=30.,.,41,例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)l4-C(6,1)l1=30.,.,42,例6,例6在正六面体的每个面上作任意一条对角线,有多少种方案?解：每个面有2种做法,六个面共26种方案,记为s1,s26。,.,43,例6,在六面体群的作用下，单位元有26个不动点;绕对面中心连线旋转正负90度无不动点;旋转180度有3*24个不动点(3对对面;上,下面各2种方案;前后方案相同,左右方案也相同,各有2种方案.由乘法原理);绕对棱中点连线旋转180度有6*23个不动点(共6对对棱;上下,前左,后右重合各2种);绕对角线旋转正负120度各有4*22个不动点(共4条对角线,下前左面重合,上后右面重合,各有2种方案).由Burnside引理,方案数l=c1(g1)+c1(g2)+c1(g24)/G=(26+3*24+6*23+4*22+4*22)/24=8。,.,44,第七节母函数型的Polya定理,不仅可以计数，还可以列举状态。例如，用b,g,r三色涂染3个相同的球，所有方案可以写成(b+g+r)(b+g+r)(b+g+r)=b3+g3+r3+3b2g+3b2r+3g2b+3g2r+3r2b+3r2g+6bgr.,.,45,母函数型的Polya定理,把以上方法用于Polya定理设n个对象用m种颜色b1,b2,bm着色。在Polya定理中一项来自于把aj表达为不相交的循环时，每个循环中的元素着同一种颜色（有m种选择）。,.,46,母函数型的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=s1c_1(a_1)s2c_2(a_1)snc_n(a_1)+s1c_1(a_g)s2c_2(a_g)snc_n(a_g)/G,其中sk=b1k+b2k+bmk.,.,47,例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.,.,48,例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种。,.,49,例2,