本文格式為Word版，下載可任意編輯——組合數(shù)學之母函數(shù)形式Polya定理及其應(yīng)用

《組合數(shù)學》第十一講

母函數(shù)形式Polya定理及其應(yīng)用

第十一講:內(nèi)容提要I.Polya定理及其證明*II.母函數(shù)形式的Polya定理

III.Boole函數(shù)的計數(shù)IV.圖簡單圖的計數(shù)*

I.Plya定理及其證明*Plya定理設(shè)G是n元集合S上的置換群,CS是用集合C中m種顏色對S中元素進行染色的全部方案組成的集合,則CS中在G作用下互不等價的染色方案數(shù)為:PG(m,m,,m)|G|1

gG

m

c(g)

其中PG(x1,x2,…,xn)為置換群G的輪換指標,c(g)是置換g中不相交輪換總數(shù).若g的類型為(c1,c2,…,cn),則c(g)=c1+c2+…+cn.我們給出的其實是特別形式的Polya定理,更一般形式的是帶權(quán)的形式.可以用來計算有條件限制的計數(shù)問題.下面我們簡單介紹Polya定理的證明.4

15913

261014

371115

4812165

證明設(shè)CS是n個對象集合S={a1,a2,…,an}用m種顏色C={c1,c2,…,cm}進行涂色所得的全部方案的集合.顯然|CS|=mn.對于置換群G中任何一個元素g,它是S的一個置換,自然也誘導出CS上的一個置換g*.具體方式:g*:ffg,fCS.即：g*(f)=fg,或：(g*(f))(a)=f(g(a)),aS.6

G*={g*|gG}構(gòu)成CS的一個置換群,而且|G*|=|G|.互不等價的染色方案數(shù)正好是G*在CS上的不同軌道數(shù)目.而要計算軌道數(shù)目,需要應(yīng)用Burnside引理.既然|G*|=|G|,我們只需要計算G*中每個元素不動點數(shù)目.設(shè)gG,下面來計算g*的不動點的數(shù)目.不仿設(shè)置換g的輪換分解如下:g=(a,b,c,…,p,q)(r,s,…,t)…(u,v,…,w),7

假使fCS在g*下不動,即g*(f)=f,那么f(b)=f(g(a))=f(a),類似可以得到f(c)=…=f(p)=f(q)=f(a).說明輪換(a,b,c,…,p,q)中的元素顏色一致.同樣有,f(r)=f(s)=…=f(t);…;f(u)=f(v)=…=f(w).由此可見,假使f是g*的一個不動點,那么f一定把位于置換g的同一個輪換中的元素染成了同樣的顏色.8

反過來,假使f把位于g的同一個輪換中的元素染成同樣的顏色,則必然是g*的不動點.這樣g*不動點的數(shù)目就等于這樣染色的數(shù)目,它把g的同一個輪換中的元素染同樣的顏色.由于g有c(g)個輪換,每個輪換可以染一種顏色,共有mc(g)種不同的染色方案.所以,c1(g*)=mc(g).由Burnside引理可以得到結(jié)論.9

II.母函數(shù)形式的Plya定理我們這里給出的Polya計數(shù)定理其實是一種特別形式.一般形式的Polya定理還可以用來解決有條件限制而且相互不等價的染色方案數(shù)目.還有一個問題是如何列舉出所有不同類型的染色方案?顯然Polya定理無法告訴我們這些.它只能告訴我們總數(shù).母函數(shù)形式Polya定理可以滿足這個要求.10

先通過一個簡單例題說明思想.例1.假設(shè)要用b,g,r,y這4種顏色涂染3個同樣的球,則所有方案可形

式地表示為(b+g+r+y)3.由于三個球無區(qū)別,故乘法是可交換的,例如b2g=gb2.把這個形式展開:(b+g+r+y)3=b3+g3+r3+y3+3b2g+3b2r+3b2y+3g2b+3g2r+3g2y+3r2b+3r2g+3r2y+3y2g+3y2r+3y2b+6bgr+6bgy+6brg+6gry展開式中的不同項表示不同的方案,每項系數(shù)表示該方案的數(shù)目.11

只要把上面這種思想方法用于Polya定理,就可以得到母函數(shù)形式Polya定理.設(shè)G是n個對象集合S={a1,a2,…,an}上的一個置換群,要用m種顏色b1,b2,,bm進行染色,我們需要探討并決定互不等價的染色方案的狀況.根據(jù)Polya定理,不等價的染色方案數(shù)目可以通過下面的公式得到:PG(m,m,,m)|G|1

gG

m

c(g)12

其中c(g)是置換g的輪換總數(shù)目,而PG(x1,x2,,xn)|G|1

gG

x1x2xn

c1

c2

cn

是置換群G的輪換指標.假使置換g的類型為:(c1(g),c2(g),…,cn(g)),c(g)=c1(g)+c2(g)+…+cn(g),我們知道m(xù)c(g)

m

c1(g)

m

c2(g)

m

cn(g)13

其含義是讓置換g的ci個長為i的輪換中每個輪換中的元素染同樣的顏色,這是為了得到由g誘導出的置換g*的不動點.當時我們并不關(guān)注這個同樣的顏色究竟是哪一種顏色.現(xiàn)在我們想列舉出染色方案狀況,就需要關(guān)注這個問題.根據(jù)方才例題的思想,對應(yīng)于置換g的每個長為i的輪換因子,其中i個元素的顏色可以形式的表示為:b1b2bmiii14

既然g有ci=ci(g)個長為i的輪換,自然長為i的輪換中出現(xiàn)的元素的染色方案可以形式的表示為:(b1b2bm)iiici(g)

考慮到g的全部輪換分解狀況,相應(yīng)于置換g的染色方案可以形式表示為:(b1b2bm)c1(g)

(b1b2bm)nnn

cn(g)

由此可以知道,總的染色方案的列舉只要在輪換指標中令:xib1b2bmiii15

即可得到能列舉出方案狀況的母函數(shù)形式的Polya定理:p|G|1

gG

(b1bm)

c1(g)

(b1bm)nn

cn(g)

這就是母函數(shù)形式的Polya定理的計數(shù)公式,在具體應(yīng)用中展開并依照同類項整理,即可列舉出不同的方案情況和數(shù)目.下面通過一個例題來說明.16

例2有3種不同顏色的珠子,用它們串成4個珠子的項鏈.問一共能串成多少種不同類型的項鏈?列舉出全部不同類型的方案.v4v1

v3

v2

解先要確定保持圖形與原來位置重合的置換群G.17

簡單看出來使得項鏈運動前后重合的置換群G含有以下8個置換:(v1)(v2)(v3)(v4),(v2)(v4)(v1v3),(v1)(v3)(v2v4),(v1v3)(v2v4),(v1v2)(v3v4),(v1v4)(v2v3),(v1v2v3v4),(v4v3v2v1),

共有4種類型的置換,簡單寫出其輪換指標公式:PG(x1,x2,x3,x4)18(x12x1x2

3x22x4),422

總方案數(shù)PG(3,3,3)18(34

23

3

33