組合數(shù)學(4)省公開課一等獎全國示范課微課金獎?wù)n件

第四章Pólya定理群概念置換群循環(huán)、奇循環(huán)與偶循環(huán)Burnside引理Pólya定理例母函數(shù)型Pólya定理圖計數(shù)第1頁Review:義11設(shè)(A；*)是一個代數(shù)系統(tǒng)，假如*是可結(jié)合，而且A中有單位元，而且A中任意一個元素都有逆元，則稱(A；*)是一個群。在運算“*”已知情況下，群(A；*)能夠簡記為A。由群定義能夠知道，一個代數(shù)系統(tǒng)(A；*)是群，則應(yīng)滿足以下條件：(1)(A；*)是可結(jié)合。即：(A；*)是一個半群。(2)(A；*)中有單位元e。(3)(A；*)中，任何一個元素都有逆元。假如一個群滿足交換律，則此群稱為交換群，也稱作阿貝爾(Abel)群(或加法群)。4/13/202410:01PM2第2頁4/13/202410:01PMZhangSanyuan,ZhejiangUniv.3拉格朗日定理定理：設(shè)<H,*>是群<G,*>一個子群。那么：是G一個等價關(guān)系，記2。假如G是有限群，|G|=n,|H|=m,則m|n。第3頁4/13/202410:01PMZhangSanyuan,ZhejiangUniv.4推論1：任何質(zhì)數(shù)階群不可能有非平凡子群。推論2：<G,*>n階有限群。那么對任意a∈G,a階必為n因子且必有。這里e為單位元。假如n為質(zhì)數(shù)，<G,*>必為循環(huán)群。第4頁4.2置換群置換群是最主要有限群，全部有限群都能夠用之表示。置換：[1,n]到本身1-1變換。n階置換。[1,n]目標集。(),a1a2…an是[1,n]中元一個排列。n階置換共有n!個，同一置換用這么表示可有n!個表示法。比如p1=()=()，n階置換又可看作[1,n]上一元運算，一元函數(shù)。12…na1a2…an1234312431422341第5頁4.2置換群置換乘法P1=(),P2=() P1P2=()()=() 注意：既然先做P1置換，再做P2置換就要求了若作為運算符或函數(shù)符應(yīng)是后置。這與普通習慣前置不一樣。P2P1≠P1P2.1234312412343124123443213124243112342431第6頁4.2置換群(1)置換群 [1,n]上全部n階置換在上面乘法定義下是一個群。 (a)封閉性()()=()(b)可結(jié)合性(()())()=()=()(()())(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)例等邊三角形運動群。 繞中心轉(zhuǎn)動120，不動， 繞對稱軸翻轉(zhuǎn)。P1=(),P2=(),P3=(),P4=(),P5=(),P6=()。 [1,n]上全部置換(共n!個)組成一個群，稱為對稱群，記做Sn. 注意：普通說[1,n]上一個置換群，不一定是指Sn.但一定是Sn某一個子群。123123123231123312123132123321123213123第8頁4.2置換群任一n階有限群同構(gòu)于一個n個文字置換群。兩個群同構(gòu)：存在一個雙射。且同態(tài)。第9頁4.2置換群設(shè)G={a1,a2,…,an}，指定G中任一元ai,任意aj∈G，Pi：aj→ajai，則Pi是G上一個置換，即以G為目標集。令Pi=()，a1a2…ana1aia2ai…anaiPi是單射：ai≠aj，則Pi≠Pj.Pi同態(tài)：

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循環(huán)、奇循環(huán)與偶循環(huán)(a1a2…am)=(

)

稱為置換循環(huán)表示。于是(

)=(14523),(

)=(132)(45),(

)=(154)(2)(3).(a1a2…am)=(a2a3…ama1)=…=(ama1…am-1)有m種表示方法。a1a2…am-1ama2a3…ama1123454315212345312541234552314第12頁4.3循環(huán)、奇循環(huán)與偶循環(huán)若兩個循環(huán)無共同文字，稱為不相交，不相交循環(huán)相乘可交換。如(132)(45)=(45)(132).若p=(a1a2…am),則p=(1)(2)…(n)=e.（拉格朗日定理推論）定理任一置換可表成若干不相交循環(huán)乘積。證對給定任一置換，

從1開始搜索1→ai1→ai2→ai3→…→aik→1得一循環(huán)(1ai1

ai2…aik),若(1ai1

…aik)包含nppppp第13頁4.3循環(huán)、奇循環(huán)與偶循環(huán)了[1,n]全部文字，則命題成立。不然在余下文字中選一個，繼續(xù)搜索,又得一循環(huán)。直到全部文字都屬于某一循環(huán)為止。因不相交循環(huán)可交換，故除了各個循環(huán)次序外，任一置換都有唯一循環(huán)表示。2階循環(huán)叫做對換第14頁4.3循環(huán)、奇循環(huán)與偶循環(huán)定理任一循環(huán)都能夠表示為對換積。(12…n)=(12)(13)…(1n)=(23)(24)…(2n)(21)表示不唯一。任一置換表示成對換個數(shù)奇偶性是唯一。置換分成兩大類：奇置換與偶置換。第15頁4.3循環(huán)、奇循環(huán)與偶循環(huán)定理Sn中全部偶置換組成一階為(n!)/2子群稱為交織群，記做An. 證(1)封閉性 (2)單位元 (3)逆元(ik)=(ik)

設(shè)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循環(huán)格式(1)(2)…(n), ∑kCk=

nSn中有相同格式置換全體組成一個共軛類。定理1

Sn中屬(1)(2)…(n)共軛類元個數(shù)為C1C2Cnnk=1C1C2Cn

