組合數(shù)學(xué)課件：群

群6.1群（group）

6.2置換群

6.3群同態(tài)、群同構(gòu)

6.4置換中的輪換

6.5Polya定理

6.6生成函數(shù)型的Polya定理6.1群(group)

定義1

代數(shù)系統(tǒng)（G，*）若滿足以下條件：

(1)結(jié)合律：對(duì)a,b,c∈G，(a*b)*c=a*(b*c)；

(2)幺元：e∈G，使對(duì)a∈G，e*a=a*e=a；

(3)逆元：對(duì)G中幺元e及a∈G，a-1∈G使a-1*a=a*a-1=e，則稱（G，*）為群。為醒目起見(jiàn)，群中特異元素e及求逆也常特別寫(xiě)出，如（G，*）又可記為（G，*，e)。(G，

*）之稱謂代數(shù)系統(tǒng)是指對(duì)a,b∈G，有a*b∈G，即G中元素在運(yùn)算“*”作用下保持封閉性。顯見(jiàn)正整數(shù)連同其上的加法運(yùn)算構(gòu)成一代數(shù)系統(tǒng),正整數(shù)在減法運(yùn)算下不構(gòu)成代數(shù)系統(tǒng)。又若僅有(1)成立時(shí)，稱代數(shù)系統(tǒng)（G，*）為半群（semigroup）；若有(2)，(3)同時(shí)成立，稱（G，*）為單子（monoid），或稱幺半群、獨(dú)異點(diǎn)。此外，因結(jié)合律能保證左逆元就是右逆元，右逆元就是左逆元，故條件(3)常改為對(duì)a∈G，a有左逆或a有右逆。當(dāng)G為有限集時(shí)，稱（G，*）為有限群；若G為無(wú)限集，則稱（G，*）為無(wú)限群。有限群中G的基數(shù)|G|常稱為群的階數(shù)。

定義2

設(shè)（G，*）為群，若對(duì)a*b∈G，a*b=b*a成立，則稱（G，*）為abel群。

例1

設(shè)Z為整數(shù)集，+、-、×、/分別為一般的加、減、乘、除法運(yùn)算，則（Z

，+）為群，且因交換律成立，（Z

，+）又是abel群。（Z

，-），Z

，×），（Z

，/）均不成其為群，原因是：減法運(yùn)算不能保持Z中元素的結(jié)合律。對(duì)乘法運(yùn)算，特異元素0∈Z（稱為零元）不存在逆元；而對(duì)除法，連封閉性都不能保證。故（Z

，-）僅為代數(shù)系統(tǒng)，（Z

，×）可為單子，（Z

，/）連代數(shù)系統(tǒng)都不是。

例2設(shè)（

Q+，×）為正有理數(shù)集及定義在其上的乘法運(yùn)算所成之二元組，則（Q+

，*）為abel群。

例3設(shè)X為任意集合，P（x）表示X上的全部雙射函數(shù)，“”為P（x）中元素的合成運(yùn)算，幺函數(shù)IX（x∈X，IX（x）=x）為P（x）中的幺元，則（P（x），。，

IX）為群。一般來(lái)說(shuō)（P（x），。，

IX

）不具交換性。

例4設(shè)Nk={0，1，…，k-1},+k,×k分別為定義在Nk上的模k加法及模k乘法運(yùn)算，即對(duì)i,j∈Nk

，有i+kj≡(i+j)modk;i×kj≡(i×j)modk則(Nk

，+k)為群，(Nk

，×k)不成其為群的原因是Nk中的乘法零元“0”無(wú)逆。順便指出，基數(shù)大于1的代數(shù)系統(tǒng)若有零元，則必不為群。

命題1

設(shè)（G，*）為群，則對(duì)a,b∈G

(1)！x∈G，使a*x=b；

(2)！y∈G，使a*y=b。

證明只證(1)，至少有一個(gè)x滿足(1)，顯見(jiàn)a-1*b∈G能充當(dāng)x。令x=a-1*b，則a*x=a*(a-1*b)=(a*a-1)*b=e*b=b

又設(shè)x∈G∧a*x=b，則x=e*x=(a-1*a)*x=a-1*(a*x)=a-1*b

類似可證(2)。

推論1設(shè)（G，*）為群，則對(duì)

a∈G，有

(1)a*x1=a*x2

x1=x2

（左消律）

(2)y1*a=y2*a

y1=y2

（右消律）其中x1，x2

，y1

，y2∈G。

證明只證(1)，令a*x1=a*x2=b，則由命題1，滿足a*x=b的x是惟一的，立得x1=x2

。同理可證(2)。

推論2群中惟有幺元是冪等元素。證明幺元素冪等顯然,又設(shè)x2=x為G中任一冪等元。則因x2=x*x=x=x*e,由命題1即得x=e。

推論3

群（G，*）的運(yùn)算表中的每一行、每一列都是G中元素的一個(gè)置換。

證明（1）設(shè)G={a1,a2,…},對(duì)a∈G，記運(yùn)算表中對(duì)應(yīng)于a所在的行為Ga={aa1,aa2,…,aai,…,aaj,…}則ai≠aj

a*aj≠a*aj（a*ai=a*aj

ai=aj的逆反命題）。由a的任意性知，G的運(yùn)算表中每一行不會(huì)兩次出現(xiàn)同一元素。（2）對(duì)ak∈G，有ak=a*(a-1*ak)∈Ga，即G中任一元素都出現(xiàn)在Ga中。于是，由（1）及（2）知G的運(yùn)算表中每一行都是G中元素的一個(gè)置換。以上證法對(duì)列亦然。

定義3設(shè)（G，*）為群，A={a1,a2,…}

G，若 ∧對(duì)a∈A，G不能利用A\{a}的元素之乘冪完全表出，則稱A為G的生成集。特別地，當(dāng)A為單元素集{a}時(shí)，稱a為G的生成元，并稱G可由a生成。

定義4

設(shè)（G，*）為群，g∈G為G的生成元，則稱（G，*）為循環(huán)群。

命題2任一循環(huán)群都是Abel群。證明留作練習(xí)題。

命題3設(shè)（G，*）是由g生成的有限循環(huán)群，如果|G|=n，則

(1)gn=e;

(2)G={g,g2,…,gn=e};

(3)不存在m(0<m<n)使gm=e。

證明先證（3），假定m∈Z+∧m<n能使gm=e，則對(duì)gk∈G，k=mg+r(0≤r<m)。于是，gk=gmq+r=(gm)q*gr=gr，這意味著G中任一元素都可寫(xiě)成gr的形式，注意到r<m，故G中至多有m個(gè)不同元素，這與|G|=n矛盾。所以使gm=e∧0<m<n的m不存在。

再證（2），{g,g2,…,gn}中元素互不相同。如若不然，有g(shù)i=gj，不妨設(shè)i<j≤n，于是gj-i=e，但j-i<n，而這是不可能的。注意到（G，*）是群，其中必有幺元，由（3）得gn=e（此即（1）），進(jìn)而有G={g,g2,…,gn=e}

例5(Z，+)為無(wú)限循環(huán)群，其中1或-1都是生成元。例4的（Nk，+k)為k階循環(huán)群。

