組合數(shù)學(xué)之母函數(shù)形式polya定理及其應(yīng)用

1、1,《組合數(shù)學(xué)》,第十一講,母函數(shù)形式Polya定理及其應(yīng)用,,,,2,第十一講: 內(nèi)容提要,III. Boole函數(shù)的計(jì)數(shù),II. 母函數(shù)形式的Polya定理,IV. 圖簡(jiǎn)單圖的計(jì)數(shù)*,I. Polya定理及其證明*,3,,,,,,Pòlya定理 設(shè)G是n元集合S上的置換群, CS是用集合C中m種顏色對(duì)S中元素進(jìn)行染色的全部方案組成的集合, 則CS中在G作用下互不等價(jià)的染色方案數(shù)為:,I. Pòlya定理及

2、其證明*,4,,,,,,其中PG(x1,x2,…,xn)為置換群G的輪換指標(biāo), c(g)是置換g中不相交輪換總數(shù). 若g的類型為(c1,c2,…,cn), 則 c(g)=c1+c2+…+cn.我們給出的其實(shí)是特殊形式的Polya定理, 更一般形式的是帶權(quán)的形式. 可以用來(lái)計(jì)算有條件限制的計(jì)數(shù)問(wèn)題.下面我們簡(jiǎn)單介紹Polya定理的證明.,,5,1,2,3,4,5,6,7,8,10,11,12,13

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

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

5、,v,…,w),,8,,,,,,如果f?CS在g*下不動(dòng), 即g*(f)=f, 那么f(b)=f(g(a))=f(a), 類似可以得到 f(c) =…=f(p)=f(q)=f(a). 說(shuō)明輪換(a, b, c, …, p, q)中的元素顏色相同. 同樣有, f(r)=f(s)=…=f(t); …; f(u)=f(v)=…=f(w). 由此可見, 如果f是g*的一個(gè)不動(dòng)點(diǎn), 那么f一定把

6、位于置換g的同一個(gè)輪換中的元素染成了同樣的顏色.,9,,,,,,反過(guò)來(lái), 如果f把位于g的同一個(gè)輪換中的元素染成同樣的顏色, 則必然是g*的不動(dòng)點(diǎn). 這樣g*不動(dòng)點(diǎn)的數(shù)目就等于這樣染色的數(shù)目, 它把g的同一個(gè)輪換中的元素染同樣的顏色. 因?yàn)間有c(g)個(gè)輪換, 每個(gè)輪換可以染一種顏色, 共有mc(g)種不同的染色方案. 所以, c1(g*)=mc(g). 由Burnside引理可以得到結(jié)論. ?,10,,,,,,我們這里給出的Po

7、lya計(jì)數(shù)定理其實(shí)是一種特殊形式. 一般形式的Polya定理還可以用來(lái)解決有條件限制而且互相不等價(jià)的染色方案數(shù)目. 還有一個(gè)問(wèn)題是如何列舉出所有不同類型的染色方案? 顯然Polya定理無(wú)法告訴我們這些. 它只能告訴我們總數(shù). 母函數(shù)形式Polya定理可以滿足這個(gè)要求.,II. 母函數(shù)形式的Pòlya定理,11,,,,,,先通過(guò)一個(gè)簡(jiǎn)單例題說(shuō)明思想. 例1. 假設(shè)要用b, g, r, y這4種顏色涂染3個(gè)同樣的球, 則所有

