組合數(shù)學(xué)（第二版）波利亞(Pólya)定理

波利亞(Pólya)定理6.1群論基礎(chǔ)6.2置換群6.3伯恩賽德(Burnside)引理6.4Pólya定理6.5母函數(shù)型的Pólya定理6.6應(yīng)用

6.1群論基礎(chǔ)

6.1.1群的概念

定義6.1.1給定非空集合G

及定義在G上的二元運算“·”,若滿足以下四個條件,則稱集合G

在運算“·”下構(gòu)成一個群,簡稱G

為一個群:

(1)封閉性:a,b∈G,則a·b∈G;

(2)結(jié)合律:(a·b)·c=a·(b·c);

(3)單位元:存在e∈G,對任意a∈G,有a·e=e·a=a;

(4)逆元素:對任意a∈G,存在b∈G,使得a·b=b·a=e,稱b為a的逆元素,記為a-1.)

群的運算符“·”可略去,即a·b=ab.

群的運算并不要求滿足交換律.如果某個群G中的代數(shù)運算滿足交換律,則稱G為交換群或Abel群.

群的元素可以是有限個,叫做有限群;也可以是無限個,叫做無限群.以|G|表示有限群中元素的個數(shù),稱為群的階,那么當(dāng)G為無限群時,可以認(rèn)為|G|=∞.

【例6.1.1】偶數(shù)集,整數(shù)集Z,有理數(shù)集Q,實數(shù)集R,復(fù)數(shù)集C關(guān)于數(shù)的加法構(gòu)成群,稱為加法群.

因為數(shù)的運算對加法滿足定義6.1.1的要求(1)和(2).其中的單位元為0,每個數(shù)a關(guān)于加法的逆元為:a-1=-a.

但是,關(guān)于數(shù)的乘法,這些集都不構(gòu)成群.因為在偶數(shù)集中關(guān)于普通乘法不存在單位元.而在Z、Q、R、C中,雖然關(guān)于普通乘法有單位元1,但數(shù)0沒有逆元.

6.1.2群的性質(zhì)

定理6.1.1群具有以下性質(zhì):

(1)單位元e唯一;

(2)逆元唯一;

(3)滿足消去律:即對a,b,c∈G,若ab=ac,則b=c;若ba=ca,則仍有b=c;

(4)a,b∈G,則(ab)-1=b-1a-1,更一般有(ab…c)-1=c-1…b-1a-1;

(5)若G是有限群,則對任意a∈G,必存在一個最小常數(shù)r,使ar=e,從而a-1=ar-1.r稱為元素a的階.

證性質(zhì)(1)~(4)顯然.只證明性質(zhì)(5).

設(shè)|G|=n,由G的定義知:

由抽屜原理知,必存在整數(shù)m,k,滿足1≤m<k≤n+1,使得am=ak

,即ak-m

=e,令r=k-m,則ar=e,即a.ar-1=e,所以a-1=ar-1.

6.1.3子群

定義6.1.2設(shè)G是群,H是G的子集,若H在G的原有運算下也構(gòu)成一個群,則稱H是G的子群.

【例6.1.9】任何群G至少有兩個子群:

H1=G,H2={e|e∈G為單位元}.

【例6.1.10】對于乘法運算,H={1,-1}是G={1,-1,i,-i}的子群.

【例6.1.11】偶數(shù)加法群是整數(shù)Z的子群,Z是有理數(shù)加法群Q的子群,Q又是實數(shù)加法群R的子群,R是復(fù)數(shù)加法群C的子群;對乘法群而言,也有Q1

是R1的子群,R1

是C1的子群.

【例6.1.12】任選群G的一個元素a,設(shè)a的階為r,則H={a,a2,…,ar-1,ar=e}是G的子群.這樣的群H是由某個固定元素a的乘方組成的,稱為循環(huán)群,或稱H是由元素a生成的群,a叫做H的生成元.

定理6.1.2有限群的階數(shù)必能被其子群的階數(shù)整除.