定義5

設(shè)（G，*）為群，非空S

G且滿足如下條件：

(1）對(duì)a,b∈S,有a*b∈S；

(2)對(duì)a∈S,有a-1∈S；

(3)（G，*）的幺元e∈S則稱（S，*）是（G，*）的子群。子群也是群，因結(jié)合律具有遺傳性，再加（1），2），（3）即知。

事實(shí)上，條件（3）可由（1）及（2）推得，故可取掉。特別地，當(dāng)G為有限集時(shí)，上述定義中只要（1）滿足即可。為此，再給出以下子群的定義：

定義6

設(shè)（G，*）為有限群，非空S

G，若對(duì)a,b∈S，有a*b∈S，則稱（S，*）為（G，*）的子群。

定義7設(shè)（G，*）為群，非空SG，若對(duì)a,b∈S，有a*b∈S，且對(duì)a∈S，有a-1∈S，則稱（S，*）為（G，*）的子群。

命題4定義6、定義7均符合定義5。

證明先證定義6符合定義5。任取a∈S，構(gòu)造序列a,a2,a3,…,a|G|+1，因|G|有限，故序列中必有相同元素，令as=at，不妨設(shè)s<t≤|G|+1。因?yàn)閑=a0=as-s=as*a-s=at*a-s=at-s

注意到t-s≤|G|及(S,*)的封閉性，令k=t-s，即有ak=e∈S，進(jìn)而因ak-1∈Sak*a-1=e*a-1=a-1∈S,故定義6符合定義5。再證定義7也符合定義5。因a,b∈S

a*b∈S,a∈S

a-1∈S，故a∈S

a*a-1=e∈S，即見(jiàn)定義7符合定義5。

例6(N4，+4)的子群有({0},+4),({0,2},+4)及(N4，+4)本身。

例7

設(shè)Z為整數(shù)集，E為偶數(shù)集，則（E，+）為（

Z，+）的子群。6.2置換群

定義1

不失一般性，集合X=(1,2,…,n)到自身的一個(gè)雙射函數(shù)φ:X→X稱為一個(gè)n次置換，記作設(shè)f,g為兩個(gè)n次置換

f和g間的運(yùn)算“?！倍x為f。g(t)=f（g（t））。其結(jié)果仍然是一個(gè)n次置換。f。g=由定義1可見(jiàn)，置換在運(yùn)算“?！钡淖饔孟卤３址忾]。

命題1

設(shè)Sn為X上的全部置換所成之集（|Sn|=n!），則代數(shù)系統(tǒng)(Sn,。)構(gòu)成群，此群常稱為n次n階的對(duì)稱群。

證明結(jié)合律：對(duì)f,g,h∈Sn,有f。(g。

h)=(f。g)。h

這樣，(f。g)。h可以無(wú)混淆的記成f。g。h。幺元：存在幺置換e∈Sn，e(x)=x使對(duì)f∈Sn，有f。e=e。

f=f

逆元：對(duì)f∈Sn，互換f的兩個(gè)行得一置換f-1，顯見(jiàn)f

f-1=f-1。f=e

f－１即為f的逆元。

定義2

若G

Sn∧(G,。)構(gòu)成群，則稱(G,。)為置換群。對(duì)稱群是置換群的一個(gè)特例。置換群一般不具交換性。

例1(二面體群)

考慮正n邊形（各頂點(diǎn)依次標(biāo)以1，2，…，n）上的兩類運(yùn)算，一類是繞重心O（逆時(shí)針）旋轉(zhuǎn)2k

π

/n弧度（k=0,1,…,n-1），可產(chǎn)生n種不同的圖案，對(duì)應(yīng)于X的n個(gè)不同的置換。另一類是當(dāng)n為奇數(shù)時(shí)繞各邊的中垂線翻轉(zhuǎn)180°，或當(dāng)n為偶數(shù)時(shí)繞各對(duì)角線及各對(duì)邊中垂線（共n條）翻轉(zhuǎn)180°。從而無(wú)論n是奇數(shù)還是偶數(shù)，又可產(chǎn)生n種不同的圖案，對(duì)應(yīng)于X的n種不同的置換。不難發(fā)現(xiàn)，以上2n種置換在相繼運(yùn)動(dòng)（旋轉(zhuǎn)或翻轉(zhuǎn)）下構(gòu)成一置換群，這類群常稱為2n階的二面體群。

例2(四面體群)考慮正四面體（各頂點(diǎn)依次標(biāo)以1，2，3，4），任選一頂點(diǎn)，不妨取4，以4與1，2，3面的頂垂線為軸，（逆時(shí)針）旋轉(zhuǎn)2kπ/3弧度（k=0,1,2）可得3種不同的圖案。由于四面體有4個(gè)頂點(diǎn)，故共可產(chǎn)生3×4=12種不同的圖案，這些圖案在以上動(dòng)作（旋轉(zhuǎn)）下構(gòu)成的群稱為四面體群。顯見(jiàn)，四面體群的階是12。類似的還有正六面體、正八面體、正十二面體及正20面體群。

例3(Klein四群)考察圖6.2.1所示的長(zhǎng)方形，記X=(e,a,b,c)

其中：

e：什么也不做；

a：繞橫軸旋轉(zhuǎn)180°；

b：繞縱軸旋轉(zhuǎn)180°；

c：繞原點(diǎn)平旋180°。圖6.2.1例3圖6.3群同態(tài)、群同構(gòu)

