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

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

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

3、,16,15,14,9,6,,,,,,證明 設(shè)CS是n個對象集合S={a1,a2,…,an}用m種顏色C={c1,c2,…,cm}進行涂色所得的全部方案的集合. 顯然 |CS|=mn. 對于置換群G中任何一個元素g, 它是S的一個置換, 自然也誘導(dǎo)出CS上的一個置換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|.互不等價的染色方案數(shù)正好是G*在CS上的不同軌道數(shù)目. 而要計算軌道數(shù)目, 需要應(yīng)用Burnside引理. 既然|G*|=|G|, 我們只需要計算G*中每個元素不動點數(shù)目.設(shè)g?G, 下面來計算g*的不動點的數(shù)目.不仿設(shè)置換g的輪換分解如下: g=(a,b,c, …, p, q)(r,s,…, t)…(u

5、,v,…,w),,8,,,,,,如果f?CS在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一定把

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

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

8、方案可形式地表示為(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ù)目.,12,,,,,,只要把上

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

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

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

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

13、, (v1v2) (v3v4), (v1v4) (v2v3),(v1v2v3v4), (v4v3v2v1), 共有4種類型的置換, 容易寫出其輪換指標公式:,,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種不同的染色方案, 不同類項數(shù)為15, 說明有15種不同的用色方案.每項的系數(shù)說明這種用色方案所能染出的不等價的類型. 例如其中b2rg的系數(shù)為2, 說明由兩顆藍色

15、珠子、紅和綠各一顆組成的方案有2.,21,,,,,,例3 由4顆紅色的珠子嵌在正六面體的4個角. 試求有多少種方案？解 問題相當(dāng)于用兩種顏色對正六面體的頂點著色. 求兩種顏色相等的方案數(shù). (1) 保證運動后六面體位置與原來重合的置換群G的的階數(shù)為24. 其類型為: (1)8的1個, (4)2的6個, (2)4的9個, (1)2(3)2的8個.(2) 求出母函數(shù)形式Polya公式中b4r4項的系數(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)的方案略.以上都是一些簡單的應(yīng)用實際例題. 下面我們要給出Polya定理的兩個重 要的應(yīng)用.,23,,,,,,布爾(Boole)函數(shù)在現(xiàn)代計算機邏輯電路的設(shè)計中有很重要的應(yīng)用.

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

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

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

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

21、2)(x1x3), h6=(x3)(x1x2).而3個布爾變量x1,x2,x3構(gòu)成的3位二進制數(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)對應(yīng)于置換：,,,

22、采用這種方式, S3中的置換h可以誘導(dǎo)變量上的一個置換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個變量全部布爾函數(shù)集合上的置換.,31,,,,,,求互不等價的布爾函數(shù)的問題. 相當(dāng)于求在S3所誘導(dǎo)出的置換群G作用下, 8個元素a0,a1,a2, a3,a4,a5,a6,a7用兩種不同顏色（相當(dāng)于布爾函數(shù)的0,1狀態(tài)）著色的不同方案數(shù)

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

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