8、方案可形式地表示為(b+g+r+y)3. 由于三個(gè)球無(wú)區(qū)別, 故乘法是可交換的, 例如b2g=gb2. 把這個(gè)形式展開: (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展開式中的不同項(xiàng)表示不同的方案, 每項(xiàng)系數(shù)表示該方案的數(shù)目.,12,,,,,,只要把上

9、面這種思想方法用于Polya定理, 就可以得到母函數(shù)形式Polya定理. 設(shè)G是n個(gè)對(duì)象集合S={a1,a2,…,an}上的一個(gè)置換群, 要用m種顏色b1,b2,?, bm進(jìn)行染色, 我們需要討論并決定互不等價(jià)的染色方案的情況. 根據(jù)Polya定理, 不等價(jià)的染色方案數(shù)目可以通過(guò)下面的公式得到:,,13,,,,,,其中c(g)是置換g的輪換總數(shù)目, 而,是置換群G的輪換指標(biāo). 如果置換g的類型為: (c1(g),c2(g)

10、,…,cn(g)), c(g)=c1(g)+c2(g)+…+cn(g),我們知道,,,14,,,,,,其含義是讓置換g的ci個(gè)長(zhǎng)為i的輪換中每個(gè)輪換中的元素染同樣的顏色, 這是為了得到由g誘導(dǎo)出的置換g*的不動(dòng)點(diǎn). 當(dāng)時(shí)我們并不關(guān)注這個(gè)同樣的顏色究竟是哪一種顏色. 現(xiàn)在我們想列舉出染色方案情況, 就需要關(guān)注這個(gè)問(wèn)題. 根據(jù)剛才例題的思想, 對(duì)應(yīng)于置換g的每個(gè)長(zhǎng)為i的輪換因子, 其中i個(gè)元素的顏色可以形式的表示為:,,15,,

11、,,,,既然g有ci=ci(g)個(gè)長(zhǎng)為i的輪換, 自然長(zhǎng)為i的輪換中出現(xiàn)的元素的染色方案可以形式的表示為:,考慮到g的全部輪換分解情況, 相應(yīng)于置換g的染色方案可以形式表示為:,,,由此可以知道, 總的染色方案的列舉只要在輪換指標(biāo)中令:,,16,,,,,,即可得到能列舉出方案情況的母函數(shù)形式的Polya定理:,,這就是母函數(shù)形式的Polya定理的計(jì)數(shù)公式, 在具體應(yīng)用中展開并按照同類項(xiàng)整理, 即可列舉出不同的方案情況和數(shù)目. 下面通過(guò)

12、一個(gè)例題來(lái)說(shuō)明.,17,,,,,,例2 有3種不同顏色的珠子, 用它們串成4個(gè)珠子的項(xiàng)鏈. 問(wèn)一共能串成多少種不同類型的項(xiàng)鏈? 列舉出全部不同類型的方案.,解 先要確定保持圖形與原來(lái)位置重合的置換群G.,,,,,v1,v2,v3,v4,18,,,,,,容易看出來(lái)使得項(xiàng)鏈運(yùn)動(dòng)前后重合的置換群G含有以下8個(gè)置換:(v1)(v2)(v3)(v4),(v2)(v4)(v1v3), (v1)(v3)(v2v4), (v1v3) (v2v4)

13、, (v1v2) (v3v4), (v1v4) (v2v3),(v1v2v3v4), (v4v3v2v1), 共有4種類型的置換, 容易寫出其輪換指標(biāo)公式:,,19,,,,,,總方案數(shù),如果要列舉出具體方案情況, 需要利用母函數(shù)形式的Polya定理. 為書寫方便, 我們用b, r, g分別表示這三種顏色. 具體的方案需要展開下面的式子: P=8-1[(b+g+r)4 + 2(b+g+r)2(b2+g2+r2)

14、 + 3(b2+g2+r2)2 + 2(b4+g4+r4)],,20,,,,,,展開式如下: P=b4+g4+r4+b3r+b3g+br3+r3g+bg3+rg3 +2b2r2+2b2g2+2r2g2+2b2rg+2br2g+2brg2這里列舉出了全部21種不同的染色方案, 不同類項(xiàng)數(shù)為15, 說(shuō)明有15種不同的用色方案.每項(xiàng)的系數(shù)說(shuō)明這種用色方案所能染出的不等價(jià)的類型. 例如其中b2rg的系數(shù)為2, 說(shuō)明由兩顆藍(lán)色

15、珠子、紅和綠各一顆組成的方案有2.,21,,,,,,例3 由4顆紅色的珠子嵌在正六面體的4個(gè)角. 試求有多少種方案？解 問(wèn)題相當(dāng)于用兩種顏色對(duì)正六面體的頂點(diǎn)著色. 求兩種顏色相等的方案數(shù). (1) 保證運(yùn)動(dòng)后六面體位置與原來(lái)重合的置換群G的的階數(shù)為24. 其類型為: (1)8的1個(gè), (4)2的6個(gè), (2)4的9個(gè), (1)2(3)2的8個(gè).(2) 求出母函數(shù)形式Polya公式中b4r4項(xiàng)的系數(shù):,22,,,,,,

16、P=(1/24)?[(b+r)8+6(b4+r4)2+9(b2+r2)4 +8(b+r)2(b3+r3)2]其中b4r4的系數(shù)為(1/24)?[C(8,4)+12+9C(4,2)+8C(2,1)C(2,1)]=7相應(yīng)的方案略.以上都是一些簡(jiǎn)單的應(yīng)用實(shí)際例題. 下面我們要給出Polya定理的兩個(gè)重 要的應(yīng)用.,23,,,,,,布爾(Boole)函數(shù)在現(xiàn)代計(jì)算機(jī)邏輯電路的設(shè)計(jì)中有很重要的應(yīng)用.

17、n個(gè)變量的Boole函數(shù)f(x1,x2,…,xn)就是集合Z2n={(x1,x2,…,xn)|xi=0或1; i=1, 2,…,n} 到集合Z2={0,1}的一個(gè)映射. n個(gè)變量的不同Boole函數(shù)總數(shù):,III. Boole函數(shù)及其等價(jià)分類,布爾量0與1的基本運(yùn)算有三種: 加法, 乘法與取補(bǔ), 分別定義如下:,24,,,,,,加法: 1+x=1, 0+x=x; 乘法: 1?x=x, 0?x=0取補(bǔ): ?1=0, ?0=1.如果一

18、個(gè)布爾函數(shù)可以通過(guò)另外一個(gè)布爾函數(shù)通過(guò)置換變量而得到, 則稱這兩個(gè)布而函數(shù)等價(jià). 也就是說(shuō), 如果存在p?Sn使得兩個(gè)布而函數(shù)f與h滿足: f(x1,x2,…,xn)= g(xp(1),xp(2) ,…,xp(n) ), 則稱f與h等價(jià). 等價(jià)的布爾函數(shù), 不需要改變函數(shù)本身, 只需要改變輸入變量的順序就可以由一個(gè)函數(shù)實(shí)現(xiàn)另一個(gè)函數(shù)的功能.,25,,,,,,例如: f(x1,x2,x3)=x1+x2x3

19、與g(x1,x2,x3)=x2+x3x1等價(jià), 因?yàn)間(x1,x2,x3)= f(x2,x3,x1).取補(bǔ)型等價(jià). 例如f(x1,?x2,x3)與f(x1,x2,x3)取補(bǔ)等價(jià).取補(bǔ)與下標(biāo)置換混合等價(jià). 可以利用Polya定理, 通過(guò)這些等價(jià)所對(duì)應(yīng)的置換群得出等價(jià)類型的數(shù)目. 我們不打算詳細(xì)推導(dǎo)這些情況.下面只針對(duì)下標(biāo)置換等價(jià)意義下布爾等價(jià)類的計(jì)數(shù)給出一個(gè)例子.,26,,,,,,求3個(gè)布爾變量x1, x2, x3的布爾函數(shù)在下標(biāo)