6.2置換群

定義6.2.1有限集合S到自身的一個一一映射叫做一個置換例如:

說明

(1)將S中的元素ai寫在上一行(順序可任意),ai

的象寫在ai

之下,同一列的兩個元素的相對關(guān)系只要保持不變,即f(ai

)=aki,不同形式的寫法都認(rèn)為是同一個置換.如:

(2)置換就是將n個元的一種排列變?yōu)榱硪环N排列.

(3)n元集S共有n!種不同的置換.

定義6.2.2兩個置換p1、p2的乘積p1p2

定義為先做置換p1再做p2的結(jié)果.

例如,對于S={1,2,3,4},

一般來說,置換的乘法不滿足交換律,即p1、p2≠p2p1,如上例中

求復(fù)合置換的一種技巧就是更改p2各列的前后次序,使其第一行的排列與前者p1第二行的排列相同,那么復(fù)合置換p1、p2的第一行就是p1的第一行,其第二行是p2的第二行.如上例:

定理6.2.1設(shè)Sn是n元集合上的所有置換構(gòu)成的集合,則Sn關(guān)于置換的乘法構(gòu)成群,稱為n次對稱群.

證不失一般性,設(shè)S={1,2,…,n}.由置換乘法的定義知,封閉性、結(jié)合律顯然成立.其次,單位元為恒等置換

逆元素

【例6.2.1】將頂點分別為1,2,3的正三角形(見圖6.2.1)繞重心O沿逆時針方向分別旋轉(zhuǎn)0°、120°、240°,視其為頂點集{1,2,3}的置換,則有旋轉(zhuǎn)對稱映射圖6.2.1S3與正三角形的對應(yīng)示意圖

另一類是反射對稱映射,即將三角形123分別繞對稱軸1A、2B、3C翻轉(zhuǎn)180°得頂點集的另一類置換

【例6.2.2】(正方形對稱群)考察使正多邊形回到原來位置的所有可能的逆時針旋轉(zhuǎn)和翻轉(zhuǎn)動作,可以得到一個群,稱為二面體群(參見圖6.2.2).圖6.2.2正方形的剛體變換與4次置換群

第一類:旋轉(zhuǎn)對稱關(guān)系

第二類:反射對稱關(guān)系

定義6.2.3

n次對稱群的子群稱為(n次)置換群.

定義6.2.4設(shè)置換p將集合S中的a1換為a2,a2換為a3,……,ak-1換為ak,ak換為a1,稱p為k階循環(huán)置換(或輪換),記為(a1a2…ak)或(a1,a2,…,ak).

定義6.2.5設(shè)輪換p1=(a1,a2,…,ar),p2=(b1,b2,…,bs),且ai、bj互不相同,稱p1與p2不相交.

定理6.2.2不相交的兩個輪換p1、p2滿足交換律,即p1p2=p2p1.

定理6.2.3任一置換都可以唯一分解為若干個互不相交的輪換之積

證對已知置換

【例6.2.3】將編號為1~52的卡片分為1~26、27~52兩組,交錯互相插入,則這樣的交錯插入重復(fù)8次后就會恢復(fù)到原來的卡片順序.

證第一次插入相當(dāng)對1~52作一次置換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).其中最長的輪換為8階,而k階輪換重復(fù)k次后恢復(fù)原狀,故結(jié)論成立.

所以,美國的研究人員認(rèn)為,撲克牌洗7次最合適.

定義6.2.6稱2階輪換為對換(或換位).

定理6.2.4任何輪換都可以表示為若干個對換之積,但表示方式不唯一.

推論6.2.1一個置換總可以表為若干個對換的乘積.

定理6.2.5每個輪換的對換表示中,對換個數(shù)的奇偶性是唯一確定的.從而一個置換在它的不同的對換分解表示式中所含的對換個數(shù)的奇偶性是不變的.