定義1

設(shè)（G，*）和(H,。)是兩個(gè)群，h∶G→H是G到H的映射。如果對(duì)a,b∈G有h(a*b)=h(a)。h(b)則稱h為（G，*）到(H，。)的群同態(tài)。

命題1

設(shè)eG∈G,

eH∈H分別為群（G，*）及(H，。)的幺元，h∶G→H為群同態(tài)，則h(eG)=eH，h(a-1)=(h(a))-1

證明因h(eG)=h(eG*eG)=h(eG)。h(eG),又注意到群中惟幺元是冪等元，故

h(eG)=Eh又h(a)。h(a-1)=h(a*a-1)=h(eG)=h(a-1*a)=h(a-1)。h(a)=eH故h(a-1)=(h(a))-1

命題3

設(shè)（G，*）是群，(H，。)為一代數(shù)系統(tǒng)，若存在滿映射h∶G→H，使對(duì)a,b∈G有h(a*b)=h(a)。h(b)則(H，。)必為群。命題3可以看作命題2的直接推論。根據(jù)h是單射、滿射及雙射，群同態(tài)分別稱為單同態(tài)、滿同態(tài)及同構(gòu)。從群（G，

*）到自身的同態(tài)稱為自同態(tài)，從群（G，*）到自身的同構(gòu)稱為自同構(gòu)。

例1

在代數(shù)系統(tǒng)(N5，×5)中，記

N*5=N5\{0}。構(gòu)造映射h：N4→N*5，有h(0)=1;h(1)=2;h(2)=4;h(3)=3對(duì)照二者的運(yùn)算表，易見(jiàn)(N4,+4)同構(gòu)于(N*5,×5)；又因(N4,+4)是群，故知(N*5,×5)也是群。

例2

任一k階循環(huán)群（G，*）都同構(gòu)于(Nk,+k)。事實(shí)上，因若a∈G是（G，*）的生成元，則G={a,a2,…,ak=e}，構(gòu)造映射h:Nk→G,h(imodk)=ai由于

h(i+kj)≡h((i+j)modk)=a(i+j)=ai*aj=h(imodk)*h(jmodk)又顯見(jiàn)h是Nk到G的雙映射函數(shù)，所以（G，*）和(Nk,+k)同構(gòu)。

命題4(Cayley定理，1854)

任一n階群，都同構(gòu)于一n次n階置換群。

證明設(shè)（G，*）是一n階有限群，由6.1節(jié)命題1的推論3可知，（G，*）的運(yùn)算表中每一行,每一列都是G的一個(gè)置換。對(duì)應(yīng)于元素a∈G的行置換是pa(x)=a*x,即對(duì)應(yīng)于G的所有元素的行的置換為PG。下面證（PG,。)是一群（其中。為置換間的合成運(yùn)算）。封閉性：對(duì)a,b∈G，有

pa。

pb(x)=a*(b*x)=(a*b)*x=pa*b(x)

幺元：設(shè)e是（G，*）的幺元，對(duì)a∈G，有pe。

pa=pa。

pe=pa即pe為（PG,。)的幺元。

逆元：對(duì)a∈G，設(shè)a-1∈G為a的逆元，則pa。p-1a=p-1a=pe。即對(duì)pa∈PG，存在逆p-1a∈PG

。結(jié)合律由置換的合成運(yùn)算立得。故知（PG,。)為群。下證（G，*）與（PG,。)同構(gòu)。構(gòu)造h:G→Pa,h(a)=pa,顯見(jiàn)h為雙射函數(shù),又因h(a*b)=pa*b=pa。pb=h(a)。h(b),即見(jiàn)h是同態(tài)。這就證明了h是同構(gòu)，亦即（G，*）與（PG,。)同構(gòu)。

定義2

設(shè)（H，*）是群（G，*）的子群，則稱aH={a*h|h∈H},Ha={h*a|h∈H}分別為由元素a∈G所確定的子群（H，*）的左陪集,右陪集，a稱為該左、右陪集的表示元。如下只討論左陪集，所得結(jié)論對(duì)右陪集也平行成立。

命題5

設(shè)（H，*）是（G，*）的子群，aH,bH是二任意左陪集，則或者aH=bH，或者aH∩bH=。

證明假定aH∩bH≠，即f(f∈aH∧f∈bH)，于是h1,h2∈H，使f=a*h1=b*h2

a=b*h2*h-11。設(shè)x是aH中任一元素，即有h3∈H使x=a*h3

x=b*h2*h-11*h3，但h2*h-11*h3∈H,故x∈bH。反之，若x∈bH

x∈aH，即有aH=bH。又aH和bH均非空集，且aH=bH和aH∩bH=不可兼得，所以命題為真。

命題6

H的任意陪集的大小是相等的。

證明對(duì)a∈G，h1,h2∈H，若h1≠h2，則a*h1≠a*h2。所以aH中不會(huì)產(chǎn)生二相同元素，這推得|aH|=|H|，亦即H的任一陪集大小相同，且均與H相等。由于（H，*）是（G，*）的子群，幺元e∈（H，*），故對(duì)a∈G

a∈aH， 。由以上二命題即可斷言H的全部左陪集構(gòu)成G的一個(gè)劃分，且該劃分中的塊均具有相同的基數(shù)。換言之，|G|=α|H|，其中a為H的左陪集的個(gè)數(shù)。于是有以下命題：

命題7(Lagrange定理）

有限群的任意子群的階數(shù)可以整除群的階數(shù)。推論1素?cái)?shù)階的群惟有兩個(gè)平凡子群。推論2有限群的任一元素的階必可整除該群的階。推論3素?cái)?shù)階的群必為循環(huán)群。推論4任意四階群或?yàn)檠h(huán)群或?yàn)镵lein四群。

定義3

設(shè)（H，。）是（G，。）的子群，對(duì)g∈G,若gH=Hg，則稱（H，。）為（G，。）的正規(guī)子群。等價(jià)的說(shuō)法是,對(duì)g∈G，有H=gHg-1。

命題8

設(shè)A

G,H

G，且（H，。）是群（G，。）的正規(guī)子群，則

換言之，（G，。）的正規(guī)子群與G的子集（相乘）可交換。

