組合數(shù)學(xué)幻燈片63

1§6.3

Burnside引理Burnside引理可以用來(lái)解決某些簡(jiǎn)單的計(jì)數(shù)問(wèn)題，我們主要它來(lái)證明下一節(jié)的Polya定理。2一、等價(jià)關(guān)系與等價(jià)類(lèi)令<a,b>表示一對(duì)有順序的元素a和b，稱(chēng)為有序?qū)?。一些有序?qū)?gòu)成的集合稱(chēng)為一個(gè)關(guān)系。設(shè)R是一個(gè)關(guān)系，若對(duì)<a,b>∈R均有a,b∈A，則稱(chēng)R為集合A上的一個(gè)關(guān)系。 設(shè)A={1,2,3,4},R1={<1，1>，<2，1><3，4>}是A上的一個(gè)關(guān)系。又設(shè)R2為A上小于關(guān)系，則R2={<a,b>|a,b∈A且a＜b}={<1,2>,<1,3>,<1,4>,<2,3>,<2,4>,<3,4>}。3等價(jià)關(guān)系若對(duì)x∈A有<x,x>∈R，則稱(chēng)R具有自反性。若對(duì)x,y∈A，當(dāng)<x,y>∈R時(shí)必有<y,x>∈R，則稱(chēng)R具有對(duì)稱(chēng)性。若對(duì)x,y,z∈A，當(dāng)<x,y>,<y,z>∈R時(shí)，必有<x,z>∈R，則稱(chēng)R具有傳遞性。A上同時(shí)具有自反性、對(duì)稱(chēng)性和傳遞性的關(guān)系稱(chēng)為A上等價(jià)關(guān)系。設(shè)R是集合A上的一個(gè)關(guān)系：實(shí)數(shù)集上的等于關(guān)系“=”，三角形集合上的三角形“相似”關(guān)系，人的集合上的“同姓”關(guān)系均為等價(jià)關(guān)系。4等價(jià)類(lèi)設(shè)R是集合A上的等價(jià)關(guān)系，a∈A,稱(chēng)[a]={x|x∈A且<a,x>∈R}為a關(guān)于R的等價(jià)類(lèi)，簡(jiǎn)稱(chēng)含a的等價(jià)類(lèi)，a稱(chēng)為代表元。5定理6.11[a]≠φ；a∈[b][a]=[b]；a[b][a]∩[b]=φ設(shè)R是集合A上的等價(jià)關(guān)系，對(duì)a,b∈A，有定理的證明從略，其正確性可從上例驗(yàn)證。由定理6.11可知集合A上關(guān)于R的所有等價(jià)類(lèi)構(gòu)成的集合是A的一個(gè)劃分，即將A分為一些互不相交的非空子集，這些子集的并為A。6二、Burnside引理設(shè)G是M上的置換群，令R={<a,σ(a)>|a∈M,σ∈G} (6.5)稱(chēng)R為G誘導(dǎo)的M上的關(guān)系。7定理6.12由置換群G誘導(dǎo)的M上的關(guān)系R是M上的等價(jià)關(guān)系。證明：對(duì)a∈M,有恒等置換I(G的幺元)∈G，使I(a)=a,故<a,a>∈R，這表明R有自反性。對(duì)a,b∈M,若<a,b>∈R，則σ∈G,使σ(a)=b，因此σ-1(b)=a，即<b,a>∈R，這表明R有對(duì)稱(chēng)性。對(duì)a,b,c∈M,若<a,b>,<b,c>∈R,則σ,τ∈G，使σ(a)=b,τ(b)=c，從而τσ(a)=τ(σ(a))=τ(b)=c，即<a,c>∈R(因G有封閉性，τσ∈G)，這表明R有傳遞性。綜上，R是M上等價(jià)關(guān)系。■8軌道對(duì)(6.5)式表達(dá)的等價(jià)關(guān)系R，取a∈M，則含a的等價(jià)類(lèi)為[a]={x|x∈M,<a,x>∈R}={x|x=τ(a),τ∈G}[a]也稱(chēng)a在G作用下的“軌道”。例3設(shè)G={(1),(12),(34),(12)(34)}是{1,2,3,4}上的置換群，求“軌道”。解：[1]=[2]={1,2},[3]=[4]={3,4}設(shè)G是集合M上的置換群，取a∈M，令Ga={τ|τ(a)=a,τ∈G}即Ga是G中使a不動(dòng)的置換的集合。例如對(duì)例3中的G，有