定義6.2.7可以分解為奇數(shù)個對換之積的置換稱為奇置換,可以分解為偶數(shù)個對換之積的置換稱為偶置換

【例6.2.4】(十五子智力玩具)在一個4×4有方格的正方形盒子中放入15個可以滑動的小方格,而正方形盒子右下角為一空格.規(guī)定方格的移動規(guī)則是只準(zhǔn)與空格相鄰的方格移入空格,那么,無論怎么變動,不可能由狀態(tài)(a)中的初始“布局”變換為狀態(tài)(b)中的布局(見圖6.2.3).圖6.2.3十五子智力游戲

定理6.2.6當(dāng)n≥2時,Sn中偶置換的全體構(gòu)成一個n!/2階的子群,稱為交代群,記為An.

證先證An為群.

(1)封閉性:設(shè)p1,p2∈An,顯然p1p2∈An,因為將二者分解的結(jié)果相乘,仍得偶數(shù)個對換的乘積.

(2)結(jié)合律:An?Sn,故An中元素自然滿足結(jié)合律;

(3)單位元:因Sn中單位元e本身就是偶置換,故e∈An;

6.3.1共軛類

定義6.3.1若n次置換p可分解為互不相交的λ1個1輪換,λ2個2輪換,……,λn個n輪換,則稱p屬于(λ1,λ2,…,λn)類型,或1λ12λ2…nλn型.

類型1λ12λ2…nλn也稱為格式.

顯然

6.3伯恩賽德(Burnside)引理

定義6.3.2置換群G中屬于同一類型(λ1,λ2,…,λn)的全體置換,叫做與該類型相應(yīng)的共軛類,記為D(λ1,λ2,…,λn).

【例6.3.3】將S3按共軛情況分類的結(jié)果見表6.3.1

【例6.3.4】4次置換群G={(1)(2)(3)(4),(12),(34),(12)(34)},共有3個共軛類:

其中第2類含2個置換

定理6.3.1在n元對稱群Sn中,

證設(shè)置換p為(λ1,λ2,…,λn)型,將p用輪換表示為

(λn≤1)將n個元素1,2,…,n按上格式填入λi≠0的輪換中,應(yīng)有n!種填法.但對同一置換p,在計數(shù)時被重新統(tǒng)計.其原因有二:

(1)一個k輪換有k種不同表示形式;

(2)λk個k輪換間互換位置,有λk!種情形.

故p被重復(fù)統(tǒng)計λ1!λ2!…λk!1λ12λ2…nλn次,定理得證.

【例6.3.5】對稱群S3共有3個共軛類,即

實際結(jié)果見例6.3.3.

6.3.2不動置換類

定義6.3.3設(shè)G是集合S={1,2,…,n}上的一個置換群,k∈S,p∈G,若p(k)=k,即置換p將k變?yōu)閗,則稱k為p的不動點.G中所有以k為不動點的全體置換,構(gòu)成G的一個子集,稱為k的不動置換類(k=1,2,…,n),記為Zk.

定理6.3.2群G中關(guān)于k的不動置換類Zk

構(gòu)成一個子群.

證

(1)封閉性:若P1,P2∈Zk,則pi(k)=k,i=1,2,從而p1p2(k)=p2(p1(k))=p2(k)=k,即p1p2∈Zk.同理可證p2p1∈Zk;

(2)結(jié)合律:由于Zk?G,故結(jié)合律顯然成立;

(3)單位元:顯然e(k)=k,故e既是G的單位元,也是Zk的單位元;

(4)逆元素:若p∈Zk且p(k)=k,那么p的逆元一定存在,即p-1∈G而且必有p-1(k)=k,即p-1∈Zk.

由定義知,Zk是一個群.

另外,還知道|Zk|必整除|G|.

6.3.3等價類

定義6.3.4設(shè)G是集S={1,2,…,n}上的置換群,若存在i,j∈S,滿足p(i)=j,則稱i與j等價,記為i~j,S中與i等價的元素的全體記為Ei,稱為元素i的“軌跡”或“蹤跡”.Ei中元素的個數(shù)稱為軌跡的長度．