命題9(1）設(shè)（H，。）是（G，。）的子群，則H的全部左陪集{gH|g∈G}或右陪集{Hg|g∈G}構(gòu)成G的劃分。這個(gè)劃分的類所成之集常記為G/H，稱為G對(duì)于H的商集，且有

（2）如果（H，。）對(duì)（G，。）是正規(guī)的，則商集G/H對(duì)如下定義的乘法K*K′={x。x′|x∈K,x′∈K′;K,K′∈G/H}構(gòu)成群。6.4置換中的輪換6.4.1輪換與對(duì)換

設(shè)X={1,2,…,n}，X上的任一置換f都聯(lián)系著一個(gè)有向圖G=(X,E)，其中i,j∈X,(i,j)∈E當(dāng)且僅當(dāng)f(i)=j。由于f是從X到自身的雙射函數(shù)，故對(duì)

i∈X，其入度和出度都是1?？疾煨蛄衚,f(k),f2(k),…

因X為有限集，故序列中必有重復(fù)出現(xiàn)的元素，不難證得最早重復(fù)出現(xiàn)者必為k。如若不然，設(shè)ft(k)是最早重復(fù)出現(xiàn)的元素，即有ft(k)=fs(k)(1≤t<s)，由最早性知ft-1(k)≠fs-1(k)。但這與f所具有的性質(zhì)i≠j

f(i)≠f(j)相矛盾。設(shè)fm(k)=k是最早重復(fù)出現(xiàn)的元素，則稱k,f(k),f2(k),…,fm(k)是一個(gè)輪換，記作(kf(k)f2(k)…fm-1(k))

m常稱為該輪換的長(zhǎng)度。長(zhǎng)度為2的輪換又稱為對(duì)換或換位。顯見(jiàn)，由f決定的有向圖G=(X,E)的每個(gè)連通分支是一個(gè)輪換，且f的所有不同的輪換形成集合X的一個(gè)劃分。設(shè)則可產(chǎn)生四個(gè)輪換:(132)、(4)、(5)、(6)。置換常記為若干輪換的乘積形式，且如不記順序，這種表示還是惟一的。例如,f可記為f=(132)(4)(5)(6)，或更簡(jiǎn)單的記作f=(132)。

上述記法對(duì)于直接計(jì)算若干置換的乘積是很方便的。設(shè)有如下置換：

f=(134)(26)

g=(152)(364)

h=(1456)

則

f。g。h=(134)(26）（152）（364）（1456）

先看數(shù)字1，從右向左依次考察各輪換，即可得出1所經(jīng)歷的變換1→4→3→3→3→4記下（14…）；再考察4所經(jīng)歷的變換4→5→5→2→6→6

記下（146…）；再考察6所經(jīng)歷的變換6→1→1→5→5→5

接下去是5→6→4→4→4→1因此，第一個(gè)輪換是（1465）；然后取出不在這個(gè)輪換中的最小整數(shù)（這里是2），用同樣方法作出第二個(gè)輪換，即2→2→1→1→3

3→3→6→6→2→2因此f。g。h=(1465)(23)

結(jié)合以上過(guò)程不難給出一般情況下求置換的不交輪換乘積表示的算法。該算法反過(guò)來(lái)即為置換可表示為不交輪換之積的證明。對(duì)置換中的輪換(12),(34)及(5)，可分別獨(dú)立解釋為即不在各輪換中出現(xiàn)的元素保持不變。(12)，(34)及(5)之間的乘積關(guān)系可解釋為輪換（即相應(yīng)置換）間的合成運(yùn)算。亦即

更進(jìn)一步，還可把輪換分解成若干對(duì)換之積，但這種分解并不惟一，其一般分解可用歸納法證明，這里從略。如下僅給出一個(gè)例子：(4321)=(12)(13)(14)=(23)(24)(21)=(23)(24)(21)(13)(31)雖然輪換(4321)可有多個(gè)不同形式對(duì)換積的分解式，但在這些分解式中，對(duì)換因子個(gè)數(shù)的奇偶性卻是不變的。如(4321)的各種對(duì)換乘積分解式中對(duì)換的數(shù)目均為奇數(shù)。任意置換的階等于它的不相交輪換之長(zhǎng)度的最小公倍數(shù)n。事實(shí)上，若設(shè)k,l,…,m的最小公倍數(shù)為n，且f=fk。fl?！?。fm=(a1a2…ak)。(b1b2…bl)?！?c1c2…cm)

則fn=fnk。fnl?！?。fnm=e。e?！=e

故知f的階為n。

例1去掉大小王后，52張撲克牌加以編碼1,2,…,52，則這副牌連續(xù)洗8次后又恢復(fù)到原來(lái)牌序。

解第一次洗牌可用置換表示為

P=(1)·(2,27,14,33,17,9,5,3)·(4,28,40,46,49,25,13,7)

·(6,29,15,8,30,41,21,11)·(10,31,16,34,43,22,37,19)

·(12,32,42,47,24,38,45,23)·(18,35)

·(20,36,44,48,50,51,26,39)·(52)其中，有2個(gè)1-輪換，1個(gè)2-輪換，6個(gè)8-輪換，由于各輪換長(zhǎng)度的最小公倍數(shù)(1,1,2,8,8,8,8,8,8)=8，故知撲克牌洗8次后又會(huì)恢復(fù)到原來(lái)的牌序。6.4.2置換的奇偶性及對(duì)換的性質(zhì)設(shè)f=a1a2…an為集合S={1,2,…,n}上的一個(gè)置換，若對(duì)i<j，有ai>aj，則稱aj出現(xiàn)了一個(gè)逆序(或稱（ai,aj

）為一逆序)。aj的逆序（個(gè)）數(shù)記為invs

(aj)，顯見(jiàn)invs(aj)為滿足i<j∧ai>aj的i的個(gè)數(shù)。若用invs(f)記置換f的逆序數(shù)，則invs(f)∷=。例如：對(duì)f=45123有invs(1)=2，invs(2)=2，invs(3)=2，invs(4)=0，invs(5)=0因此 invs(f)=2+2+2+0+0=6

又對(duì)f=12345，由invs(f)=0，知幺置換的逆序數(shù)為0。

若記置換f的符號(hào)為sign(f)，則sign(f)∷=(-1)invs(f)

若sign(f)=-1，則稱置換f為奇置換；若sign(f)=1，則稱置換f為偶置換。幺置換為偶置換。一個(gè)置換的奇偶性很容易從置換的不交輪換乘積分解式而得。

性質(zhì)1

若t=(ij)為一對(duì)換，則t2=e，且t=t-1。

性質(zhì)2

任一對(duì)換t=(ij)為一奇置換。事實(shí)上，若設(shè)t=(ij)為S={1,2,…,n}的一個(gè)置換，即t=(ij)=(1,2,…,i-1,i,i+1,…,j-1,j,j+1,…,n)其中

invs(1)=invs(2)=…=invs(i-1)=invs

(j-1)=…=invs(n)=0

invs(i+1)=…=invs(j-1)=1共j-1-(i+1)+1=j-i-1個(gè)逆序）

invs(i)=j-1-i+1=j-i

（共j-i個(gè)逆序）從而invs(t)=j-i-1+j-i=2(j-i)-1，故知，對(duì)換t=(ij)為奇置換。性質(zhì)3

對(duì)任一置換f及對(duì)換t=(i,i+1)，有invs(f)=invs(ft)±1例如且有invs(f)=invs(1)+invs(4)+invs(2)=1+1+4=6

invs(ft)=invs(1)+invs(2)=1+4=5

即invs(f)=invs(ft)+1

性質(zhì)3反映了將t=(i,i+1)作用于f時(shí)，f的逆序數(shù)增（或減）1，而逆序數(shù)增（或減）1恰好改變了f的奇偶性。對(duì)任一置換f若用形如(i,i+1)的對(duì)換將序列a1a2…an變?yōu)?2…n，即將f變?yōu)楹愕然蜱壑脫Q，問(wèn)最少需要多少個(gè)這樣的對(duì)換？例如即共用了6個(gè)形如(i,i+1)的對(duì)換。注意45123的逆序數(shù)為6。

