组合数学幻灯片63

1§6.3

Burnside引理Burnside引理可以用来解决某些简单的计数问题，我们主要它来证明下一节的Polya定理。2一、等价关系与等价类令<a,b>表示一对有顺序的元素a和b，称为有序对。一些有序对构成的集合称为一个关系。设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上的一个关系：实数集上的等于关系“=”，三角形集合上的三角形“相似”关系，人的集合上的“同姓”关系均为等价关系。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的所有等价类构成的集合是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上等价关系。■8轨道对(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的稳定子群。证明：因对恒等置换I，有I(a)=a,故I∈Ga,这表明Ga≠φ。对σ,τ∈Ga,则有σ(a)=a,τ(a)=a,故στ(a)＝σ(τ(a))＝σ(a)＝a,所以στ∈Ga。因G是有限群，由定理6.4知Ga是G的子群。■含a的等价类[a]，a的稳定子群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=τ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证明(续)所以 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|。■13定理6.15(Burnside引理)设G是集合M上的置换群，t为G诱导的M上的等价类的个数，则其中c1()为置换中的1-循环个数。14证明：令T={<τ，a>|τ∈G,a∈M,τ(a)=a},可用两种方法计算|T|。方法1：因对每个置换τ，使τ(a)=a的a的个数，即为c1(τ)，这表明对这个τ，有c1(τ)个有序对〈τ,a〉，当τ取遍G时，即得(6.7)方法2：因对每个a∈M，使τ(a)=a的τ的集合，即为Ga，故对这个a，使τ(a)=a的τ的个数为|Ga|，即有|Ga|个有序对〈τ,a〉，当a取遍M时，即得(6.8)15证明(续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证明(续2)从而有这样。■定理6.14所提到的等价类，可简称为G导出的等价类。

17例4设G={τ1,τ2,τa3,τ4}是M={1,2,3,4}上的置换群，其中τ1=(1),τ2=(a13),τ3=(24),τ4=(13)(24),求G导出的等价类的个数。解：因τ1=(1)=(1)(2)(3)(4)，即τ1中有4个1-循环，故c1(τ1)=4;类似地,c1(τ2)=c1(τ3)=2，c1(τ4)=0。由定理6.15，等价类个数t=[c1(τ1)+c1(τ2)+c1(τ3)+c1(τ4)]/|G| =(4+2+2)/4=2实际上这两个等价类即{1，3}与{2，4}。18三、应用在组合计数问题中，若被计数的对象经某类变换能使之重合的算一种，即存在置换σ，对象a与σ(a)算一种，此类问题常常归结为求不同等价类的个数的问题。故可用Burnside引理求解。19例5一正三角形被均分为三个小三角形，如图所示，现用黑、白二色对其小三角形着色，问能得到多少不同的图像?经旋转能使之重合的图像算一种。20解：若不允许旋转，因每个小三角形均可着二色，三个小三角形共有8种着色方案，故可得8种不同的图像。如图所示。21解(续1)若允许旋转，则经旋转后某些图像可重合，故只算一种，如将以上所列的8种图像作成一个集合，M={1,2,…,8}。建立由三角形绕中心反时针旋转而引出的M中的元的置换如下。22解(续2)不动的置换I，即旋转0°有I=(1)(2)(3)(4)(5)(6)(7)(8)旋转120°。此时8种图像中1→1,2→3,3→4,4→2,5→6,6→7,7→5,8→8。故此置换为σ=(1)(234)(567)(8)旋转240°。此时，1→1,2→4,4→3,3→2,5→7,7→6,6→5,8→8，即此置换为τ=(1)(243)(576)(8)23解(续3)设G={I,σ,τ}，因G包含所有旋转变换所导出的置换，故G中元对置换的乘法封闭，从而是有限群S8(8次对称群)的子群。易知c1(I)=8,c1(σ)=2,c1(τ)=2,|G|=3,故由Burnside引理，G导出的等价类个数为t=(8+2+2)/3=4所以有4种不同的图像，如图所示。a24例6在一张卡片上打印一个由数字0，1，6，8，9组成的4位码。如果一个码倒转过来是另一个码，例如0668与8990，则这两个码使用一张卡片。问共需多少张卡片。解：由0，1，6，8，9组成的4位码共54=625个，分别设为x1,x2,…x625,令M={x1,x2,…,x625}。一个码倒转过来成另一个码相当于将码绕中点转180°，建立由这类变换而引出的M中的元的置换如下。不动的置换I，即I=(x1)(x2)…(x625),有c1(I)=62525绕中点转180°，记为σ。因当且仅当xi中第一位与第四位的数字互为倒转相