组合数学(4)省公开课一等奖全国示范课微课金奖课件

第四章Pólya定理群概念置换群循环、奇循环与偶循环Burnside引理Pólya定理例母函数型Pólya定理图计数第1页Review:义11设(A；*)是一个代数系统，假如*是可结合，而且A中有单位元，而且A中任意一个元素都有逆元，则称(A；*)是一个群。在运算“*”已知情况下，群(A；*)能够简记为A。由群定义能够知道，一个代数系统(A；*)是群，则应满足以下条件：(1)(A；*)是可结合。即：(A；*)是一个半群。(2)(A；*)中有单位元e。(3)(A；*)中，任何一个元素都有逆元。假如一个群满足交换律，则此群称为交换群，也称作阿贝尔(Abel)群(或加法群)。4/13/202410:01PM2第2页4/13/202410:01PMZhangSanyuan,ZhejiangUniv.3拉格朗日定理定理：设<H,*>是群<G,*>一个子群。那么：是G一个等价关系，记2。假如G是有限群，|G|=n,|H|=m,则m|n。第3页4/13/202410:01PMZhangSanyuan,ZhejiangUniv.4推论1：任何质数阶群不可能有非平凡子群。推论2：<G,*>n阶有限群。那么对任意a∈G,a阶必为n因子且必有。这里e为单位元。假如n为质数，<G,*>必为循环群。第4页4.2置换群置换群是最主要有限群，全部有限群都能够用之表示。置换：[1,n]到本身1-1变换。n阶置换。[1,n]目标集。(),a1a2…an是[1,n]中元一个排列。n阶置换共有n!个，同一置换用这么表示可有n!个表示法。比如p1=()=()，n阶置换又可看作[1,n]上一元运算，一元函数。12…na1a2…an1234312431422341第5页4.2置换群置换乘法P1=(),P2=() P1P2=()()=() 注意：既然先做P1置换，再做P2置换就要求了若作为运算符或函数符应是后置。这与普通习惯前置不一样。P2P1≠P1P2.1234312412343124123443213124243112342431第6页4.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-1第7页4.2置换群(2)例等边三角形运动群。 绕中心转动120，不动， 绕对称轴翻转。P1=(),P2=(),P3=(),P4=(),P5=(),P6=()。 [1,n]上全部置换(共n!个)组成一个群，称为对称群，记做Sn. 注意：普通说[1,n]上一个置换群，不一定是指Sn.但一定是Sn某一个子群。123123123231123312123132123321123213123第8页4.2置换群任一n阶有限群同构于一个n个文字置换群。两个群同构：存在一个双射。且同态。第9页4.2置换群设G={a1,a2,…,an}，指定G中任一元ai,任意aj∈G，Pi：aj→ajai，则Pi是G上一个置换，即以G为目标集。令Pi=()，a1a2…ana1aia2ai…anaiPi是单射：ai≠aj，则Pi≠Pj.Pi同态：

f(aiaj)=()=()()=f(ai)f(aj)a1a2…ana1(aiaj)a2(aiaj)…an(aiaj)a1a2…ana1aia2ai…anaia1ai

a2ai

…anai(a1ai)aj(a2ai)aj…(anai)aj第10页4.2置换群

令P={Pi|a,ai∈G},则P≈G第11页4.3循环、奇循环与偶循环(a1a2…am)=(

)

称为置换循环表示。于是(

)=(14523),(

)=(132)(45),(

)=(154)(2)(3).(a1a2…am)=(a2a3…ama1)=…=(ama1…am-1)有m种表示方法。a1a2…am-1ama2a3…ama1123454315212345312541234552314第12页4.3循环、奇循环与偶循环若两个循环无共同文字，称为不相交，不相交循环相乘可交换。如(132)(45)=(45)(132).若p=(a1a2…am),则p=(1)(2)…(n)=e.（拉格朗日定理推论）定理任一置换可表成若干不相交循环乘积。证对给定任一置换，

从1开始搜索1→ai1→ai2→ai3→…→aik→1得一循环(1ai1

ai2…aik),若(1ai1

…aik)包含nppppp第13页4.3循环、奇循环与偶循环了[1,n]全部文字，则命题成立。不然在余下文字中选一个，继续搜索,又得一循环。直到全部文字都属于某一循环为止。因不相交循环可交换，故除了各个循环次序外，任一置换都有唯一循环表示。2阶循环叫做对换第14页4.3循环、奇循环与偶循环定理任一循环都能够表示为对换积。(12…n)=(12)(13)…(1n)=(23)(24)…(2n)(21)表示不唯一。任一置换表示成对换个数奇偶性是唯一。置换分成两大类：奇置换与偶置换。第15页4.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)An包含于Bn|An|≤|Bn|∴|An|=|Bn|=(n!)/2-1第16页4.4Burnside引理(1)共轭类 先观察S3,A3,S4,A4,以增加感性认识。S3={(1)(2)(3),(23),(13),(12),(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)}.第17页4.4Burnside引理Sn中P循环格式(1)(2)…(n), ∑kCk=