一般情況下，可以證明下面若干結(jié)論：（１）將置換f的簡(jiǎn)記形式a1a2…an變?yōu)?2…n所需的形如(i,i+1)的對(duì)換的最小個(gè)數(shù)等于f的逆序數(shù)invs(f)。證明分兩步：首先,證明f=a1a2…an一定可以通過(guò)invs(f)個(gè)對(duì)換變?yōu)?2…n。思路是通過(guò)逐個(gè)考察元素1,2,…,n-1的逆序數(shù)并重復(fù)對(duì)換相鄰項(xiàng),而將各元素?fù)Q到自然位置，而這種操作是機(jī)械式的。其次，證明invs(f)是將f=a1a2…an變?yōu)?2…n的最小次數(shù)，這是由于若將(i,i+1)施加于f得到f′時(shí)，有

invs(f)+1,若ai<ai+1

invs(f)-1,若ai>ai+1invs(f′)=

（２）若置換f經(jīng)過(guò)q個(gè)形如(i,i+1)的對(duì)換，而將序列a1a2…an變?yōu)殓壑脫Q12…n，則q與invs(f)具有相同的奇偶性。注意到(1)中曾證明過(guò)一定能用invs(f)次操作使invs(f)降到0。又若用q次形如(i,i+1)的對(duì)換使得invs(f)變?yōu)?，必有q≥invs(f)。其中多余部分出現(xiàn)了使invs(f)加1的冗余操作及相同次數(shù)減1的冗余操作,去掉往返的偶數(shù)次冗余操作后，所剩操作次數(shù)一定是invs(f)次。故知q與invs(f)具有相同的奇偶性。

（３）對(duì)稱群Sn的每個(gè)置換f均可表示為q個(gè)對(duì)換（不一定形如(i,i+1)）之積，且若各對(duì)換形為(i,i+1)時(shí)，q與invs(f)具有相同的奇偶性。注意到f=a1a2…an一定可以通過(guò)q個(gè)對(duì)換t1t2…tq變?yōu)?2…n。即

即f可表示為q個(gè)形如(i,i+1)的對(duì)換之積。又若f可表示為q個(gè)形為(i,i+1)的對(duì)換之積(即f=tq·tq-1…t1)時(shí)，則可推知f·t1·t2…tq=e，由（2）知與invs(f)具有相同的奇偶性。

（4）對(duì)稱群Sn是由(12),(23),…,(n-1,n)這n-1個(gè)對(duì)換生成的。（５）sign(f。

f′)=sign(f)sign(f′)。由（3）知Sn中的每個(gè)置換f均可分解為q個(gè)形如(i,i+1)的對(duì)換之積，而q又與invs(f)同奇偶,對(duì)f′亦有q′與invs(f′)同奇偶,故sign(f。f′)=(-1)q+q′=(-1)invs(f)+invs(f′)

=(-1)invs(f)·(-1)invs(f′)=sign(f)·sign(f′)

（６）若置換f可表示為q個(gè)對(duì)換之積，則q與invs(f)有相同的奇偶性。令f=t1。t2?！?。tq

，其中ti(i=1,2,…,q)都是對(duì)換，且都是奇性的。由（５）知(-1)invs(f)=sign(f)=sign(t1)…sign(t2)sign(tq)=(-1)q

故invs(f)與q具有相同的奇偶性。(7)置換的奇偶性等于其偶數(shù)長(zhǎng)輪換的個(gè)數(shù)的奇偶性。即設(shè)置換f分解的輪換積中偶數(shù)長(zhǎng)輪換的個(gè)數(shù)為q，則f與q具有相同的奇偶性。首先，任一k階輪換可分解為k-1個(gè)對(duì)換之積,即(a1a2…ak)=(a1a2)(a2a3)…(ak-1ak)其次，設(shè)f中有λ1個(gè)1-輪換，λ2個(gè)2-輪換，…,λk個(gè)λk-輪換，將其記為 ，這些輪換可分解的對(duì)換數(shù)為m=λ2+2λ3+3λ4+4λ5+…+(k-1)λk=λ2+λ4+…+2λ3+2λ4+…由（6）知，f與m同奇偶，即f與λ2+λ4+…同奇偶。從而，f與偶數(shù)長(zhǎng)輪換的個(gè)數(shù)同奇偶。例如,(1234)(5),(123)(4567)都是奇置換，(12345),(1234)(567)(89)都是偶置換。

