资源描述
,*,第,4,章,Burnside,引理与,Polya,定理,4.1,群的概念,1,4.2,置换群,1,4.3,循环、奇循环与偶循环,1,4.4 Burnside,引理,2,4.5,Polya,定理,3,4.6,举例,3,4.7,母函数形式的,Polya,定理 *,4.8,图的计数 *,4.9,Polya,定理的若干推广,*,1,第四章 贝恩塞特引理与波利亚定理,一个田字格，用两种颜色染色，共有多少种方案？旋转能够重叠的算一种方案。,2,第四章 贝恩塞特引理与波利亚定理,C,1,C,2,C,3,C,4,C,5,C,6,C,7,C,8,C,9,C,10,C,11,C,12,C,13,C,14,C,15,C,16,3,4.1,群的概念,(a),封闭性,:,4.1.1,群的定义,:,给定一个集合,G=,a,b,c,.,和集合,G,上的二元运算“,”,并满足下列,4,个条件,(b),满足结合律,:,(c),存在单位元素,(d),存在逆元素,称集合,G,在运算“,”,之下是一个群,有时也称,G,是一个群,运算,a,b,简记为,ab,。,4,例,4.1,对于任意两个整数,当除以,n,的余数相等时,说他们是相等的,或,mod n,相等,.,(a),封闭性成立,除以,n,的余数只能是,0,1,2,.,n-1,(b),普通加法满足结合律,(c)0,是单位元素,(d),对于任意,a,G,a+(n,-a)=0,modn,集合,G=0,1,2,.,n-1,对,mod n,在加法下是一个群,.,n-a,是,a,的逆。,4.1,群的概念,5,例,4.2,设,R=0,0,90,0,180,0,270,0,表示几何图形绕轴心顺时针旋转角度的,4,种状态,设,“,”,是,R,上的二元运算,ab,表示平面图形连续旋转,a,和,b,得到的总旋转状态,并规定旋转,360,0,等于原来的状态，也就是没有旋转。证明集合,A,在运算“,”,构成一个群。,4.1,群的概念,0,90,180,270,0,0,90,180,270,90,90,180,270,0,180,180,270,0,90,270,270,0,90,180,(a),封闭性成立,(b),结合律成立,(c)0,是单位元素,(d),逆原素存在,6,有限群,G,的元素个数叫做群的阶，记作,G,当群的元素个数是有限时,称为有限群,当群的元素个数为无限时,称为无限群,.,若群,G,的任意二元素,a,b,恒满足,ab,=,ba,时,称,G,为交换群,或,Abel,群。,有限群和无限群,交换群,4.1,群的概念,7,4.1.2,群的基本性质,定理,4.1,群的单位元是唯一的,4.1,群的概念,定理,4.2,ab,=,acb,=,c,ba,=,ca,b,=c,定理,4.3 G,中每一个元素的逆元素是唯一的,定理,4.4,8,定理,4.5 G,是有限群,h=G,设,G=a,1,a,2,.,a,h,设,a,是,G,的任意元素,则必存在一个最小正整数,r(a,),使得,a,r(a,),=e,而且,a,-1,=a,r(a)-1,证明,:h,是群,G,的阶,G,aG,aa,r(a)-1,=e,即,a,-1,=a,r(a)-1,。,构造,:a,a,2,.,a,h,a,h+1,共,h+1,项,其中至少有两项相等,设,a,m,=,a,n,m,n,a,r(a,),=e,4.1,群的概念,设,mn,取所有,a,m,=,a,n,m,n,m-n,的最小值,令,m-n,=,r(a,),9,子群定义,4.1,设,G,是群,H,是,G,的子集,若,H,在,G,的原来定义的运算下也构成群,则称,H,为群,G,的子群。,例,4.2,若,x,是群,G,的一个元素，存在一最小的正整数,m,，使,x,m,=e,，则称,m,为,x,的阶，试证：,C=e,x,x,2,x,m-1,是,G,的一个子群,证明：,(1),封闭性成立。,(2),结合律,(3),单位元,(4),逆元素,4.1,群的概念,*,10,4.2,置换群,假定,n,个元素为,1,2,3,.,n,并且若,ij,a,i,a,j,i,j,=1,2,.,n,若元素,1,被,1,到,n,中某一元素,a,1,所取代,2,被其中某一元素,a,2,所取代，,.,n,被,a,n,所取代,置换的定义,有限集合,S,到自身的一一对应称为,S,上的一个置换。,11,说明：只要对应一样，就是同一个置换,置换与表示方式或顺序无关,4.2,置换群,12,置换运算的定义,4.2,置换群,13,n,个元素形成的置换集合在以上运算下形成一个群。,(1),封闭性,4.2,置换群,14,(2),结合律,4.2,置换群,15,(3),单位元（恒等置换）,(4),逆元素（逆映射）,4.2,置换群,16,例,4.4,圆圈上装有,A,B,C,三颗珠子,正好构成圆内接等边三角形,ABC,(a),绕过圆心,o,垂直于圆平面的轴,沿反时针方向旋转,0,度,120,度,240,度,;,(b),沿过圆心,o,及,A(,或,B,或,C),点的轴线翻转,180,度,经过,(,a),(b,),变换,A,B,C,三颗珠子两两重合,但顶点交换了位置,经过以上变换形成的所有置换构成群。,用,1,代表,A,2,代表,B,3,代表,C,A,C,B,4.2,置换群,17,A,C,B,设,A,代以,1,B,代以,2,C,代以,3,可得,:,3,、单位元存在,4,、逆元素存在,1,、封闭性成立,2,、结合律成立,4.2,置换群,18,n,个元素的置换的个数以及,n,个元素的置换群,有,n!,个置换,这,n!,个置换构成一个群,称为,n,个文字的对称群,记作,Sn,;,任一,n,阶有限群都和一个,n,个文字的置换群同构。,Sn,的任一子群称为置换群,;,4.2,置换群,19,群同构的定义,设,(G,1,+),(G,2,*),是群，如果存在一个一一对应：,G,1,G,2,，使得,a,bG,1,有,(,a+b,)=(a)*(b),则称群,G,1,与,G,2,同构,;,4.2,置换群,0,1,2,模,3,相等,例,:,20,定理：任何一个群都同构于一个置换群,证明的方法是建立起有限群,G=a,1,a,2,.,a,n,的元素,a,i,和某一置换群的某一置换一一对应,并且同构。,4.2,置换群,对于,G,的某一元素,a,i,构造对应序列,:,a,1,a,i,a,2,a,i,.,a,n,a,i,其中所有元素都不相同,如若不然,a,h,a,i,=,a,m,a,i,两端同乘以,a,i,的逆可得,a,h,=a,m,是一个置换,21,令,a,i,和置换,对应,即,(,a,i,)=p,i,4.2,置换群,首先证明上述对应关系是一一对应：,第二步,:,证明这些置换构成群,进而需证,:,若,(,a,i,)=,p,i,(,a,j,)=,p,j,则,(,a,i,a,j,)=,p,i,p,j,22,a,1,对应,a,2,对应,a,n,对应,因此上述对应关系是一一对应。,首先证明上述对应关系是一一对应：,4.2,置换群,23,单位元存在，结合律成立,需证明封闭性和逆元素。,4.2,置换群,第二步,:,证明这些置换构成群,24,封闭性成立。,4.2,置换群,25,4.2,置换群,26,进而需证,:,若,(,a,i,)=,p,i,(,a,j,)=,p,j,证明,:,根据假定有,则,(,a,i,a,j,)=,p,i,p,j,4.2,置换群,*,27,4.3,循环、奇循环与偶循环,定义,:,叫做,m,阶循环置换,例如,5,个文字,1,2,3,4,5,的置换,28,循环置换,(a,1,a,2,.,a,k,),实际上只与元素的相邻状况有关,而与哪个元素为首无关,比如,(123)=(231),如若两个循环,(a,1,a,2,.a,n,),与,(b,1,b,2,.,b,m,),没有相同的文字,则称为是不相交的,不相交两循环的乘积可交换,.,不相交循环置换,4.3,循环、奇循环与偶循环,29,定理设,(i,1,i,2,.,i,k,),与,=j,1,j,2,.,j,r,是两个没有共同数字的循环置换，则与可交换，即,=,。,证,分三种情况讨论,1.,被,变动的元素,2.,被,变动的元素,3.,不被二者变动的元素。,i1,2,.,n,如果,ii,ii,所以,ii,所以,i=i,。,i,不被变动,即,i=i,所以,i=i,。,1.,针对被,变动的元素,2.,针对被,变动的元素,同样可证,3.,对于不被二者变动的元素显然有,=,。,4.3,循环、奇循环与偶循环,30,定理,设,=(i,1,i,2,.,i,r,),则,r,=I,且,1,kr,时,k,I,。,置换,把,i,1,变,i,2,，把,i,2,变,i,3,.,i,r-1,变,i,r,i,r,变,i,1,。,证,置换,2,把,i,1,变,i,3,，把,i,2,变,i,4,.,i,r-1,变,i,1,i,r,变,i,2,。,.,置换,r-1,把,i,1,变,i,r,，把,i,2,变,i,1,.,i,r-1,变,i,r-2,i,r,变,i,r-1,。,置换,r,把,i,1,变,i,1,，把,i,2,变,i,2,.,i,r-1,变,i,r-1,i,r,变,i,r,。,假设使,k,=I,的最小正整数,k,为,的阶。,r-,循环置换的阶为,r,。,4.3,循环、奇循环与偶循环,31,定理,4.6,任何一个置换都可以表示成若干循环的乘积。,例如：,4.3,循环、奇循环与偶循环,32,定理,4.6,任何一个置换都可以表示成若干循环的乘积。,证明,:,对已知置换,从,1,开始搜索,1,a,1,a,1,b,2,b,2,b,3,这样找下去，总有一次不再是新的元素了，设第一个不是新元素的是,b,k+1,b,k,b,k+1,则,b,k+1,一定是,1,，,如果,b,k+1,=b,i,ik+1,b,i,1,，,b,i-1,b,i,b,k,b,k+1,b,i-1,=,b,k,矛盾！,4.3,循环、奇循环与偶循环,33,从,1,开始搜索,如果,1,a,1,b,2,.b,k,1,则得一循环置换,(1a,1,b,2,.,b,k,),，如若它包含了,123.n,的所有文字,则搜索停止,否则从余下的文字中的任意一文字开始,如法进行,再得一循环,如此反复直到所有文字都取完为止,这样便得到一组不相交的循环之积。,证毕。,4.3,循环、奇循环与偶循环,34,定义,4.2 2,阶循环,(,ij,),叫做,i,和,j,的对换或换位,定理,4.7,任意一个循环都可以表达成若干对换之积,对换或换位,证明只需给出一个分解的方法就可以了,对换的性质,(,ij,)(,ij,)=(i)(j)=I,(ij),-1,=(,ij,),4.3,循环、奇循环与偶循环,35,定义,4.3,若一个置换可分解成奇数个换位之积,叫做奇置换,;,若可分解成偶数个换位之积,叫做偶置换,如果把置换分解成若干个对换的乘积，则对换的个数的奇偶性是不变的。,略：,4.3,循环、奇循环与偶循环,36,例子，图,4.3,是一个有,4,4,格的棋盘，除了右下角的一个格子空着外，其余格子布着,1-15,个棋子，,(0),(0),与空格相邻的棋子可以与空格互换得到另一种布局，这样的一次交换可以看作是一次置换。,4.3,循环、奇循环与偶循环,37,证明图,4.3,的状态无论如何不可能通过标志为“,0”,的棋子与其相邻的棋子换位而达到图,4.4,的状态。,(0),(0),图,4.3,图,4.4,图,4.3,到图,4.4,相当于作如下置换。,4.3,循环、奇循环与偶循环,38,定理,4.8,S,n,中偶置换的全体构成一个,n!/2,阶的子群,记作,An,，称为交代群。,证明：先证,An,是,Sn,的子群,是偶置换,An,包含单位元；,(1),封闭性,:,若,p,1,p,2,是偶置换,则,p,3,=p,2,p,1,也是偶置换,故封闭性成立,.,(2),结合律,:,置换群的结合律成立,.,(3),单位元素,:,置换群的单位元素本身,.,4.3,循环、奇循环与偶循环,39,(4),逆
展开阅读全文