不難看出,元素i與j的這種等價關(guān)系滿足如下三條性質(zhì):

(1)反身性:即i~i;

(2)對稱性:若i~j,則j~i;

(3)傳遞性:若i~j,j~k,則i~k.

定理6.3.3|Ek||Zk|=|G|,k=1,2,…,n

6.3.4Burnside引理

定理6.3.4設(shè)G是n元集S={1,2,…,n}上的置換群G={p1,p2,…,pr},令λk(p)表示置換p的k階(不相交)輪換的個數(shù),則G在S上誘導(dǎo)出的等價關(guān)系將S分為不同等價類的個數(shù)為

其中λ1(p)為置換p中不動點(即1階輪換)的個數(shù).圖6.3.1正方形的2染色

【例6.3.11】制作5位數(shù)的十進制卡片(小于10000的數(shù)前面補0).其中某些不同的數(shù)可以合用一張卡片,例如數(shù)字0,1,6,8,9倒轉(zhuǎn)180°后認(rèn)為還是可讀的,像18609倒轉(zhuǎn)后讀做60981.這樣,共需多少張卡片即可表示所有的5位數(shù)?

【例6.3.12】用黃珠和藍珠穿成長度為2的直線形珠串,如果顛倒一個珠串的兩端而得到另一個珠串,則認(rèn)為二者相同,求不同的珠串?dāng)?shù).

解不考慮等價時,所有可能的珠串有{bb,by,yb,yy}=S,置換群G={p1=e,p2=顛倒置換}.即

所以,不同珠串?dāng)?shù)為

即bb,by,yy.

6.4Pólya定理

Burnside引理的前提是要列出各種涂色方案,方可利用置換的性質(zhì)將方案分為不同的等價類進行計數(shù).當(dāng)被染色的對象的個數(shù)n或顏色數(shù)m較大時,問題就變得非常復(fù)雜,且工作量很大,因為首先各種染色方案共有mn

個,一個個枚舉出來是比較困難的;其次還要找出在各種置換下互相等價的方案可能更加困難,故W.Burnside自1911年提出Burn-side引理以來,該引理在計數(shù)問題中未得到廣泛應(yīng)用.

問題設(shè)有n個對象,今用m種顏色對其染色,其中每個對象任涂一種顏色,問有多少種不同的染色方案.其中,對n個對象作某一置換,若其中一種染色方案變?yōu)榱硪环N方案,則認(rèn)為該兩個方案是相同的,或者說是等價的.

從集合與置換的角度來描述這個問題則是:S是有n個元素的集合,Q是S上的置換群,C是m種顏色的集合,用C中的顏色對S中的元素染色,對每個元素任選一色染之,共有多少種不等價的方案?

兩種方案稱為等價:指存在q∈Q,將S中元素的一種染色方案變?yōu)榱硪环N方案.

例如:q1有4個輪換因子,將每個輪換因子中的頂點染以某種顏色,由于每個輪換因子可選兩色之一,故共得24=16種方案,它恰好對應(yīng)CS中在不動置換p1作用下的λ1(p1)=16種方案,而且可以看出在恒等置換p1作用下,16種染色方案確實不等價.

同理,q2只有一個輪換因子,即4個元素涂同一種顏色,共有21=2種涂法(一般情況下,使用m種顏色,應(yīng)為m種涂法),對應(yīng)CS中在p2作用下不變的方案f1、f2.其它情形依此類推

總之,由上面的討論,可以得到以下結(jié)論:

(1)λ1(pi)=2λ(qi),i=1,2,3,4.

(2)|G|=|Q|.

定理6.4.1(Pólya定理)設(shè)Q是n個對象的一個置換群,用m種顏色涂染這n個對象,一個對象涂任意一種顏色,則在Q作用下不等價的方案數(shù)為