例2（15-謎題）圖6.4.1給出了4×4棋盤上棋子的兩種布局,棋子分別標(biāo)以數(shù)字0,1,2,…,15。若規(guī)定只允許出現(xiàn)0棋子與其相鄰的棋子對(duì)換，證明其中的置換（a）布局不能演變?yōu)椋╞）布局。證明從（a）變到（b）相當(dāng)于做以下置換f：這是一個(gè)奇置換。圖6.4.1例2圖

另一方面，按移動(dòng)規(guī)則將0從右下角換出，最后再返回到右下角，往返必須經(jīng)過(guò)偶數(shù)次對(duì)換。亦即，按移動(dòng)規(guī)則使０恢復(fù)原位一定會(huì)產(chǎn)生一個(gè)偶置換。由此推知，按照題給移動(dòng)規(guī)則，不能將（a）布局變到（b）布局。因此，只有當(dāng)給定布局間能用偶置換表示時(shí)，才能按移動(dòng)規(guī)則將一種狀態(tài)演變到另一種狀態(tài)。

定義1

設(shè)（G，。）為一置換群，若g∈G，使得s=g。t。g-1，則稱s和t在G中共軛。

命題1“共軛”是G上的一種等價(jià)關(guān)系。

證明自反性：s=e。s。e-1,e∈G。對(duì)稱性：s=g。t。g-1

t=g-1。s。g=h。s。h-1,h=g-1∈G。傳遞性：s=g。t。g-1∧t=h。u。h-1

s=g。(h。u。h-1)。g-1=(g。h)。u。(g。h)-1,g。

h∈G。

命題2

兩個(gè)置換s與t在n次對(duì)稱群（Sn，。）中共軛，當(dāng)且僅當(dāng)它們的各種長(zhǎng)度的輪換的數(shù)目相同。

證明必要性：令s=g。t。g-1，

g∈Sn定義為bpq=g(apq)，t=(a11a12…a1i)(a21a22…a2j)…(am1am2…amk

)于是s(bpq)=g。t。g-1(bpq)=g。t(apq)=g(apq+1)=bpq+1

因此s=(b11b12…b1i)(b21b22…b2j)…(bm1bm2…bmk)

充分性：如果s與t的各種長(zhǎng)度的輪換的數(shù)目相同（不妨設(shè)s，t就為必要性證明中所示形式），則s=g。t。g-1

，即s和t在Sn中共軛。例3

S3有三個(gè)共軛類，分別對(duì)應(yīng)于3的三個(gè)拆分：3=1+1+1,3=1+2,3=3第一類僅含一個(gè)置換：第二類含有三個(gè)置換：第三類含有二個(gè)置換：

定義2

設(shè)f為n次對(duì)稱群（Sn，。）中的任一置換，若f可表示為λi(i=1,2,…,k)個(gè)長(zhǎng)為i的輪換之積，則稱f屬于∏iλi型的置換。例如,f=（1）（23）（4567）屬于11213041型的置換，或省去指標(biāo)為0的項(xiàng)而簡(jiǎn)寫(xiě)為112141型。顯見(jiàn)

命題3

（Cauchy定理）Sn中屬于 型的置換的數(shù)目為證明具有上述要求的置換的格式為

格式中的n個(gè)*可用n！種方法代之以1，2，…，n，但是這樣得出的置換并不都是相同的，因?yàn)棣薸個(gè)長(zhǎng)為i的輪換可以互換而f不變。在這種意義下，同一f重復(fù)的次數(shù)為。另外，對(duì)每個(gè)長(zhǎng)為i的輪換（有向圈）為首的數(shù)字有i種不同的寫(xiě)法。在這種意義下，同一f重復(fù)出現(xiàn)的次數(shù)是 。因此， 型的置換的個(gè)數(shù)是例如，當(dāng)n=3時(shí)，1·2型置換的個(gè)數(shù)為參見(jiàn)前例，這三個(gè)置換分別是a,b,c。

推論在Sn中 型的共軛類的元素個(gè)數(shù)為h(λ1,λ2,…,λk)。定義3設(shè)（G，。）是作用在有限集X(|X|=n)上的置換群，若對(duì)x,y∈X,g∈G，使得y=g(x)，則稱“相對(duì)于G，x等價(jià)于y”。記作x≡y(G)

顯見(jiàn)“≡”是一種等價(jià)關(guān)系（其證明作為練習(xí)）。等價(jià)關(guān)系“≡”的等價(jià)類稱為群（G，。）的軌道（Orbit）。若當(dāng)（G，。）是由置換f生成的循環(huán)群，即G={e,f,f2,…}，則（G，。）的軌道就是f中的輪換。由此，軌道可看作輪換概念的推廣。

定義4

對(duì)k∈X，定義Gk={g|g∈G∧g(k)=k}為使元素k保持不動(dòng)的全部置換，常稱Gk為k的不動(dòng)置換類。注意到f,g∈Gkf。g(k)=f(k)=k

f。g∈Gk（封閉性），即得如下命題：

命題4(Gk，。）是（G，。)的子群。如下由建立Ok到G/Gk的一個(gè)雙射函數(shù)來(lái)證明|G/Gk|=|Ok|。

命題5

設(shè)（Gk，。）是（G，。）的使k不動(dòng)的子群，Ok是G的包含k的軌道，即Ok={y|k≡y(G)}={y|

g∈G,g(k)=y}

則 |Gk|·|Ok|=|G|

證明根據(jù)6.3節(jié)命題9，有

事實(shí)上，對(duì)y∈Ok，因至少g∈G使g(y)=k，就令y對(duì)應(yīng)商集G/Gk中的類Gk。g。若g(y)=k∧h(y)=k，h,g∈G

h。g-1(k)=k

h。g-1∈Gk

h∈Gk。gGk。g=Gk。h即見(jiàn)這種對(duì)應(yīng)構(gòu)成Ok到G/Gk的單射。對(duì)于Gk。g∈G/Gk,Gk。g是g-1(k)∈Ok的像,又見(jiàn)這種對(duì)應(yīng)構(gòu)成Ok到G/Gk的滿射。從而Ok與G/Gk間有一雙射函數(shù)存在，故

|G/Gk|=|Ok|

例4

考慮由f=（123）（45）生成的群（G，。），其中G={f,f2,f3,f4,f5,f6=e},f2=(132)(4)(5),f3=(1)(2)(3)(45)f4=(123)(4)(5),f5=(132)(45),f6=(1)(2)(3)(4)(5)軌道為O1={1,2,3};O4={4,5}

