第四组合数学

第四章Plya定理,群的概念置换群循环、奇循环与偶循环Burnside引理Plya定理例母函数型的Plya定理图的计数,4.1群的概念,(1)群定义给定集合G和G上的二元运算，满足下列条件称为群。(a)封闭性：若a,bG,则存在cG,使得ab=c.(b)结合律成立：任意a,b,cG,有(ab)c=a(bc).(c)有单位元：存在eG,任意aG.ae=ea=a.(d)有逆元：任意aG,存在bG,ab=ba=e.b=a.由于结合律成立，(ab)c=a(bc)可记做abc.例证明对于a1,a2,an的乘积，结合律成立.aaa=a(共n个a相乘).,-1,n,4.1群的概念,(2)简单例子例G=1,-1在普通乘法下是群。例G=0,1,2,n-1在modn的加法下是群.例二维欧氏空间所有刚体旋转T=Ta构成群。其中Ta=cosasina-sinacosaTbTa=cosbsinbcosasina-sinbcosb-sinacosa,4.1群的概念,=cosacosb-sinasinbsinacosb+cosasinb-sinacosb-cosasinbcosacosb-sinasinb=cos(a+b)sin(a+b)=Ta+b-sin(a+b)cos(a+b)从而有(a)封闭性;(b)结合律成立：(TT)T=T(TT)=TTT;(c)有单位元：T0=;(d)有逆元：Ta=T-a=cosa-sinasinacosa,1001,4.1群的概念,前两例群元素的个数是有限的，所以是有限群；后一例群元素的个数是无限的，所以是无限群。有限群G的元素个数叫做群的阶,记做|G|。若群G的任意二元素a,b恒满足ab=ba。称G为交换群，或Abel群。设G是群,H是G的子集,若H在G原有的运算之下也是一个群,则称为G的一个子群。,4.1群的概念,基本性质,单位元唯一e1e2=e2=e1消去律成立ab=acb=c,ba=cab=c每个元的逆元唯一aa=aa=e,ab=ba=e,aa=ab,a=b(d)(ab.c)=cba.cbaabc=e,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,4.1群的概念,(e)G有限，aG，则存在最小正整数r，使得a=e.且a=a.,r,-1,r-1,4.2置换群,置换群是最重要的有限群，所有的有限群都可以用之表示。置换：1,n到自身的1-1变换。n阶置换。1,n目标集。(),a1a2an是1,n中元的一个排列。n阶置换共有n!个，同一置换用这样的表示可有n!个表示法。例如p1=()=()，n阶置换又可看作1,n上的一元运算，一元函数。,12na1a2an,12343124,31422341,4.2置换群,置换乘法P1=(),P2=()P1P2=()()=()注意：既然先做P1的置换，再做P2的置换就规定了若作为运算符或函数符应是后置的。这与一般习惯的前置不一样。一般而言，对1,n上的n阶置换，i1,n要写成(i)P1P2，而不是P1P2(i).(i)P有时写成i在上面例中，132,214,323,441.也可写(1)P1P2=2,(2)P1P2=4,(3)P1P2=3,(4)P1P2=1.P2P1=()()=()P1P2.,12343124,12343124,12344321,31242431,12342431,P1,P1,P2,P1,P1,P2,P2,P2,12344321,43214213,12344231,4.2置换群,置换群具有的性质(a)封闭性()()=()(b)可结合性()()()=()=()()()(c)有单位元e=()(d)()=(),12na1a2an,a1a2anb1b2bn,12nb1b2bn,12na1a2an,a1a2anb1b2bn,12na1a2an,a1a2anb1b2bn,12nc1c2cn,b1b2bnc1c2cn,b1b2bnc1c2cn,12n12n,12na1a2an,a1a2an12n,-1,定义：置换群1,n上的所有n阶置换集合及在其上定义的置换乘法构成的代数系统是一个群，该群成为置换群。,4.2置换群,(2)例等边三角形的运动群。绕中心转动120，不动，绕对称轴翻转。P1=(),P2=(),P3=(),P4=(),P5=(),P6=()。1,n上的所有置换(共n!个)构成一个群，称为对称群，记做Sn.注意：一般说1,n上的一个置换群，不一定是指Sn.但一定是Sn的某一个子群。,123123,123231,123312,123132,123321,123213,123,4.3循环、奇循环与偶循环,(a1a2am)=()称为置换的循环表示。于是()=(14523),()=(132)(45),()=(154)(2)(3).(a1a2am)=(a2a3ama1)=(ama1am-1)有m种表示方法。,a1a2am-1ama2a3ama1,1234543152,1234531254,1234552314,4.3循环、奇循环与偶循环,若两个循环无共同文字，称为不相交的，不相交的循环相乘可交换。如(132)(45)=(45)(132).若p=(a1a2am),则p=(1)(2)(n)=e.定理任一置换可表成若干不相交循环的乘积。,n,4.3循环、奇循环与偶循环,例一副扑克牌，一分为二，交错互相插入(洗牌)，这样操作一次相当于一个置换p。,i=,p,(i+1)/2,i=1,3,5,51.i/2+26,i=2,4,6,52.,p=(),第i个位置被i号牌占据.,pi,p,p,4.3循环、奇循环与偶循环,26.533211,5252.296284272,p=(1)(227143317953)(42840464925137)(62915830412111)(1031163443223719)(1232424724384523)(1835)(2036444850512639)(52)p=e2阶循环叫做对换。