G1={(1),(34)}, G2={(1),(34)}, G3={(1),(12)}, G4={(1),(12)}。9定理6.13設(shè)G是M上的置換群，a∈M,則Ga為G的子群。Ga稱(chēng)為a的穩(wěn)定子群。證明：因?qū)愕戎脫QI，有I(a)=a,故I∈Ga,這表明Ga≠φ。對(duì)σ,τ∈Ga,則有σ(a)=a,τ(a)=a,故στ(a)＝σ(τ(a))＝σ(a)＝a,所以στ∈Ga。因G是有限群，由定理6.4知Ga是G的子群?！龊琣的等價(jià)類(lèi)[a]，a的穩(wěn)定子群Ga與G有下列關(guān)系。10定理6.14設(shè)G是M上的置換群，對(duì)a∈M,|G|＝|[a]|·|Ga|。證明：設(shè)|[a]|=k，不妨設(shè)[a]={b1(=a),b2,…,bk}由[a]的定義，存在G中k個(gè)元τ1，τ2，…，τk有τi(a)=bi,i=1,2,…,k令τiGa={τiσ|σ∈Ga},i=1,2,…,k則當(dāng)i≠j時(shí),τiGa∩τjGa＝φ。否則，若τiGa∩τjGa≠φg∈τiGa∩τjGag∈τiGa且g∈τjGaσ′,σ″∈Ga，有g(shù)=τiσ′且g=τjσ″11證明τiσ′=τjσ″τiσ′(a)=τjσ″(a)τi(σ′(a))=τj(σ″(a))τi(a)=τj(a)bi=bj，矛盾。顯然

τ1Ga∪τ2Ga∪…∪τkGaG (6.6A)另一方面，τ∈G，有τ(a)∈[a]，故對(duì)某一j有τ(a)=bj,于是

τj(a)=bj=τ(a)τ-1j(τj(a))=τ-1j(τ(a))τ-1jτj(a)=τ-1jτ(a)τ-1jτ(a)=aτ-1jτ∈Gaτ=(τjτ-1j)τ=τj(τ-1jτ)∈τjGaτ∈τ1Ga∪τ2Ga∪…∪τkGa12證明(續(xù))所以 Gτ1Ga∪τ2Ga∪…∪τkGa

(6.6B)由(66A)與(66B)得G＝τ1Ga∪τ2Ga∪…∪τkGa對(duì)任意的τiGa及任意的τiσ′，τiσ″∈τiGa,當(dāng)σ′≠σ″時(shí)，因消去律成立，故τiσ′≠τiσ″，因而|τiGa|=|Ga|。再考慮到i≠j時(shí)τiGa∩τjGa＝φ，所以

|G|＝|τ1Ga∪τ2Ga∪…∪τkGa|

＝|τ1Ga|+|τ2Ga|+…+|τkGa|

＝k|Ga|＝|[a]|·|Ga|?！?3定理6.15(Burnside引理)設(shè)G是集合M上的置換群，t為G誘導(dǎo)的M上的等價(jià)類(lèi)的個(gè)數(shù)，則其中c1()為置換中的1-循環(huán)個(gè)數(shù)。14證明：令T={<τ，a>|τ∈G,a∈M,τ(a)=a},可用兩種方法計(jì)算|T|。方法1：因?qū)γ總€(gè)置換τ，使τ(a)=a的a的個(gè)數(shù)，即為c1(τ)，這表明對(duì)這個(gè)τ，有c1(τ)個(gè)有序?qū)Α处?a〉，當(dāng)τ取遍G時(shí)，即得(6.7)方法2：因?qū)γ總€(gè)a∈M，使τ(a)=a的τ的集合，即為Ga，故對(duì)這個(gè)a，使τ(a)=a的τ的個(gè)數(shù)為|Ga|，即有|Ga|個(gè)有序?qū)Α处?a〉，當(dāng)a取遍M時(shí)，即得(6.8)15證明(續(xù)1)由(6.7)，(6.8)得由假設(shè)M可分解為t個(gè)不同的等價(jià)類(lèi)，設(shè)為[a1],[a2],…,[at]。于是M=[a1]∪[a2]∪…∪[at]再由定理6.11，