【例6.4.1】用紅、黃、藍三色對等邊三角形的頂點著色,共有多少種不同方案?解設(shè)針對S={1,2,3}的置換群為

所求不等價的方案數(shù)為

所有著色方案見圖6.4.1.圖6.4.1三角形頂點的3染色方案(互不等價)

若置換群為Q2={(1)(2)(3),(123),(132)},即只有旋轉(zhuǎn),沒有翻轉(zhuǎn),則不等價的方案數(shù)

比在Q1作用下的著色方案多了一個,即此時除了圖6.4.2的10種涂法外,還有一種如圖6.4.3所示的涂法,它是圖6.4.2中最后一種涂法翻轉(zhuǎn)過來的情形.由于Q2不含相應(yīng)于翻轉(zhuǎn)的置換,故在Q2作用下,二者不等價.圖6.4.2僅有旋轉(zhuǎn)置換時增加的不等價方案

若改為用4種顏色染色,則

【例6.4.2】用兩種顏色給正立方體的8個頂點著色,試問有多少種不同的方案.

解使正立方體重合的關(guān)于頂點的運動群是(參見圖6.4.3):

(1)單位元(1)(2)(3)(4)(5)(6)(7)(8),格式為(1)8;

(2)繞xx'軸旋轉(zhuǎn)±90°,可得兩個置換分別為(1234)(5678)和(4321)(8765),格式為(4)2,同類的置換共有6個;

(3)繞xx'軸旋轉(zhuǎn)180°,可得置換為(13)(24)(57)(68),格式為(2)4,同類的置換有3個;．

(4)繞yy'軸旋轉(zhuǎn)180°,可得置換為(17)(26)(35)(48),格式為(2)4,同類的置換有6個;

(5)繞zz'軸旋轉(zhuǎn)±120°,可得兩個置換分別為(136)(475)(8)(2)和(631)(574)(2)(8),格式為(1)2(3)2,同類置換有8個.

由Pólya定理,不同的染色方案數(shù)為圖6.4.3正方體8個頂點的置換示意

6.5母函數(shù)型的Pólya定理

母函數(shù)型的Pó方lya案定進理行也枚稱舉為.帶權(quán)的Pólya定理,它主要用于帶有限制條件的染色方案問題或?qū)唧w的方案進行枚舉.

首先,考慮用4種顏色涂3個編號分別為1、2、3的球,設(shè)顏色為b(藍)、g(綠)、r(紅)、y(黃).為了“詳細枚舉”各種涂色方案,用bi表示第i號球涂藍色,gi表示第i號球涂綠色,……,那么,用4種顏色染3個球的各種方案可表示如下:

右邊的每一項都代表一種染色方案,且各種方案互不相同,即互不等價.例如b1r2g3表示1號球涂藍色,2號球涂紅色,3號球涂綠色;而b1r2b3則表示1、3號球涂藍色,2號球涂紅色.欲知總共有多少種不等價的方案,也就是統(tǒng)計上式右邊有多少項.只要在等式右端令bi=gi=ri=yi=1(i=1,2,3)就可得染色方案總數(shù)L.為方便計算,從左端看,有

若只關(guān)心某方案用了哪些顏色,不關(guān)心具體對象染了什么顏色,即將各種方案按使用顏色情況“分類枚舉”,或稱“分類統(tǒng)計”.例如欲知道2個球染藍色、1個球染綠色的方案有多少個,那么,展開多項式

下面考慮分組染色的方案數(shù).問題來源于Pólya定理的推導(dǎo)過程.如上一節(jié)中用m種顏色對構(gòu)成大正方形的4個相同的小正方形進行染色,大正方形的空間變換為置換q2={旋轉(zhuǎn)180°},那么,只有當(dāng)小正方形1和3同色,2和4同色時,才能保證在q2作用下,所染的方案保持不變.這實質(zhì)上就是將不同的球先分組,同一組的球顏色相同,求不等價的染色方案數(shù).