20、置換意義下不同的等價(jià)類型的個(gè)數(shù)? 3個(gè)變量的布爾函數(shù)有28=256個(gè). 但布爾函數(shù)f(x1,x2,x3)的裝置可以通過(guò)改變輸入端的順序而得到.不必改變裝置本身的內(nèi)容.布爾函數(shù)f(x1,x2,x3) 中的3個(gè)變量上的置換群就是3次對(duì)稱群S3共有6個(gè)置換:,27,,,,,,h1=(x1)(x2)(x3), h2=(x1x2x3), h3=(x3 x2 x1), h4=(x1)(x2x3), h5=(x

21、2)(x1x3), h6=(x3)(x1x2).而3個(gè)布爾變量x1,x2,x3構(gòu)成的3位二進(jìn)制數(shù)x1x2x3的狀態(tài)有23=8種： a0=0 0 0, a1=0 0 1, a2=0 1 0, a3=0 1 1, a4=1 0 0, a5=1 0 1, a6=1 1 0, a7=1 1 1.以在h2=(x1 x2 x3)的作用下為例：,28,,,,,,,29,,,,,,即h2=(x1x2x3)對(duì)應(yīng)于置換：,,,

22、采用這種方式, S3中的置換h可以誘導(dǎo)變量上的一個(gè)置換p, 即:hi?pi, i=1,2,?,6.,30,,,,,,下面是S3誘導(dǎo)出的置換群G的元素: p1=(a0) (a1) (a2) (a3) (a4) (a5) (a6) (a7) p2=(a0) (a1a2a4) (a3a6a5) (a7) p3=(a0) (a1a4a2) (a3a5a6) (a7) p4=(a0) (a1a2) (a3) (a4) (

23、a5a6) (a7) p5=(a0) (a1a4) (a2) (a3a6) (a5) (a7) p6=(a0) (a1)(a2a4) (a3a5) (a6) (a7)當(dāng)然這些置換也誘導(dǎo)出3個(gè)變量全部布爾函數(shù)集合上的置換.,31,,,,,,求互不等價(jià)的布爾函數(shù)的問(wèn)題. 相當(dāng)于求在S3所誘導(dǎo)出的置換群G作用下, 8個(gè)元素a0,a1,a2, a3,a4,a5,a6,a7用兩種不同顏色（相當(dāng)于布爾函數(shù)的0,1狀態(tài)）著色的不同方案數(shù)