a∈[aj][a]=[aj]|[a]|=|[aj]| |[aj]|·|Ga|=|[a]|·|Ga|=|G|(定理6.14)故(6.9)(6.10)16證明(續(xù)2)從而有這樣?！龆ɡ?.14所提到的等價(jià)類(lèi)，可簡(jiǎn)稱(chēng)為G導(dǎo)出的等價(jià)類(lèi)。

17例4設(shè)G={τ1,τ2,τa3,τ4}是M={1,2,3,4}上的置換群，其中τ1=(1),τ2=(a13),τ3=(24),τ4=(13)(24),求G導(dǎo)出的等價(jià)類(lèi)的個(gè)數(shù)。解：因τ1=(1)=(1)(2)(3)(4)，即τ1中有4個(gè)1-循環(huán)，故c1(τ1)=4;類(lèi)似地,c1(τ2)=c1(τ3)=2，c1(τ4)=0。由定理6.15，等價(jià)類(lèi)個(gè)數(shù)t=[c1(τ1)+c1(τ2)+c1(τ3)+c1(τ4)]/|G| =(4+2+2)/4=2實(shí)際上這兩個(gè)等價(jià)類(lèi)即{1，3}與{2，4}。18三、應(yīng)用在組合計(jì)數(shù)問(wèn)題中，若被計(jì)數(shù)的對(duì)象經(jīng)某類(lèi)變換能使之重合的算一種，即存在置換σ，對(duì)象a與σ(a)算一種，此類(lèi)問(wèn)題常常歸結(jié)為求不同等價(jià)類(lèi)的個(gè)數(shù)的問(wèn)題。故可用Burnside引理求解。19例5一正三角形被均分為三個(gè)小三角形，如圖所示，現(xiàn)用黑、白二色對(duì)其小三角形著色，問(wèn)能得到多少不同的圖像?經(jīng)旋轉(zhuǎn)能使之重合的圖像算一種。20解：若不允許旋轉(zhuǎn)，因每個(gè)小三角形均可著二色，三個(gè)小三角形共有8種著色方案，故可得8種不同的圖像。如圖所示。21解(續(xù)1)若允許旋轉(zhuǎn)，則經(jīng)旋轉(zhuǎn)后某些圖像可重合，故只算一種，如將以上所列的8種圖像作成一個(gè)集合，M={1,2,…,8}。建立由三角形繞中心反時(shí)針旋轉(zhuǎn)而引出的M中的元的置換如下。22解(續(xù)2)不動(dòng)的置換I，即旋轉(zhuǎn)0°有I=(1)(2)(3)(4)(5)(6)(7)(8)旋轉(zhuǎn)120°。此時(shí)8種圖像中1→1,2→3,3→4,4→2,5→6,6→7,7→5,8→8。故此置換為σ=(1)(234)(567)(8)旋轉(zhuǎn)240°。此時(shí)，1→1,2→4,4→3,3→2,5→7,7→6,6→5,8→8，即此置換為τ=(1)(243)(576)(8)23解(續(xù)3)設(shè)G={I,σ,τ}，因G包含所有旋轉(zhuǎn)變換所導(dǎo)出的置換，故G中元對(duì)置換的乘法封閉，從而是有限群S8(8次對(duì)稱(chēng)群)的子群。易知c1(I)=8,c1(σ)=2,c1(τ)=2,|G|=3,故由Burnside引理，G導(dǎo)出的等價(jià)類(lèi)個(gè)數(shù)為t=(8+2+2)/3=4所以有4種不同的圖像，如圖所示。a24例6在一張卡片上打印一個(gè)由數(shù)字0，1，6，8，9組成的4位碼。如果一個(gè)碼倒轉(zhuǎn)過(guò)來(lái)是另一個(gè)碼，例如0668與8990，則這兩個(gè)碼使用一張卡片。問(wèn)共需多少?gòu)埧ㄆ?。解：?，1，6，8，9組成的4位碼共54=625個(gè)，分別設(shè)為x1,x2,…x625,令M={x1,x2,…,x625}。一個(gè)碼倒轉(zhuǎn)過(guò)來(lái)成另一個(gè)碼相當(dāng)于將碼繞中點(diǎn)轉(zhuǎn)180°，建立由這類(lèi)變換而引出的M中的元的置換如下。不動(dòng)的置換I，即I=(x1)(x2)…(x625),有c1(I)=62525繞中點(diǎn)轉(zhuǎn)180°，記為σ。因當(dāng)且僅當(dāng)xi中第一位與第四位的數(shù)字互為倒轉(zhuǎn)相