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

1§6.3

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

G1={(1),(34)}, G2={(1),(34)}, G3={(1),(12)}, G4={(1),(12)}。9定理6.13設G是M上的置換群，a∈M,則Ga為G的子群。Ga稱為a的穩(wěn)定子群。證明：因?qū)愕戎脫QI，有I(a)=a,故I∈Ga,這表明Ga≠φ。對σ,τ∈Ga,則有σ(a)=a,τ(a)=a,故στ(a)＝σ(τ(a))＝σ(a)＝a,所以στ∈Ga。因G是有限群，由定理6.4知Ga是G的子群。■含a的等價類[a]，a的穩(wěn)定子群Ga與G有下列關系。10定理6.14設G是M上的置換群，對a∈M,|G|＝|[a]|·|Ga|。證明：設|[a]|=k，不妨設[a]={b1(=a),b2,…,bk}由[a]的定義，存在G中k個元τ1，τ2，…，τk有τi(a)=bi,i=1,2,…,k令τiGa={τiσ|σ∈Ga},i=1,2,…,k則當i≠j時,τ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]，故對某一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對任意的τiGa及任意的τiσ′，τiσ″∈τiGa,當σ′≠σ″時，因消去律成立，故τiσ′≠τiσ″，因而|τiGa|=|Ga|。再考慮到i≠j時τiGa∩τjGa＝φ，所以

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

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

＝k|Ga|＝|[a]|·|Ga|?！?3定理6.15(Burnside引理)設G是集合M上的置換群，t為G誘導的M上的等價類的個數(shù)，則其中c1()為置換中的1-循環(huán)個數(shù)。14證明：令T={<τ，a>|τ∈G,a∈M,τ(a)=a},可用兩種方法計算|T|。方法1：因?qū)γ總€置換τ，使τ(a)=a的a的個數(shù)，即為c1(τ)，這表明對這個τ，有c1(τ)個有序?qū)Α处?a〉，當τ取遍G時，即得(6.7)方法2：因?qū)γ總€a∈M，使τ(a)=a的τ的集合，即為Ga，故對這個a，使τ(a)=a的τ的個數(shù)為|Ga|，即有|Ga|個有序?qū)Α处?a〉，當a取遍M時，即得(6.8)15證明(續(xù)1)由(6.7)，(6.8)得由假設M可分解為t個不同的等價類，設為[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所提到的等價類，可簡稱為G導出的等價類。

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