nSn中有相同格式置换全体组成一个共轭类。定理1

Sn中属(1)(2)…(n)共轭类元个数为C1C2Cnnk=1C1C2Cn

n！C1!C2!…Cn!12…nC1C2Cn第18页4.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)个不一样置换.CkC1C2Cn第19页4.4Burnside引理例1

S4中(2)2

共轭类有4!/(2!22)=3(1)1(3)1

共轭类有4!/(C1!C3!1131)=8(1)2(2)1

共轭类有4!/(C1!C2!1221)=6(2)k不动置换类 设G是[1,n]上一个置换群。G≤Sn.K∈[1,n]G中使k保持不变置换全体，称为k不动置换类，记做Zk.第20页4.4Burnside引理定理置换群Gk不动置换类Zk是G一个子群。 封闭性：k→k→k,kk. 结合性：自然。 有单位元：G单位元属于Zk. 有逆元：P∈Zk,k→k,则k→k,P∈Zk.∴Zk≤G.P1P2P1P2PP-1第21页4.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]上G将[1,n]分成若干等价类，满足等价类3个条件.(a)自反性;(b)对称性;(c)传递性。如第一个例子中，共有两个等价类：{1,2},{3,4}第22页4.4Burnside引理一个由G定义关系k： 若存在p∈G,使得k→j则称kRj.显然kRk；kRj则jRk；kRj,jRl则kRl。R是[1,n]上一个等价关系。将[1,n]划分成若干等价类。含目标集元素k在G作用下等价类也称为含k轨道。p第23页4.4Burnside引理定理设G是[1,n]上一个置换群，Ek是[1,n]在G作用下包含k等价类(轨道)，Zk是k不动置换类。有|Ek||Zk|=|G|. 证设|Ek|=m,Ek={a1(=k),a2,…,am},于是存在pi满足a1→ai,i=1,2,…,m.令P={p1,p2,…,pm},(是集合不一定是群.)令Gi=Zkpi,i=1,2,…,m.Gi包含于G(G关于Zk陪集分解)i≠j,Gi∩Gj=Φ.G1+G2+…+Gm包含于G.另首先，任意P∈G.k→aj→kPPj∈Zk,

P∈ZkPj=Gj. ···-1Pj-1Ppi第24页4.4Burnside引理 ∴G包含于G1+…+Gm.从而，G=G1+G2+…+Gm. |G|=|G1|+|G2|+…+|Gm|=|Zk|·m=|Zk|·|Ek|·····第25页4.4Burnside引理(4)Burnside引理 设G={a1,a2,…ag}是目标集[1,n]上置换群。每个置换都写成不相交循环乘积。G将[1,n]划分成若干个等价类。C1(ak)是在置换ak作用下不动点个数，也就是长度为1循环个数。Burnside引理设G={a1,a2,…ag}是目标集[1,n]上置换群，则G在N上引出不一样等价类个数为 =[c1(a1)+c1(a2)+…+c1(ag)]/|G|第26页4.4Burnside引理比如，G={e,(12),(34),(12)(34)}.c1(a1)=4,c1(a2)=2,c1(a3)=2,c1(a4)=0. =[4+2+2+0]/4=2.以本例列表分析：1234c1(aj)(1)(2)(3)(4)11114(1)(12)(3)(4)00112(1)(2)(1)(2)(34)11002(1)(2)(12)(34)00000(2)|Zk|→22228Sjkkaj421212第27页4.4Burnside引理Sjk= 对第j行求和得c1(aj),对第k列求和得|Zk|表中元素总和=∑∑Sjk=∑|Zk|=∑c1(aj).普通而言，与上表相仿，有下页表格，其中