（G，。）的使1不變的子群為(G1={f3,f6},。)即見(jiàn)|G1|×|O1|=3×2=6=|G|

命題6（Burnside引理）設(shè)λ(g)是在置換g作用下X中不動(dòng)的元素的個(gè)數(shù)（即g的長(zhǎng)為1的輪換的個(gè)數(shù)），則n次對(duì)稱群（Sn，。）的子群（G，。）的軌道數(shù)為 ，其中LG為G的軌道集。

證明如下用兩種不同的方法求算適合g(k)=k，g∈G，k∈X的序偶(g,k)的個(gè)數(shù)，即如果j與k屬于同一軌道，則因此例5

對(duì)前邊的例子，應(yīng)用命題6有λ(f)=0,λ(f2)=2,λ(f3)=3,λ(f4)=2,λ(f5)=0,λ(f6)=5

例6

一個(gè)正方形均分成4個(gè)格子，用兩種顏色對(duì)4個(gè)格子著色，若經(jīng)旋轉(zhuǎn)可以吻合的方案算作同一個(gè)方案，問(wèn)能得到多少種不同方案的圖像。

解每格有兩種顏色可供選擇，故所有可能的圖像共有16種，記為X={X1,X2,…,X16}。當(dāng)每個(gè)圖像都繞中心軸逆時(shí)針旋轉(zhuǎn)0°、90°、180°、270°時(shí)，都可得到X的一種排列，記4種排列為G={P0,P90,P180,P270}。若記為連續(xù)動(dòng)作，Px,Py∈G，Px。Py為先作用Py后作用Px

，則（G，。）構(gòu)成X上的一個(gè)置換群，從而問(wèn)題歸結(jié)為求置換群（G，。）的軌道（旋轉(zhuǎn)等價(jià)類）數(shù)。

不難求得λ(P0)=16,λ(P90)=λ(P270)=2,λ(P180)=4，故（G，。）的不同軌道數(shù)為亦即在旋轉(zhuǎn)吻合的前提下共有6種（不同等價(jià)類）圖案。

例7

考察由藍(lán)、白、黃三種顏色的珠子中選取5粒串成的手鐲，如將一只手鐲經(jīng)（逆時(shí)針?lè)较颍┬D(zhuǎn)而得另一只手鐲視為同一手鐲，則稱二手鐲是旋轉(zhuǎn)等價(jià)的。試求在旋轉(zhuǎn)等價(jià)的意義下不同手鐲的數(shù)目。

解設(shè)X是不考慮旋轉(zhuǎn)等價(jià)時(shí)的手鐲，則顯見(jiàn)X={f:A→B}，其中A={1,2,3,4,5},B={藍(lán)，白，黃}。|X|=|B||A|=3·3·3·3·3=35=243。將手鐲的（逆時(shí)針）旋轉(zhuǎn)方式定義為Pk(mod5)。令G={Pj|j≡k(mod5)∧k∈Z+},則（G，。）為X上的一個(gè)置換群。其中為連續(xù)動(dòng)作，Px。Py為先作用Py后作用Px。

對(duì)任意手鐲，若珠子顏色全同，則任意一種旋轉(zhuǎn)都會(huì)使該手鐲自身變到自身，即旋轉(zhuǎn)不變。又當(dāng)手鐲中珠子粒數(shù)為素?cái)?shù)時(shí)，則不會(huì)出現(xiàn)不同色的手鐲保持不變的情形。本例中5為素?cái)?shù)，即只有全白、全藍(lán)及全黃這三種手鐲是旋轉(zhuǎn)不變的。故λ(P1)=λ(P2)=λ(P3)=λ(P4)=3。由Burnside定理，在旋轉(zhuǎn)等價(jià)的意義下，不同手鐲的數(shù)目應(yīng)為

利用不同手鐲數(shù)目的計(jì)算結(jié)果，可獲得數(shù)論中Fermat（?。┒ɡ淼囊粋€(gè)有趣證明。

對(duì)素?cái)?shù)p，考察由a種珠子中選取p粒串成的手鐲，在旋轉(zhuǎn)等價(jià)的意義下，不同手鐲的數(shù)目為由于手鐲的數(shù)目總是整數(shù)，從而p|a(ap-1+p-1)，即p或者整除a，或者整除ap-1-1+p。而對(duì)后者，可得p|(ap-1-1)。由本例即得Fermat（?。┒ɡ恚簩?duì)a,ap-a≡0(modp)（p為素?cái)?shù)），或?qū),ap≡a(modp)，或?qū),ap-1≡1(modp)。6.5Polya定理

定義1

設(shè)X={1,2,…,n}為染色對(duì)象集，A={a1,a2,…,am}為顏色集，（G，。）為X上的一個(gè)置換群，函數(shù)φ:x→A為一種染色（方案），φ把對(duì)象i∈X染上顏色φ(i)∈A。注意：對(duì)g∈G,φg也是一種染色。例如若g∈G，使得φ1g=φ2，則稱二染色φ1與φ2屬于同一格式（或?qū)偻活悾?記作φ1~φ2。顯見(jiàn)“~”是一種等價(jià)關(guān)系。定義2

設(shè)g∈G，令λi(g)表示g中長(zhǎng)為i的輪換的個(gè)數(shù)，則多項(xiàng)式稱為G的輪換指數(shù)。

命題1(Polya計(jì)數(shù)定理）根據(jù)定義1和定義2，相對(duì)于G的格式的數(shù)目為

證明記Φ={φ|φ:X→A}，對(duì)φ∈Φ,

g∈G,定義g:Φ→Φ,g(φ)=φgc斷言g是Φ到自身的雙射函數(shù)。因Φ為有限集，故只需證g為單射即可。事實(shí)上φ1≠φ2

φ1g≠φ2gg(φ1)≠g(φ2)。令S表Φ中元素的全部置換，則g∈S，因?yàn)榧处?G→ψ(G)

S,ψ(g)=g∈S為一雙射函數(shù)。因此，G=ψ(G)={g|g∈G}與G的基數(shù)相同。此外(G,。)構(gòu)成(S,。)的子群。事實(shí)上，因若g,h∈G，則