24、. 可以運(yùn)用Polya定理. 輪換指標(biāo):,N=(1/6)?(28+3?26+2?24)=480/6=80.所以3元布爾函數(shù)不等價(jià)的是80種.,32,,,,,,圖的計(jì)數(shù)問(wèn)題是一個(gè)很復(fù)雜的問(wèn)題. 很難給出一個(gè)通用的公式, 這里簡(jiǎn)單介紹思想方法. 要計(jì)數(shù)的圖類—給定點(diǎn)數(shù)、簡(jiǎn)單（無(wú)重邊, 無(wú)環(huán)）、無(wú)向圖. 要計(jì)算不同構(gòu)的圖的數(shù)目.兩個(gè)圖G1=(V1,E1), G2=(V2,E2)同構(gòu)?存在雙射?:V1?V2使得(vi,vj)?V1 ?

25、 (?(vi), ?(vj))?V2.,IV*. 圖的計(jì)數(shù),33,,,,,,n個(gè)頂點(diǎn)標(biāo)記為1,2,…,n的完全圖共有n(n-1)/2條邊. 可設(shè)想通過(guò)用0,1兩種顏色對(duì)完全圖的邊進(jìn)行染色來(lái)得到任意一個(gè)圖. 染1色的看作有邊, 染0色看作無(wú)邊. 設(shè)有標(biāo)號(hào)的圖全體為?,則|?|= 2n(n-1)/2.Sn為頂點(diǎn)集合上的對(duì)稱群, 可以誘導(dǎo)出在?上的作用.同構(gòu)計(jì)數(shù)就是要計(jì)算Sn在?上的軌道數(shù)目.,34,例1 三個(gè)點(diǎn)的無(wú)向圖,S3={(v