Sjk=1,k=k,0,k≠k.ajajgj=1gj=1nk=1nk=11,k=k,0,k≠k.ajaj第28页4.4Burnside引理12…nc1(aj)a1S11S12…S1nc1(a1) a2S21S22…S2nc1(a2)…………agSg1Sg2…Sgnc1(ag)|Zk||Z1||Z2|…|Zn|Sjkkaj∑|Zk|=∑c1(aj).gj=1nk=1∵∑Sjk=c1(aj),∑Sjk=|Zk|,设在G作用下，[1,n]分成l个等价类。[1,n]=E1+E2+…+El.gj=1nk=1第29页4.4Burnside引理若j,i同属一个等价类，则Ei=Ej,|Ei|=|Ej|因|Ei||Zi|=|G|,故|Zi|=|Zj|. ∑|Zi|=|Ej||Zj|

（由上式得）i∈Ej第30页4.4Burnside引理例2一正方形分成4格，2着色，有多少种方案？图象：看上去不一样图形。方案：经过转动相同图象算同一方案。图象数总是大于方案数。12345678910111213141516第31页4.4Burnside引理不动：p1=(1)(2)…(16)逆时针转90：p2=(1)(2)(3456)(78910) (1112)(13141516)顺时针转90：p3=(1)(2)(6543)(10987) (1112)(16151413)转180：p4=(1)(2)(35)(46)(79)(810) (11)(12)(1315)(1416)着色方案数就是不一样等价类个数:(16+2+2+4)/4=6(种方案)。。。第32页4.5Pólya定理设Ω=[1,n],M={S1,S2,…Sm}是m种颜色集合，对Ω中元素用M中颜色着色，得到图象集适用M表示，每个中元素都有m种着色可能，n个元着色有m种可能。即共有m个图象。设G是以Ω为目标置换群，是某一转动群R表示。G是以M为目标置换群，是同一转动群R表示。（区分）ΩΩΩnn第33页4.5Pólya定理G≌R,G≌R，G≌G 一个着色图象在G作用下变为另一个图象，则这两个图象属于同一方案。Pólya定理设G={P1,P2,…,Pg}是Ω上一个置换群，C(Pk)是置换Pk循环个数，用M中颜色对Ω中元着色，着色方案数为第34页4.5Pólya定理在Pi作用下M中不动图象个数C1(Pi)=m，C(Pi)表示Pi循环个数，即同一循环中元素都着同一个颜色图象在Pi作用下保持不变。对应于P∈G,有P∈G,P是M(图象集)上一个置换。现在要计算也就是图象集在G作用下等价类个数。下面对前例进行分析，然后推导到普通。ΩC(Pi)Ω第35页4.5Pólya定理P1=(1)(2)(3)(4),P1=(1)(2)…(16)P2=(4321),P2=(1)(2)(3456)(78910)(1112)(13141516)

P3=(1234),P3=(1)(2)(6543)(10987)(1112)(16151413)

P4=(13)(24),P4=(1)(2)(35)(46)(79)(810)(11)(12)(1315)(1416)

C(P1)=4,C1(P1)=16=2C(P2)=1,C1(P2)=2=2C(P3)=1,C1(P3)=2=2C(P4)=2,C1(P4)=4=2求着色方案数也即求图象等价类个数。按Burside定理，求等价类个数归结为每个置换下不动点(不动图象)个数。C(P1)C(P2)C(P3)C(P4)2134第36页4.5Pólya定理证对Ωn个目标用m种颜色着色图象集为M|M|=|M|=mG每一个元Pi是Ω上一个置换，也对应了M上一个置换Pi,这么G≌G,T:Pi←→Pi在Pi作用下不动图象个数C1(Pi)等于Pi同一循环中目标都着相同色选择个数。即C1(Pi)=m。因而在G作用下，M(图象)等价类个数。 Ω|Ω|ΩΩnC(Pi)Ω第37页4.6举例例1等边三角形3个顶点用红，兰，绿3着色，有多少种方案？ 解在3维空间考虑，3顶点置换群S3. (3):2个； (1)(2):3个； (1):1个； l=(2·3+3·3+3)/6=101311123第38页4.6举例例2甲烷CH44个键任意用H,Cl,CH3,C2H5连接，有多少种方案？ 解

CH4结构是一个正4面体，C原子居于正4面体中心。正4面体转动群按转动轴分类：顶点-对面中心：(1)(3)8个；棱中-棱中：(2)（2）3个；不动：(1)1个；6条棱,每条棱看作一有向边，正向重合与反向重合共6·2=12个位置，故转动群群元有12个。l=[11·4+4]/12=[44+64]/3=36。24第39页4.6举例例3

正6面体6个面分别用红，蓝两种颜色着色，有多少方案？ 正6面体转动群用面置换表示：面心-面心±90(1)(4)6个 180(1)(2)3个顶点-顶点±120(3)8个棱中-棱中