n！C1!C2!…Cn!12…nC1C2Cn第18頁4.4Burnside引理證(1)(2)…(n)即C1C2Cn(·)…(·)(··)…(··)…(·…·)…(·…·)_∧_/\1個_∧_/\2個____∧____/\n個\____________/\/C1個\________________/\/C2個\________________/\/Cn個一個長度為k循環(huán)有k種表示，Ck個長度為k循環(huán)有Ck!k種表示.1,2,…,n全排列共有n!個，給定一個排列，裝入格式得一置換，除以前面重復(fù)度得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不動置換類 設(shè)G是[1,n]上一個置換群。G≤Sn.K∈[1,n]G中使k保持不變置換全體，稱為k不動置換類，記做Zk.第20頁4.4Burnside引理定理置換群Gk不動置換類Zk是G一個子群。 封閉性：k→k→k,kk. 結(jié)合性：自然。 有單位元：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定義關(guān)系k： 若存在p∈G,使得k→j則稱kRj.顯然kRk；kRj則jRk；kRj,jRl則kRl。R是[1,n]上一個等價關(guān)系。將[1,n]劃分成若干等價類。含目標集元素k在G作用下等價類也稱為含k軌道。p第23頁4.4Burnside引理定理設(shè)G是[1,n]上一個置換群，Ek是[1,n]在G作用下包含k等價類(軌道)，Zk是k不動置換類。有|Ek||Zk|=|G|. 證設(shè)|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關(guān)于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引理 設(shè)G={a1,a2,…ag}是目標集[1,n]上置換群。每個置換都寫成不相交循環(huán)乘積。G將[1,n]劃分成若干個等價類。C1(ak)是在置換ak作用下不動點個數(shù)，也就是長度為1循環(huán)個數(shù)。Burnside引理設(shè)G={a1,a2,…ag}是目標集[1,n]上置換群，則G在N上引出不一樣等價類個數(shù)為 =[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|,設(shè)在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著色，有多少種方案？圖象：看上去不一樣圖形。方案：經(jīng)過轉(zhuǎn)動相同圖象算同一方案。圖象數(shù)總是大于方案數(shù)。12345678910111213141516第31頁4.4Burnside引理不動：p1=(1)(2)…(16)逆時針轉(zhuǎn)90：p2=(1)(2)(3456)(78910) (1112)(13141516)順時針轉(zhuǎn)90：p3=(1)(2)(6543)(10987) (1112)(16151413)轉(zhuǎn)180：p4=(1)(2)(35)(46)(79)(810) (11)(12)(1315)(1416)著色方案數(shù)就是不一樣等價類個數(shù):(16+2+2+4)/4=6(種方案)。。。第32頁4.5Pólya定理設(shè)Ω=[1,n],M={S1,S2,…Sm}是m種顏色集合，對Ω中元素用M中顏色著色，得到圖象集適用M表示，每個中元素都有m種著色可能，n個元著色有m種可能。即共有m個圖象。設(shè)G是以Ω為目標置換群，是某一轉(zhuǎn)動群R表示。G是以M為目標置換群，是同一轉(zhuǎn)動群R表示。（區(qū)分）ΩΩΩnn第33頁4.5Pólya定理G≌R,G≌R，G≌G 一個著色圖象在G作用下變?yōu)榱硪粋€圖象，則這兩個圖象屬于同一方案。Pólya定理設(shè)G={P1,P2,…,Pg}是Ω上一個置換群，C(Pk)是置換Pk循環(huán)個數(shù)，用M中顏色對Ω中元著色，著色方案數(shù)為第34頁4.5Pólya定理在Pi作用下M中不動圖象個數(shù)C1(Pi)=m，C(Pi)表示Pi循環(huán)個數(shù)，即同一循環(huán)中元素都著同一個顏色圖象在Pi作用下保持不變。對應(yīng)于P∈G,有P∈G,P是M(圖象集)上一個置換?，F(xiàn)在要計算也就是圖象集在G作用下等價類個數(shù)。下面對前例進行分析，然后推導(dǎo)到普通。Ω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求著色方案數(shù)也即求圖象等價類個數(shù)。按Burside定理，求等價類個數(shù)歸結(jié)為每個置換下不動點(不動圖象)個數(shù)。C(P1)C(P2)C(P3)C(P4)2134第36頁4.5Pólya定理證對Ωn個目標用m種顏色著色圖象集為M|M|=|M|=mG每一個元Pi是Ω上一個置換，也對應(yīng)了M上一個置換Pi,這么G≌G,T:Pi←→Pi在Pi作用下不動圖象個數(shù)C1(Pi)等于Pi同一循環(huán)中目標都著相同色選擇個數(shù)。即C1(Pi)=m。因而在G作用下，M(圖象)等價類個數(shù)。 Ω|Ω|ΩΩ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結(jié)構(gòu)是一個正4面體，C原子居于正4面體中心。正4面體轉(zhuǎn)動群按轉(zhuǎn)動軸分類：頂點-對面中心：(1)(3)8個；棱中-棱中：(2)（2）3個；不動：(1)1個；6條棱,每條棱看作一有向邊，正向重合與反向重合共6·2=12個位置，故轉(zhuǎn)動群群元有12個。l=[11·4+4]/12=[44+64]/3=36。24第39頁4.6舉例例3

正6面體6個面分別用紅，藍兩種顏色著色，有多少方案？ 正6面體轉(zhuǎn)動群用面置換表示：面心-面心±90(1)(4)6個 180(1)(2)3個頂點-頂點±120(3)8個棱中-棱中