若g∈G，使φ2=g(φ1)=φ1g，即φ1與φ2屬于G的同一軌道，則φ1和φ2等價(jià)。因此，相對(duì)于G的格式的數(shù)目等于G的軌道數(shù)。由Burnside定理，G的軌道數(shù)為其中,v(g)是滿足φg=φ的染色φ的個(gè)數(shù)，而φg=φ表示φ使g的每個(gè)輪換中的元素染上同樣的顏色,因此v(g)等于g的輪換集合（該集的元素個(gè)數(shù)為 )到m種顏色的映射的個(gè)數(shù)。因此

例1

令X={1,2,3,4,5,6},A={b,w}。把X中的元素看作立方體的6個(gè)面：1表頂面；3表底面；2表迎面；4表背面；5和6表左、右側(cè)面。A的元素看作黑白兩種顏色。下面在旋轉(zhuǎn)等價(jià)的意義下計(jì)算立方體染色的格式數(shù)。首先構(gòu)造立方體的旋轉(zhuǎn)群（G，。），并把一種染色看作X到A的一個(gè)映射。上、下底面不動(dòng)，每次旋轉(zhuǎn)（右轉(zhuǎn)）一個(gè)面、二個(gè)面、三個(gè)面，可得X的3個(gè)置換：g1:(1)(3)(2645);g2:(1)(3)(24)(65);

g3:(1)(3)(2546)

前、后面不動(dòng)，每次旋轉(zhuǎn)（逆時(shí)針）一個(gè)面、二個(gè)面、三個(gè)面，可得X的3個(gè)置換：g4:(2)(4)(1536);g5:(2)(4)(13)(56);g6:(2)(4)(1635)

左、右側(cè)面不動(dòng)，仿上可得三個(gè)置換：g7:(1234)(5)(6);g８:(13)(24)(5)(6);g９:(1432)(5)(6)

分別繞四條對(duì)角線旋轉(zhuǎn)120°、240°可得8個(gè)置換：g10：(145)（632）； g11：（152）（643）g12：（154）（623）；

g13：（125）（634）g14：（126）（345）；

g15：（162）（354）g16：（164）（352）；

g17：（146）（325）

此外分別以六對(duì)對(duì)角平行棱線的中點(diǎn)為軸線旋轉(zhuǎn)180°，共可產(chǎn)生6個(gè)不同置換：g18：（15）（63）（24）；g19：（16）（35）（24）g20：（12）（43）（56）；g21：（14）（23）（56）g22：（25）（64）（13）；g23：（26）（54）（13）再加單位元（幺置換）g24：（1）（2）（3）（4）（5）（6），共有24個(gè)置換。在上述立方體的染色問(wèn)題中，

G的輪換指數(shù)易見(jiàn)為從而由命題1，六面體每面可染兩種顏色的格式數(shù)為P(G;2,2,2,2,2,2)=10

例2

類似于例1，對(duì)立方體的8個(gè)頂點(diǎn)著兩種顏色的方案數(shù)，可由構(gòu)造8個(gè)點(diǎn)上的置換群G并用命題1求算如下：

例3

骰子的六個(gè)面分別有1，2，3，4，5，6個(gè)點(diǎn)，試求旋轉(zhuǎn)等價(jià)意義下，六個(gè)面的分布方案數(shù)。

解六個(gè)面用6種顏色著色，各面顏色互不相同，共有6！種方案。又依例1，六面體旋轉(zhuǎn)運(yùn)動(dòng)群共有24個(gè)置換。分別將各置換同時(shí)作用于6！種方案，則除幺置換能使各方案保持不動(dòng)外，其余23種置換的任一種都不能使6！種方案的任一方案置換不變。故除幺置換的所有置換的置換不變?cè)膫€(gè)數(shù)都是0，而幺置換的置換不變?cè)?！。由Burnside定理，不同的方案數(shù)為

例4

等邊三角形V1V2V3，若以紅，白，藍(lán)三色涂染各頂點(diǎn)，試求置換等價(jià)意義下的染色方案數(shù)。

解構(gòu)造三角形的旋轉(zhuǎn)置換群（G，。）。分別繞形心旋轉(zhuǎn)（逆旋）120°、240°可得二置換：g1:(V1V2V3);g2:(V3V2V1)

分別繞三邊中垂線翻轉(zhuǎn)180°可得三個(gè)置換：g3:(V1)(V2V3);g4:(V1V3)(V2);g5:(V1V2)(V3)

不作任何動(dòng)作可得到置換（幺元）g6:(V1)(V2)(V3)

故不同方案數(shù)為

例5

對(duì)正四面體的4個(gè)頂點(diǎn)用4種顏色著色，求置換等價(jià)意義下的不同方案數(shù)。

解使正四面體V1V2V3V4重合的剛體運(yùn)動(dòng)有兩類，一類是繞各面的中垂線分別旋轉(zhuǎn)0°、120°和240°；一類是繞過(guò)二對(duì)邊中點(diǎn)的連線旋轉(zhuǎn)180°，從而可得群G的各置換如下：(V1)(V2)(V3)(V4) (V1)(V2V3V4) (V1)(V4V3V2)(V2)(V1V3V4) (V2)(V4V3V1) (V3)(V1V2V4)

(V3)(V4V2V1) (V4)(V1V2V3) (V4)(V3V2V1)

(V1V2)(V3V4) (V1V3)(V2V4) (V1V4)(V2

V3)故不同的方案數(shù)為

例6（分放問(wèn)題）將4個(gè)球a，a，b，b放進(jìn)兩個(gè)有編號(hào)的盒子A，B中，試問(wèn)有幾種放法？

解令X={a1,a2,a3,a4}，其中,a1=a2=a,a3=a4=b。因?qū)θ我环欧?對(duì)調(diào)a1與a2或a3與a4仍屬同一放法，故相應(yīng)的置換群(G,。)的各置換如下：g1:(12)(3)(4); g2:(1)(2)(34)

g3:(12)(34); g4:(1)(2)(3)(4)從而各分放方案為￠|aabb,a|abb,b|aab,aa|bb,ab|ab,aabb|￠,abb|a,aab|b,bb|aa

命題2(Polya定理)

n個(gè)物件中恰有αi個(gè)物件染成ai色（i=1,2,…,m）的格式數(shù)為