组合数学课件(经典)第四章

第四章Pólya定理•群的概念•置换群•循环、奇循环与偶循环•Burnside引理•Pólya定理•例•母函数型的Pólya定理•图的计数4.1群的概念(1)群定义给定集合G和G上的二元运算·，满足下列条件称为群。(a)封闭性：若a,b∈G,则存在c∈G,使得a·b=c.(b)结合律成立：任意a,b,c∈G,有(a·b)·c=a·(b·c).(c)有单位元：存在e∈G,任意a∈G.a·e=e·a=a.(d)有逆元：任意a∈G,存在b∈G,a·b=b·a=e.b=a.由于结合律成立，(a·b)·c=a·(b·c)可记做a·b·c.例证明对于a1,a2,…,an的乘积，结合律成立.a·a·…·a=a(共n个a相乘).-1n4.1群的概念(2)简单例子例G={1,-1}在普通乘法下是群。例G={0,1,2,…,n-1}在modn的加法下是群.例二维欧氏空间所有刚体旋转T={Ta}构成群。其中Ta=cosasina-sinacosaTbTa=cosbsinbcosasina-sinbcosb-sinacosa4.1群的概念=cosacosb-sinasinbsinacosb+cosasinb-sinacosb-cosasinbcosacosb-sinasinb=cos(a+b)sin(a+b)=Ta+b-sin(a+b)cos(a+b)从而有(a)封闭性;(b)结合律成立：(TαTβ)Tγ=Tα(TβTγ)=TαTβTγ;(c)有单位元：T0=;(d)有逆元：Ta=T-a=cosa-sinasinacosa10014.1群的概念•前两例群元素的个数是有限的，所以是有限群；后一例群元素的个数是无限的，所以是无限群。•有限群G的元素个数叫做群的阶,记做|G|。•若群G的任意二元素a,b恒满足ab=ba。责称G为交换群，或Abel群。•设G是群,H是G的子集,若H在G原有的运算之下也是一个群,则称为G的一个子群。4.1群的概念•基本性质(a)单位元唯一e1e2=e2=e1(b)消去律成立ab=ac→b=c,ba=ca→b=c(c)每个元的逆元唯一aa=aa=e,ab=ba=e,aa=ab,a=b(d)(ab….c)=c…ba.c…baab…c=e-1-1-1-1-1-1-1-1-1-1-14.1群的概念(e)G有限，a∈G，则存在最小正整数r，使得a=e.且a=a.证设|G|=g,则a,a,…,a,a∈G,由鸽巢原理其中必有相同项。设a=a,1≤m＜l≤g+1,e=a,1≤l-m≤g，令l-m=r.则有a=aa=e.即a=a.既然有正整数r使得a=e,其中必有最小者，不妨仍设为r.r称为a的阶。易见H={a,a,…a,a=e}在原有运算下也是一个群。r-1r-12gg+1mll-mrr-1r-1-1r2r-1r4.2置换群•置换群是最重要的有限群，所有的有限群都可以用之表示。•置换：[1,n]到自身的1-1变换。n阶置换。[1,n]目标集。(),a1a2…an是[1,n]中元的一个排列。n阶置换共有n!个，同一置换用这样的表示可有n!个表示法。例如p1=()=()，n阶置换又可看作[1,n]上的一元运算，一元函数。12…na1a2…an12343124314223414.2置换群•置换乘法P1=(),P2=()P1P2=()()=()注意：既然先做P1的置换，再做P2的置换就规定了若作为运算符或函数符应是后置的。这与一般习惯的前置不一样。•一般而言，对[1,n]上的n阶置换，i[1,n]要写成(i)P1P2，而不是P1P2(i).(i)P有时写成i在上面例中，1→3→2,2→1→4,3→2→3,4→4→1.也可写(1)P1P2=2,(2)P1P2=4,(3)P1P2=3,(4)P1P2=1.P2P1=()()=()≠P1P2.1234312412343124123443213124243112342431P1P1P2P1P1P2P2P21234432143214213123442314.2置换群•(1)置换群[1,n]上的所有n阶置换在上面的乘法定义下是一个群。(a)封闭性()()=()(b)可结合性(()())()=()=()(()())(c)有单位元e=()(d)()=()12…na1a2…ana1a2…anb1b2…bn12…nb1b2…bn12…na1a2…ana1a2…anb1b2…bn12…na1a2…ana1a2…anb1b2…bn12…nc1c2…cnb1b2…bnc1c2…cnb1b2…bnc1c2…cn12…n12…n12…na1a2…ana1a2…an12…n-14.2置换群•(2)例等边三角形的运动群。绕中心转动120，不动，绕对称轴翻转。P1=(),P2=(),P3=(),P4=(),P5=(),P6=()。[1,n]上的所有置换(共n!个)构成一个群，称为对称群，记做Sn.•注意：一般说[1,n]上的一个置换群，不一定是指Sn.但一定是Sn的某一个子群。1231231232311233121231321233211232131234.2置换群•任一n阶群同构于一个n个文字的置换群。设G={a1,a2,…,an}，指定G中任一元ai,任意aj∈G，Pi：aj→ajai，则Pi是G上的一个置换，即以G为目标集。Pi=()，G的右正则表示f：ai→()=Pi。f是单射：ai≠aj，则Pi≠Pjf(aiaj)=()=()()=f(ai)f(aj)令P={Pi=()|a,ai∈G},则P≈Ga1a2…ana1aia2ai…anaiaiaaia1a2…ana1(aiaj)a2(aiaj)…an(aiaj)a1a2…ana1aia2ai…anaia1a2…an(a1ai)aj(a2ai)aj…(anai)ajaiaai4.3循环、奇循环与偶循环•(a1a2…am)=()称为置换的循环表示。•于是()=(14523),()=(132)(45),()=(154)(2)(3).•(a1a2…am)=(a2a3…ama1)=…=(ama1…am-1)有m种表示方法。a1a2…am-1ama2a3…ama11234543152123453125412345523144.3循环、奇循环与偶循环•若两个循环无共同文字，称为不相交的，不相交的循环相乘可交换。如(132)(45)=(45)(132).•若p=(a1a2…am),则p=(1)(2)…(n)=e.•定理任一置换可表成若干不相交循环的乘积。证对给定的任一置换p=()，从1开始搜索1→ai1→ai2→ai3→…→aik→1得一循环(1ai1ai2…aik),若(1ai1…aik)包含n12…na1a2…anpppppp4.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号牌占据.pipp4.3循环、奇循环与偶循环5126...5332115252...296284272p=(227143317953)(42840464925137)(62915830412111)(1031163443223719)(1232424724384523)(1835)(2036444850512639)(52)p=e2阶循环叫做对换。84.3循环、奇循环与偶循环•定理任一循环都可以表示为对换的积。(12…n)=(12)(13)…(1n)=(23)(24)…(2n)(21)表示不唯一。sgn(p)∈{1,-1}.(1)sgn(p)∏(2)sgn(pq)=sgn(p)sgn(q)(3)sgn((i,i+1))=-1,p=(i,i+1)(4)sgn((lk))=-1奇数个邻位对换。故任一置换表示成对换的个数的奇偶性是唯一的置换分成两大类：奇置换与偶置换。循环长度减1的奇偶性即置换奇偶性。△=i-ji-jppij4.3循环、奇循环与偶循环•例0表示空格，任一变动都是与0做相邻的对换。p=(0)(115)(214)(313)(412)(511)(610)(79)(8)奇置换。0从右下角出发回到右下角，水平方向上，垂直方向上都做了偶数次对换。一个奇置换不会等于一个偶置换。123456789101112131415015141312111098765432104.3循环、奇循环与偶循环•定理Sn中所有偶置换构成一阶为(n!)/2的子群称为交错群，记做An.证(1)封闭性(2)单位元(3)逆元(ik)=(ik)设p=(i1j1)(i2j2)…(iiji),则p=(iiji)…(i1j1)令Bn=Sn-An,|Bn|+|An|=n!,则(ij)Bn包含于An|Bn|≤|An|，(ij)Bn包含于An|An|≤|Bn|∴|An|=|Bn|=(n!)/2-14.4Burnside引理•(1)共轭类先观察S3,A3,S4,A4,以增加感性认识。S3={(1)(2)(3),(23),(13),(123)(132)}.A3={(1)(2)(3),(123),(132)}.S4={(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.4Burnside引理•Sn中P的循环格式(1)(2)…(n),∑kCk=n•Sn中有相同格式的置换全体构成一个共轭类。•定理1Sn中属(1)(2)…(n)共轭类的元的个数为C1C2Cnnk=1C1C2Cnn！C1!C2!…Cn!12…nC1C2Cn4.4Burnside引理•证(1)(2)…(n)即C1C2Cn(·)…(·)(··)…(··)…(·…·)…(·…·)_∧_/\1个_∧_/\2个____∧____/\n个\____________/\/C1个\________________/\/C2个\________________/\/Cn个一个长度为k的循环有k种表示，Ck个长度为k的循环有Ck!k种表示.1,2,…,n的全排列共有n!个，给定一个排列，装入格式得一置换，除以前面的重复度得n!/(C1!C2!…Cn!12…n)个不同的置换.CkC1C2Cn4.4Burnside引理•例1S4中(2)共轭类有4!/(2!2)=3(1)(3)共轭类有4!/(C1!C3!13)=8(1)(2)共轭类有4!/(C1!C2!12)=6•(2)k不动置换类设G是[1,n]上的一个置换群。G≤Sn.K∈[1,n]G中使k保持不变的置换全体，称为k不动置换类，记做Zk.2C1C3C1C2111124.4Burnside引理•定理置换群G的k不动置换类Zk是G的一个子群。封闭性：k→k→k,kk.结合性：自然。有单位元：G的单位元属于Zk.有逆元：P∈Zk,k→k,则k→k,P∈Zk.∴Zk≤G.P1P2P1P2PP-14.4Burnside引理•(3)等价类举一个例子。G={(1)(2)(3)(4),(12),(34),(12)(34)}.在G下，1变2，3变4，但1不变3。Z1=Z2={e,(34)},Z3=Z4={e,(12)}.对于A4,Z1={e,(234),(243)},Z2={e,(134),(143)}Z3={e,(124),(142)},Z4={e,(123),(132)}•一般[1,n