個用3種顏色b(藍色)、r(紅色)、y(黃色)染4個不同的球,將4個球分為2組,每組2個，要求同組的球同色(如1、3號球為第一組,2、4號球為第二組),各種方案的詳細枚舉情況如下:

【例6.5.1】用三種不同顏色的珠子穿成4個珠子的項鏈,共有多少不同的方案?

解如圖6.5.1所示,使之重合的運動有關(guān)于圓環(huán)中心旋轉(zhuǎn)±90°和±180°,以及關(guān)于xx'和yy'軸翻轉(zhuǎn)180°.故有置換群G={p1,p2,…,p8},其中圖6.5.1四珠項鏈的幾何變換圖6.5.2兩藍、一紅一綠珠子組成的不等價的項鏈

【例6.5.2】由4顆紅色的珠子嵌在正六面體的4個角,試問有多少種方案.圖6.5.3正方體頂點兩種顏色數(shù)相等的2染色

6.6應(yīng)用

【例6.6.1】將兩個相同的白球和兩個相同的黑球放入兩個不同的盒子里,問有多少種不同的放法.列出全部方案.又問每盒中有兩個球的放法有多少種.

解這是一個典型的球分類相同的分配問題.即將4個球放入兩個不同的盒子,但4個球既不是全相同,也不是全不同,而是分類相同.

又如將題目改為白球兩個、黑球3個,則相應(yīng)的置換群為

【例6.6.2】用紅、黃、藍三種顏色對正六邊形的頂點進行著色,共有多少種不同的方案?其中正六邊形可以繞幾何中心旋轉(zhuǎn)或沿其對稱軸翻轉(zhuǎn).

解圖6.6.1的正六邊形可以分別繞其中心O逆時針旋轉(zhuǎn)0°、60°、120°、180°、240°、300°以及過3對頂點、3個對稱邊的中點連線翻轉(zhuǎn),從而得置換群Q所含的置換如下:圖6.6.1正六邊形頂點的置換示意

【例6.6.3】3個布爾變量x1,x2,x3的布爾函數(shù)裝置(見圖6.6.2)有多少種不同的結(jié)構(gòu)?圖6.6.23個輸入端的布爾裝置

由此可得各種狀態(tài),即集合S的置換群Q為

求不同布爾函數(shù)裝置的問題,相當(dāng)于求服從群Q的變換的8個頂點a0,a1,a2,a3,a4,a5,a6,a7用兩種顏色(相當(dāng)于布爾函數(shù)的0、1狀態(tài))對之著色的方案數(shù).故由Pólya定理,有

種方案.也就是說,三個變量的256個布爾函數(shù)中,只有80個是不等價的,其余的函數(shù)可通過改變輸入端的順序而得到.

【例6.6.4】用紅、藍兩色給正立方體的六個面著色,可得多少種不同方案?

解將正方體的上、下、左、右、前、后6個面分別編號為1、6、4、2、3、5,使正立方體的面重合的剛體運動群有以下幾種情況(參見圖6.6.3):

(1)不動置換:即單位元素(1)(2)(3)(4)(5)(6),格式為(1)6;

(2)繞過(1)和(6)面中心的AB軸旋轉(zhuǎn)±90°(圖6.6.3(a)),對應(yīng)置換為(1)(2345)(6),(1)(5432)(6),格式為(1)2(4)1.類似的面共有3對,故這種格式的置換共有6個;

(3)繞AB軸旋轉(zhuǎn)180°的置換為(1)(24)(35)(6),格式為(1)2(2)2,同類的置換有3個;

(4)繞CD軸旋轉(zhuǎn)180°(圖6.6.3(b))的置換為(16)(25)(34),格式為(2)3,而正立方體對角線位置的平行的棱有6對,故同類置換有6個;

(5)繞對角線EF旋轉(zhuǎn)±120°(圖6.6.3(c))的置換分別為(346)(152)和(643)(251),格式都是(3)2.這樣的對角線有4個,即同類置換有8個.

所以,不同的染色方案為圖6.6.3