资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章 Plya定理,群的概念,置换群,循环、奇循环与偶循环,Burnside,引理,Plya,定理,例,母函数型的,Plya,定理,图的计数,4.1 群的概念,(1),群,定义,给定集合,G,和,G,上的二元运算,,满足下列条件称为群。,(,a),封闭性:,若,a,bG,则存在,cG,使得,a,b=c.,(b),结合律成立:,任意,a,b,cG,有(,a,b),c=a,(b,c).,(,c),有单位元:,存在,eG,任意,aG.a,e=e,a=a.,(d),有逆元:,任意,aG,存在,bG,a,b=b,a=e.b=a.,由于结合律成立,,(,a,b),c=a,(,b,c),可记做,a,b,c.,例,证明对于,a,1,a,2,a,n,的乘积,结合律成立.,a,a,a=a (,共,n,个,a,相乘).,-1,n,4.1 群的概念,(2)简单例子,例,G=1,-1,在普通乘法下是群。,例,G=0,1,2,n-1,在,mod n,的加法下是群.,例,二维欧氏空间所有刚体旋转,T=T,a,构成群。其中,T,a,=cos,a,sin,a,-sin,a,cos,a,T,b,T,a,=,cos,b,sin,b,cos,a,sin,a,-sin,b,cos,b,-sin,a,cos,a,4.1 群的概念,=,cos,a,cos,b,-sin,a,sin,b,sin,a,cos,b,+cos,a,sin,b,-sin,a,cos,b,-cos,a,sin,b,cos,a,cos,b,-sin,a,sin,b,=cos(,a,+,b,)sin(,a,+,b,)=T,a,+,b,-sin(,a,+,b,)cos(,a,+,b,),从而有,(,a),封闭性;,(b),结合律成立:,(,T,T,)T,=T,(T,T,)=,T,T,T,;,(,c),有单位元:,T,0,=;,(d),有逆元:,T,a,=T,-a,=,cos,a,-sin,a,sin,a,cos,a,1 0,0 1,4.1 群的概念,基本性质,单位元唯一,e,1,e,2,=e,2,=e,1,消去律成立,ab,=ac b=c,ba,=ca b=c,每个元的逆元唯一,aa,=a a=e,ab,=,ba,=e,aa,=,ab,a =b,(d)(,ab,.c)=c b a.,c b a,ab,c=e,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,4.1 群的概念,(,e)G,有限,,aG,,则存在最小正整数,r,,使得,a =e.,且,a =a .,证,设|,G|=g,则,a,a,a ,a G,由鸽巢原理其中必有相同项。设,a =a ,1m,l,g+1,e=a ,1,l,-mg,,令,l,-m=r.,则有,a=a a=e.,即,a =a .,既然有正整数,r,使得,a =e,其中必有最小者,不妨仍设为,r.r,称为,a,的阶。易见,H=a,a,a ,a =e,在原有运算下也是一个群。,r,-1,r-1,2,g,g+1,m,l,l,-m,r,r-1,r-1,-1,r,2,r-1,r,4.2 置换群,置换群是最重要的有限群,所有的有限群都可以用之表示。,置换:1,n,到自身的1-1变换。,n,阶置换。1,n,目标集。(),a,1,a,2,a,n,是1,n,中元的一个排列。,n,阶置换共有,n!,个,同一置换用这样的表示可有,n!,个表示法。例如,p,1,=()=(),n,阶置换又可看作1,n,上的一元运算,一元函数。,1 2,n,a,1,a,2,a,n,1 2 3 4,3 1 2 4,3 1 4 2,2 3 4 1,4.2 置换群,(1)置换群 1,n上的所有n阶置换在上面的乘法定义下是一个群。(a)封闭性 ()()=()(b)可结合性()()()=()=()()()(c)有单位元 e=()(d)()=(),1 2,n,a,1,a,2,a,n,a,1,a,2,a,n,b,1,b,2,b,n,1 2,n,b,1,b,2,b,n,1 2,n,a,1,a,2,a,n,a,1,a,2,a,n,b,1,b,2,b,n,1 2,n,a,1,a,2,a,n,a,1,a,2,a,n,b,1,b,2,b,n,1 2,n,c,1,c,2,c,n,b,1,b,2,b,n,c,1,c,2,c,n,b,1,b,2,b,n,c,1,c,2,c,n,1 2,n,1 2 n,1 2,n,a,1,a,2,a,n,a,1,a,2,a,n,1 2,n,-1,4.2 置换群,(2)例 等边三角形的运动群。绕中心转动120,不动,绕对称轴翻转。,P,1,=(),P,2,=(),P,3,=(),P,4,=(),P,5,=(),P,6,=()。1,n,上的所有置换(共,n!,个)构成一个群,称为对称群,记做,S,n,.,注意:一般说1,n,上的一个置换群,不一定是指,S,n,.,但一定是,S,n,的某一个子群。,1 2 3,1 2 3,1 2 3,2 3 1,1 2 3,3 1 2,1 2 3,1 3 2,1 2 3,3 2 1,1 2 3,2 1 3,1,2 3,4.3循环、奇循环与偶循环,(,a,1,a,2,a,m,)=,(,),称为置换的循环表示。,于是,(,),=(14523),(,),=(132)(45),(,),=(154)(2)(3).,(,a,1,a,2,a,m,)=,(,a,2,a,3,a,m,a,1,)=,(,a,m,a,1,a,m,-,1,),有,m,种表示方法。,a,1,a,2,a,m-1,a,m,a,2,a,3,a,m,a,1,12345,43152,12345,31254,12345,52314,4.3循环、奇循环与偶循环,了1,n,的所有文字,则命题成立。否则在余下的文字中选一个,继续搜索,又得一循环。直到所有文字都属于某一循环为止。,因不相交循环可交换,故除了各个循环的顺序外,任一置换都有唯一的循环表示。,例,一副扑克牌,一分为二,交错互相插入(洗牌),这样操作一次相当于一个置换,p。,i =,p,(i+1)/2,i=1,3,5,51.,i/2+26,i=2,4,6,52.,p=(),第,i,个位置,被,i,号牌占据.,p,i,p,p,4.3循环、奇循环与偶循环,26,.,.,.,5 3,3 2,1 1,52 52,.,.,.,29 6,28 4,27 2,p=,(2 27 14 33 17 9 5 3)(4 28 40 46 49 25 13 7),(6 29 15 8 30 41 21 11)(10 31 16 34 43 22 37 19),(12 32 42 47 24 38 45 23)(18 35),(20 36 44 48 50 51 26 39)(52),p =e,2,阶循环叫做对换。,8,4.3循环、奇循环与偶循环,例 0表示空格,任一变动都是与0做相邻的对换。,p=(0)(1 15)(2 14)(3 13)(4 12)(5 11)(6 10)(7 9)(8),奇置换。0从右下角出发回到右下角,水平方向上,垂直方向上都做了偶数次对换。一个奇置换不会等于一个偶置换。,1 2 3 4,5 6 7 8,9 10 11 12,13 14 15 0,15 14 13 12,11 10 9 8,7 6 5 4,3 2 1 0,4.3循环、奇循环与偶循环,定理,Sn,中所有偶置换构成一阶为(,n!)/2,的子群称为交错群,记做,An.,证,(1)封闭性 (2)单位元 (3)逆元(,i k)=(i k),设,p=(i,1,j,1,)(i,2,j,2,)(i,i,j,i,),则,p =(i,i,j,i,)(i,1,j,1,),令,Bn=Sn-An,|Bn|+|An|=n!,则(,i j)Bn,包含于,An|Bn|An|,,(,i j)Bn,包含于,An|An|Bn|An|=|Bn|=(n!)/2,-1,4.4,Burnside,引理,(1)共轭类 先观察,S,3,A,3,S,4,A,4,以增加感性认识。,S,3,=(1)(2)(3),(23),(13),(123)(132).A,3,=(1)(2)(3),(123),(132).S,4,=(1)(2)(3)(4),(12),(13),(14),(23),(24),(34),(123),(124),(132),(134),(142),(143),(234),(243),(1234),(1243),(1324),(1342),(1423),(1432),(12)(34),(13)(24),(14)(23).A4=(1)(2)(3)(4),(123),(124),(132),(134),(142),(143),(234),(243),(12)(34),(13)(24),(14)(23).,4.4,Burnside,引理,Sn,中,P,的循环格式(1)(2)(,n),kC,k,=,n,Sn,中有相同格式的置换全体构成一个共轭类。,定理1,Sn,中属(1)(2)(,n),共轭类的元的个数为,C,1,C,2,C,n,n,k=1,C,1,C,2,C,n,n!,C,1,!C,2,!C,n,!1 2 n,C,1,C,2,C,n,4.4,Burnside,引理,证(1)(2)(n)即,C,1,C,2,C,n,()()()()()(),_,/,1个,_,/,2个,_,/,n个,_ _/,/,C,1,个,_ _/,/,C,2,个,_ _/,/,C,n,个,一个长度为,k,的循环有,k,种表示,,C,k,个长,度为,k,的循环有,C,k,!k,种表示.1,2,n,的全,排列共有,n!,个,给定一个排列,装入格式,得一置换,除以前面的重复度得,n!/(C,1,!C,2,!C,n,!1 2 n ),个不同的置换.,C,k,C,1,C,2,C,n,4.4,Burnside,引理,定理 置换群,G,的,k,不动置换类,Z,k,是,G,的一个子群。封闭性:,kkk,kk.,结合性:自然。有单位元:,G,的单位元属于,Z,k,.,有逆元:,PZ,k,kk,则,kk,PZ,k,.Z,k,G.,P,1,P,2,P,1,P,2,P,P,-1,4.4,Burnside,引理,(3)等价类举一个例子。,G=(1)(2)(3)(4),(12),(34),(12)(34).,在,G,下,1变2,3变4,但1不变3。,Z,1,=Z,2,=e,(34),Z,3,=Z,4,=e,(12).,对于,A,4,Z,1,=e,(234),(243),Z,2,=e,(134),(143)Z,3,=e,(124),(142),Z,4,=e,(123),(132),一般1,n,上,G,将1,n,分成若干等价类,满足等价类的3个条件.(,a),自反性;(,b),对称性;(,c),传递性。,4.4,Burnside,引理,一个由G定义的关系k:若存在pG,使得kj则称kRj.显然kRk;kRj则jRk;kRj,jRl则kRl。R是1,n上的一个等价关系。将1,n划分成若干等价类。,含目标集元素k的在G作用下的等价类也称为含k的轨道。,p,4.4,Burnside,引理,(4),Burnside,引理 设,G=a,1,a,2,a,g,是目标集1,n,上的置换群。每个置换都写成不相交循环的乘积。,G,将1,n,换分成,l,个等价类。,c,1,a,k,是在置换,a,k,的作用下不动点的个数,也就是长度为1的循环的个数。,Burnside,引理,l,=c,1,(a,1,)+c,1,(a,2,)+c,1,(a,g,)/|G|,4.4,Burnside,引理,例如,,G=e,(12),(34),(12)(34).,c,1,(a,1,)=4,c,1,(a,2,)=2,c,1,(a,3,)=2,c,1,(a,4,)=0.,l,=4+2+2+0/4=2.,以本例列表分析:,1 2 3 4,c,1,(a,j,),(1)(2)(3)(4)1 1 1 1 4 (1),(12)(3)(4)0 0 1 1 2 (1)(2),(1)(2)(34)1 1 0 0 2 (1)(2),(12)(34)0 0 0 0 0 (2),|,Z,k,|2 2 2 2 8,S,jk,k,a,j,4,2 1,2 1,2,4.4,Burnside,引理,S,jk,k,a,j,1 2 ,n c,1,(a,j,),a,1,S,11,S,12,S,1n,c,1,(a,1,),a,2,S,21,S,22,S,2n,c,1,(a,2,),a,g,S,g1,S,g2,Sg,n,c,1,(a,g,),|,Z,k,|,|,Z,1,|,|,Z,2,|,|,Z,1,|,|Z,k,|=c,1,(a,j,),.,g,j=1,n,k=1,S,jk,=c,1,(a,j,),S,jk,=|Z,k,|,设在,G,作用下,,1,n,分成,l,个等价类。1,n=E,1,+E,2,+E,l,.,g,j=1,n,k=1,4.4,Burnside,引理,若,j,I,同属一个等价类,则,E,i,=E,j,|E,i,|=|E,j,|,因,|E,i,|Z,i,|=|G|,故,|Z,i,|=|Z,j,|.|Z,i,|=|E,j,|Z,j,|,|Z,k,|=|Z,k,|=|E,i,|Z,i,|=|G|=,l,|G|,l,=|Z,k,|=c,1,(a,j,),.,iEj,g,j=1,n,k=1,n,k=1,1,|,G|,1,|,G|,l,i=1,l,i=1,l,i=1,iEj,4.4,Burnside,引理,例2,一正方形分成4格,2着色,有多少种方案?图象:看上去不同的图形。方案:经过转动相同的图象算同一方案。图象数总是大于方案数。,1 2 3 4 5 6 7 8,9 10 11 12 13 14 15 16,4.4,Burnside,引理,不动:p1=(1)(2)(16),逆时针转90:p2=(1)(2)(3 4 5 6)(7 8 9 10)(11 12)(13 14 15 16),顺时针转90:p3=(1)(2)(6 5 4 3)(10 9 8 7)(11 12)(16 15 14 13),转180 :p4=(1)(2)(3 5)(4 6)(7 9)(8 10)(11 12)(13 15)(14 16),(16+2+2+4)/4=6(种方案),。,。,。,4.5,Plya,定理,设,=1,n,M=S,1,S,2,S,m,是,m,种颜色的集合,对,中的元素用,M,中的颜色着色,得到的图象集合用,M,表示,|,M|=m ,每个中的元素都有,m,种着色可能,,n,个元的着色有,m,种可能。即共有,m,个图象。,设,G,是以,为目标记得置换群,是某一转动群,R,的表示。,G,是以,M,为目标记得置换群,是同一转动群,R,的表示。,n,n,n,4.5,Plya,定理,GR,GR,GG,一个着色图象在,G,的作用下变为另一个图象,则这两个图象属于同一方案。,Plya,定理,设,G=P,1,P,2,P,g,是,上的一个置换群,,C(P,k,),是置换,P,k,的循环的个数,用,M,中的颜色对,中的元着色,着色方案数为,l,=m +m +m .,C(P,1,),C(P,2,),C(P,g,),1,|,G|,4.5,Plya,定理,f:M,G,是作用在图象集合,M,上的置换群。对于,PG,P=,k=1,2,n T:PP,P=,i=1,2,m ,T:GG f,i,(k)=f,i,(k ),i=1,2,m ,k=1,n.P,称为由,P,诱导出的,M,上的置换。,G=P,1,P,g,G=P,1,P,2,P,g,T,是,G,到,G,的同构映射。,C,1,(P,i,)=m,k,k,p,f,i,f,i,p,n,_,p,n,C(P,i,),4.5,Plya,定理,在,P,i,作用下,M,中的不动图象的个数,C,1,(P,i,)=m ,C(P,i,),表示,P,i,的循环的个数,即同一循环中的元素都着同一种颜色的图象在,P,i,的作用下保持不变。,对应于,PG,有,PG,P,是,M (,图象集)上的一个置换。现在要计算的也就是图象集在,G,作用下的等价类的个数。下面对前例进行分析,然后推导到一般。,C(P,i,),4.5,Plya,定理,P,1,=(1)(2)(3)(4),P,1,=(1)(2)(16),P,2,=(4321),P,2,=(1)(2)(3 4 5 6)(7 8 9 10)(11 12)(13 14 15 16),P,3,=(1234),P,3,=(1)(2)(6 5 4 3)(10 9 8 7)(11 12)(16 15 14 13),P,4,=(13)(24),P,4,=(1)(2)(35)(46)(79)(8 10)(11)(12)(13 15)(14 16),C(P,1,)=4,C,1,(P,1,)=16=2,C(P,2,)=1,C,1,(P,2,)=2=2,C(P,3,)=1,C,1,(P,3,)=2=2,C(P,4,)=2,C,1,(P,4,)=4=2,求着色的方案数也即求图象的等价类个数。按,Burside,定理,求等价类的个数归结为每个置 换下的不动点(不动图象)的个数。,C(P,1,),C(P,2,),C(P,3,),C(P,4,),2 1,3 4,4.5,Plya,定理,证 对,的,n,个目标用,m,种颜色着色的图象集为,M|M|=|M|=m G,的每一个元,P,i,是,上的一个置换,也对应了,M,上的一个置换,P,i,这样,GG,T:P,i,P,i,在,P,i,的作用下不动图象的个数,C,1,(P,i,),等于,P,i,的同一循环中的目标都着相同色的选择的个数。即,C,1,(P,i,)=m 。,因而在,G,的作用下,,M (,图象)的等价类的个数。,l,=,C,1,(P,1,)+C,1,(P,g,)=m +m +m .,|,n,C(P,i,),C(P,1,),C(P,2,),C(P,g,),1,|,G|,1,|,G|,4.6 举例,例1,等边三角形的3个顶点用红,兰,绿3着色,有多少种方案?,解,在3维空间考虑,3顶点的置换群,S,3,.(3):2,个;(1)(2):3个;(1):1个;,l,=(23+33+3 )/6=10,1,3,1 1,1 2 3,4.6 举例,例2,甲烷,CH,4,的4个键任意用,H,Cl,CH,3,C,2,H,5,连接,有多少种方案?,解,CH,4,的结构是一个正4面体,,C,原子居于正4面体的中心。正4面体的转动群按转动轴分类:,顶点-对面的中心:,(1)(3)8个;,棱中-棱中:,(2)3个;,不动:,(1)1个;6条棱,每条棱看作一有向边,正向重合与反向重合共62=12个位置,故转动群的群元有12个。,l,=114+4/12=44+64/3=36。,2 4,4.6 举例,例3,3个输入端一个输出端的布尔电路有多少种实质上不同的结构?,解,3个变量的布尔函数形式上有2 =256个,但有的只是输入端的顺序不同.输入端的变换群是,S,3,。,输入端的电平取值共有000111计8种。输出,f:S,3,H S,3,H P,j,h,j,=i=07 P1=(1)(2)(3),h1=,(1)(1)1,个;(3)(1)(3)2个;(1)(2)(1)(2)3个;结构总数为2+22+32/6=80,a,1,a,2,a,3,a,1,a,2,a,3,(,i),(,i),(,i),(,i),(,i),pj,pj pj,000 001 010 011 100 101 110 111,000 001 010 011 100 101 110 111,3 8 1 2 2 1 1 4 2,4.6 举例,例4,正6面体的6个面分别用红,蓝两种颜色着色,有多少方案?正6面体的转动群用面的置换表示:面心-面心90(1)(4)6个 180(1)(2)3个 顶点-顶点 120 (3)8个 棱中-棱中 180 (2)6个不动 (1)1个122+32+82+2/24=10,。,。,。,。,2,2 2,2,3,6,3 4 2 6,4.6 举例,例5,用2种颜色给正6面体的8个顶点着色,有多少方案?,解,用顶点的置换表示:面心-面心90 (4)6个 180 (2)3个 顶点-顶点 120 (1)(3)8个 棱中-棱中 180 (2)6个不动 (1)1个172+62+2/24=34+3+32/3=23,。,。,。,。,2,4,2 2,4,8,4 2 8,4.6 举例,例6,在正6面体的每个面上任意做一条对角线,有多少方案?,解,在每个面上做一条对角线的方式有2种,可参考面的2着色问题。但面心-面心的转动轴转90 时,无不动图象。除此之外,都可比照面的2着色。所求方案数:不动 (1)1个 2 面心-面心 90 (1)(4)6个 无不动图象 0 180 (1)(2)3个 32 顶点-顶点,120 (3)8,个 82 棱中-棱中 180 (2)6个 62 2+0+32 +82 +62 /24=8+6+4+6/3=8,。,。,。,。,6,2,2 2,2,3,6 4 2 3,6,4,2,3,4.6 举例,例7,骰子的6个面分别有1,6点,有多少种不同的方案?,解,1)6!个图象的目标集,只有单位元有6!个不动点(图象)其他23个群元不动点。由,Burnside,引理有,C,1,(e)/24=6!/24=30,个方案。,C,1,(p,1,)=C,1,(p,2,)=C,1,(p,23,)=0 2)2,点,3点,6点各有两种取向,1点,4点,5点各有一种取向,故应有302=240种方案。,4.6 举例,为了解决正多面体及一些对称对面体的计算问题介绍下面的定理。,定义,凸多面体与一个顶点相关的面角之和与360 的差称为该顶点的欠角。,定理,凸多面体各顶点欠角的和为720(用欧拉定理证),。,。,4.6 举例,用正5边形搭成的正多面体:,(5-2)180/5=108,360-3108=36。720/36=20(个顶点),一个顶点3条棱,重复度为2:203/2=30条棱 一个顶点相关3个面,重复度为5:203/5=12个面,用正3角形搭成的面最多的正多面体:360-560=60。720/60=12(个顶点),一个顶点关联5条棱,重复度为2:125/2=30条棱。一个顶点关联5个面,重复度为3:125/3=20个面,。,。,。,4.6 举例,足球:欠角=360(108+2120)=12 720/12=60(个顶点)603/2=90(条棱)60/5=12(个5边形)602/6=20(个6边形)(正20面体砍去12个顶点),。,4.7 母函数型式的,Plya,定理,l,=m ,目标集1,n m,种颜色:,b,1,b,2,b,m,m,用(,b,1,+b,2,+b,m,)(b,1,+b,2,+b,m,)(b,1,+b,2,+b,m,),代替。,P(b,1,b,2,b,m,),以,b,1,b,2,b,m,为复元的,n,次对称多项式。令,S,k,=(b,1,+b,2,+b,m,)m S,1,S,2,S,n,P(b,1,b,2,b,m,)=S,j,kC,k,(p,i,)=n,1,|,G|,g,C(Pi),i=1,C(P,i,),C,1,(P,i,),C,2,(P,i,),2 2 2,n n n,C(P,i,),k k k,C(P,i,),C,1,(P,i,),C,2,(P,i,),C,n,(P,i,),C,j,(P,i,),1,|,G|,g n,i=1 j=1,4.7 母函数型式的,Plya,定理,例1,有3种不同颜色的珠子,串成4颗珠子的项链,有哪些方案?,解,正4边形的运动群 绕心转 90 (4)2个 180 (2)1个 绕轴翻转 (2)2个 (1)(2)2个 不动 (1)1个,。,。,1,2,2,2,4,4.7 母函数型式的,Plya,定理,P(b,g,r)=(b+g+r)+2(b+g+r)+3(b+g+r)+2(b+g+r)(b+g+r)/8 =b+g+r+b g+b r+bg+br+g r+gr +2b g+2b r+2g r+2b gr+2bg r+2bgr,例2,4颗红色珠子嵌在正6面体的4个顶点上,有多少方案?,解,相当于对顶点2着色。无珠设,b.(1)1,个;(4)6个;(2)9个;(1)(3)8个;,p=(b+r)+6(b+r)+9(b+r)+8(b+r)(b+r)/24,4 4 4 4 2 2 2 2,2 2 2 2,4 4 4 3 3 3 3 3 3,2 2 2 2 2 2 2 2 2,8 4 4 2 2 2 4 2 3 3 2,4.7 母函数型式的,Plya,定理,b r 的系数:+62+9+82=7,1 8!,24 4!4!,4!,2!2!,4 4,4.8 图的计数,例1,4个顶点的图,对完全图的边的2着色,S,4,的每个置换对应6条边的集上的一个置换 (1)(1)1个 (4)(2)(4)6个 (2)(1)(2)3个 (1)(2)(1)(2)6个(1)(3)(3)8个,P(x,y)=(x+y)+9(x+y)(x+y)+8(x+y)+6(x+y)(x+y),1,24,6 2 2 2 2 3 3 2,2 2 2 2,4,1,2,2,6,1,2 2,2 2,2,4.8 图的计数,=,x+x y+2x y+3x y+2x y+xy+y,6 5 4 2 3 3 2 4 5 6,4.8 图的计数,例2,求4个顶点的不同构的有向图的个数。,解,顶点置换 有向边置换,(1)(1)1个 (1)(2)(1)(2)6个 (2)(2)3个 (1)(3)(3)8个 (4)(4)6个,P(x,y)=(x+y)+6(x+y)(x+y)+3(x+y)+8(x+y)+6(x+y),4,2,2,12,2 5,6,4,3,12 2 2 2 5 2 2 6,3 3 4 4 4 3,1,24,4.8 图的计数,x y,的系数:+6(1+)+3+0+0=5,1 12!5!6!,24 2!10!4!5!,2 10,
展开阅读全文