組合數(shù)學(xué)課件：第五章 生成函數(shù)

1、1第五章 生成函數(shù)5.1 生成函數(shù)的定義和性質(zhì)5.2 組合數(shù)的生成函數(shù)5.3 指數(shù)型生成函數(shù)與多重集的排列數(shù)5.4 Catalan數(shù)列與Stirling數(shù)列的生成函數(shù)5.5 分拆數(shù)的生成函數(shù)2生成函數(shù)1720年前后，古老的方法，但應(yīng)用極為廣泛，高級(jí)的組合計(jì)數(shù)方法，離散的數(shù)列多項(xiàng)式(冪級(jí)數(shù))，離散數(shù)列間的關(guān)系=多項(xiàng)式或冪級(jí)數(shù)之間的運(yùn)算。美國(guó)著名計(jì)算數(shù)學(xué)家Wilf “一根晾衣繩”，其上掛滿(mǎn)了要展示的一列數(shù)。生成函數(shù)在多重集合的排列和組合、 遞推關(guān)系的求解、 正整數(shù)分拆、 組合恒等式證明3生成函數(shù)可解決前面的排列組合問(wèn)題。本節(jié)主要討論幾類(lèi)特殊的生成函數(shù)，即組合數(shù)序列、排列數(shù)序列、分拆數(shù)序列、組合分配

2、數(shù)序列以及排列分配數(shù)序列的生成函數(shù)，以及Catalan數(shù)和Stirling數(shù)的生成函數(shù)。4生成函數(shù)的定義Generating function（ordinary or exponential）Formal power series 例 5.1.1 求組合數(shù)數(shù)列 的生成函數(shù)， 其中 解：設(shè)要求的生成函數(shù)為G(x)，根據(jù)定義5.1.1， 由二項(xiàng)式定理， 生成函數(shù)的定義例5.1.2 無(wú)限數(shù)列 1,1,., 的生成函數(shù)。解：設(shè)要求的生成函數(shù)為G(x)，根據(jù)定義5.1.1， 由牛頓二項(xiàng)式定理的推論， 生成函數(shù)的定義例5.1.3 求數(shù)列 的生成函數(shù)，其中 解 該數(shù)列記作 ，它的生成函數(shù)是G(x)，則： 生

3、成函數(shù)的定義P52頁(yè)的牛頓二項(xiàng)式定理生成函數(shù)的定義當(dāng) n=1 時(shí)，數(shù)列 變成了例5.1.2中的無(wú)限數(shù)列 1,1,., ，其生成函數(shù) :當(dāng) n=2 時(shí)，數(shù)列 變成 ，其生成函數(shù) :n=3 , C(3+k-1,k)=C(k+2,k)=C(k+2,2)=(k+2)(k+1)/2k=0 1k=1 3k=2 6k=3 10(1-x)-3n=4 , C(4+k-1,k)=C(k+3,k)=C(k+3,3)=(k+3)(k+2)(k+1)/6(1-x)-45.1.2 生成函數(shù)的性質(zhì)生成函數(shù)數(shù)列，因此，若兩個(gè)生成函數(shù)之間存在某種關(guān)系，那么相應(yīng)的兩個(gè)數(shù)列之間也必然存在一定的關(guān)系；反之亦然。設(shè)數(shù)列 的生成函數(shù)為

4、， 數(shù)列 的生成函數(shù)為 ， 數(shù)列 的生成函數(shù)為 ，11生成函數(shù)的性質(zhì)（1）性質(zhì)1 若 則 證明 根據(jù)已知條件，有 12生成函數(shù)的性質(zhì)（2）性質(zhì)2 若 則 證明 根據(jù)已知條件，有 13生成函數(shù)的性質(zhì)（3）性質(zhì)3 若 則 證明 等式 的兩端都乘以 ，得以上各式兩邊分別相加，得 14生成函數(shù)的性質(zhì)（4）性質(zhì)4 若 則 其中 收斂 證明 因?yàn)?收斂，所以 是存在的，于是有 以上各式兩邊分別相加，得 15生成函數(shù)的性質(zhì)（5）性質(zhì)5 若 則 證明 由 的定義知 16生成函數(shù)的性質(zhì)（6）性質(zhì)6 若 則 證明 根據(jù)已知條件有 17生成函數(shù)的性質(zhì)（7）性質(zhì)7 若 則 證明 根據(jù)已知條件有 18生成函數(shù)的性質(zhì)（8

5、）性質(zhì)8 若 則 證明 根據(jù)已知條件有 19生成函數(shù)的性質(zhì)（9）性質(zhì)9 若 證明：一些數(shù)列的生成函數(shù)20 (1) (2) (3) (4) (5) (6) (7) (8) 例5.1.3 求 的生成函數(shù)解方法1：設(shè)則：所以 故 21方法222例5.1.4 已知 的生成函數(shù)為求解方法1：用多項(xiàng)式的長(zhǎng)除法得則： 所以有23方法2當(dāng)k=0時(shí)，ak=2；當(dāng)k=1時(shí)，ak=22+3=7；當(dāng)k1時(shí)，ak=2k+1+32k-1-62k-2=2k+1；24，例5.1.5 求前n個(gè)正整數(shù)的平方和解 由前面列出的第（5）個(gè)數(shù)列的生成函數(shù)有， 的生成函數(shù)為此處， 令 則由性質(zhì)3得： 的生成函數(shù)為再根據(jù)例5.1.3，25

6、性質(zhì)3比較等式兩邊 的 系數(shù)，有：26 k=n-1， k=n-25.2 組合數(shù)的生成函數(shù)我們?cè)谇懊鎺渍轮杏懻撨^(guò)三種不同類(lèi)型的組合問(wèn)題：求 的 組合數(shù)；求 的 組合數(shù)；求 的10組合數(shù)。其中:問(wèn)題（1）是普通集合的組合問(wèn)題；問(wèn)題（2）轉(zhuǎn)化為不定方程 的非負(fù)整數(shù)解的個(gè)數(shù)問(wèn)題；問(wèn)題（3）是第四章的例子，利用容斥原理來(lái)計(jì)數(shù)。它們?cè)诮忸}方法上各不相同。下面我們將看到，引入生成函數(shù)的概念后，上述三類(lèi)組合問(wèn)題可以統(tǒng)一地處理27定理 5.3.1 設(shè)多重集 ，則M的k-組合數(shù) ck 對(duì)應(yīng)序列 的生成函數(shù)為 其中， ck 為 展開(kāi)式中 的系數(shù)。28i=1, 第一個(gè)因式中j=2, 即x2表示元素a1 選取了 2次，

7、依次類(lèi)推。證明: 令 中各 的項(xiàng)分別對(duì)應(yīng)各個(gè)元素的可能取法。 展開(kāi)式中的項(xiàng) xk 具有一般形式 其中 對(duì)此方程的一非負(fù)整數(shù)解 (滿(mǎn)足條件 下 )，相應(yīng)的 就對(duì)應(yīng)了M的一個(gè)k-組合因此合并同類(lèi)項(xiàng)后， xk的系數(shù)就表示了M的k-組合數(shù) 。 29例5.2.2 用生成函數(shù)方法求多重集合 的10-組合數(shù)。解 將 的k-組合數(shù)記為 ， 的生成函數(shù)是所以， 的系數(shù) 為與第4章中用容斥原理得到的結(jié)果相同。30推論5.2.1 設(shè) ，若限定在k-組合中元素 出現(xiàn)的次數(shù)集合為 ，則從M的k-組合數(shù) 對(duì)應(yīng)序列 的生成函數(shù)為例5.2.1 利用生成函數(shù)方法求 的k-組合數(shù)。31解 設(shè) 的k-組合數(shù)為 ，則數(shù)列 的生成函數(shù)

8、為：其中 的系數(shù)就是 M 的k-組合數(shù) ， 這個(gè)結(jié)果顯然與第三章中定理3.3.3是一致的。32在普通集合 的k -組合中， 或出現(xiàn)或不出現(xiàn)，故其k -組合數(shù)數(shù)列 的生成函數(shù)為 從而例5.2.3 求 的每個(gè)元素至少取一次的k-組合數(shù)。33解 設(shè) 的每個(gè)元素至少取一次的k-組合數(shù) 對(duì)應(yīng)數(shù)列 的生成函數(shù)為 為 的系數(shù) 。34（變量替換：n+k=m）例5.2.4 求方程 的整數(shù)解的個(gè)數(shù)。解：設(shè)方程的 整數(shù)解數(shù)為 ，數(shù)列 對(duì)應(yīng)的生成函數(shù)為我們所求的是 為 展開(kāi)式中 的系數(shù)35例5.2.5 求方程 x1+2x2=15 的非負(fù)整數(shù)解的個(gè)數(shù)。解 設(shè)方程 x1+2x2=k 的非負(fù)整數(shù)解的個(gè)數(shù)為 ak , ak的

9、生成函數(shù)為 因此， a15=8.36其中，有理分式中P(x)的次數(shù)小于Q (x)的次數(shù)。例5.2.6 假定有足夠多的蘋(píng)果、香蕉、橘子和梨，用這4種水果裝成由k個(gè)水果構(gòu)成的水果袋，要求水果袋中蘋(píng)果數(shù)為偶數(shù)，香蕉數(shù)是5的倍數(shù)，橘子最多有4個(gè)，梨的個(gè)數(shù)是0或者1，求可以有多少種不同的裝法？解 設(shè)有ck種裝法，則數(shù)列ck對(duì)應(yīng)的生成函數(shù)因此，有k+1種不同的裝法。385.3 指數(shù)型生成函數(shù)與多重集的排列數(shù)當(dāng)涉及到與排列有關(guān)的問(wèn)題時(shí)，需要引入指數(shù)型生成函數(shù)。定義5.3.1 數(shù)列 的指數(shù)型生成函數(shù)定義為形式冪級(jí)數(shù)記為 或者39例如，考慮前面多次提到的數(shù)列1,1,1，根據(jù)定義5.3.1有 ，而根據(jù)高等數(shù)學(xué)的知

10、識(shí)， 因此定理 5.3.1 設(shè) ,考慮 M 的k-排列若要求在k-排列中元素 出現(xiàn)次數(shù)構(gòu)成的集合為 (1in)，則 k-排列數(shù) 對(duì)應(yīng)數(shù)列 的生成函數(shù)為 40證明根據(jù)和式的性質(zhì)，上式右端等于由多項(xiàng)式系數(shù)的組合學(xué)意義知，正是元素 出現(xiàn) 次，元素 出現(xiàn) 次 ，元素 出現(xiàn) 次的 k-排列數(shù)。故按所有可能的 求和，即得總的k-排列數(shù) 。有了定理定理 5.3.1，我們就可以方便的計(jì)算多重集的排列數(shù)41例5.3.1 求排列數(shù)數(shù)列 的指數(shù)型生成函數(shù)，其中 解：設(shè)要求的生成函數(shù)為Ge(x)，根據(jù)定義5.1.143例5.3.2 求多重集合 的k -排列數(shù)bk. ( nk )解 設(shè)數(shù)列bk 的指數(shù)型生成函數(shù)為Geb

11、k，根據(jù)定理5.3.1有， 從而 ，與第3章中的結(jié)果是一致的。44例5.3.3 計(jì)算M=4r, 5g, 6b 中r和g均出現(xiàn)奇數(shù)次 的10-排列數(shù)。解 顯然根據(jù)要求在所求的10-排列中r可能出現(xiàn)的次數(shù)為1或3，g出現(xiàn)的次數(shù)為1或3或5。若設(shè)M的k-排列數(shù)為bk，數(shù)列bk 的指數(shù)型生成函數(shù)為Gebk，則有我們要求的 是 的系數(shù)，為9660.45例5.3.4 用紅、白、藍(lán)三種顏色給1行k列棋盤(pán)涂色，并要求紅色方格的個(gè)數(shù)是偶數(shù)且至少有一個(gè)方格為白色，求涂色方案數(shù)bk，其中k為正整數(shù)。 解 設(shè)數(shù)列 的指數(shù)型生成函數(shù)為Gebk，則有因此，46例5.3.5 有3個(gè)紅球，2個(gè)黃球，3個(gè)藍(lán)球，每次從中取出4個(gè)

12、排成一行，求排列方案數(shù)。解 設(shè)每次取出k個(gè)球的排列數(shù)為 bk ，數(shù)列bk 的指數(shù)型生成函數(shù)為Gebk，則有而我們所求的即為 為 的系數(shù)，則取出4個(gè)球的排列方案有70種。475.4 Catalan數(shù)列與Stirling數(shù)列的生成函數(shù)5.4.1 Catalan數(shù)列的生成函數(shù)Catalan數(shù)首先是由Euler在精確計(jì)算對(duì)凸n邊形的不同的對(duì)角三角形剖分的個(gè)數(shù)問(wèn)題時(shí)得到的，它經(jīng)常出現(xiàn)在組合計(jì)數(shù)問(wèn)題中。例5.4.1 在一個(gè)凸n邊形中，可以用(n-3)條不在內(nèi)部相交的對(duì)角線(xiàn)將其剖分成(n-2)個(gè)三角形，問(wèn)有多少種不同的分法？C4=2,C5=548解 令 表示將一個(gè)凸(n+1)邊形剖為三角形的方法數(shù)，規(guī)定 。

13、當(dāng)n = 2時(shí)，(n+1)邊形就是三角形，不需剖分，故 當(dāng) 考慮一個(gè)凸(n+1)邊形，它的頂點(diǎn)分別用 表示，如圖5.4.1所示。取邊 ，任取頂點(diǎn) 將 分別與 之間連線(xiàn)，得三角形T，三角形T將凸(n+1)邊形分成 T，R 1和R 2 三部分，其中， R 1為(k+1)邊形， R 2為(n-k+1)邊形。因此，R 1可以用 種方法剖分，R 2 可以用 種方法剖分，所以 這正是Catalan數(shù)列的通項(xiàng)公式。4950TR2R1A1An+1Ak+2AkAk+1k+1= 2, 3, n = k= 1, 3, n -1h(k)h(n-k)A2An那么如何求 ,本節(jié)用 的生成函數(shù) 來(lái)計(jì)算。解 得51 i+j=

14、k)利用牛頓二項(xiàng)式定理，有因?yàn)?，開(kāi)方應(yīng)該取負(fù)號(hào)，故舍去顯然一個(gè)凸n+1邊形中有 種不同的剖分方法。52 我們并不陌生，在第3章中3.4節(jié)中，例3.4.6的結(jié)論是從（0，0）點(diǎn)到（n , n）點(diǎn)的除端點(diǎn)外不接觸直線(xiàn)y = x的路徑數(shù)為 ， 例3.4.7的結(jié)論是從(0,0) 點(diǎn)到（n , n）點(diǎn)的除端點(diǎn)外不穿過(guò)直線(xiàn)y = x 的路徑數(shù)為 定理：n個(gè)+1和 n個(gè)-1 構(gòu)成的2n項(xiàng)a1,a2,a2n,其部分和滿(mǎn)足 a1+a2+ak =0 (k=1,2,2n) 的數(shù)列的個(gè)數(shù)等于第n個(gè)Catalan數(shù)。53序列 的生成函數(shù)為 并有證明： 對(duì)遞歸關(guān)系 兩端同乘以 ，并對(duì)n求和，得即： 令 則有54故：從而

15、等式右端展開(kāi)后，各 項(xiàng)的一般形式為55其中， ，且 。合并同類(lèi)項(xiàng)后的 的系數(shù)為其中， 是滿(mǎn)足 非負(fù)整數(shù)解，因此56作為驗(yàn)證，我們計(jì)算 ，其中n=4，k=2，n-k=2， n1+n2=2的所有非負(fù)整數(shù)解為（0，2），（1，1），（2，0），因此 根據(jù)第3章的知識(shí)，結(jié)果顯然是正確的。57有序分拆定理 對(duì)于n的k有序分拆其k有序分拆數(shù)數(shù)列 的生成函數(shù)是這個(gè)定理等價(jià)于如下分配模型：即把n個(gè)相同的球放入k個(gè)不同的盒子里，第i個(gè)盒的容量為 ，且使每盒非空的方案數(shù)為58推論5.5.1 若對(duì)n的k有序分拆的各分量 ( ) 沒(méi)有限制，則其k有序分拆數(shù)數(shù)列 的生成函數(shù)是 ， 且 59無(wú)序分拆在3.6節(jié)中可知無(wú)序分

16、拆和有序分拆的區(qū)別在于是否考慮分拆后的各分量的順序.將n分拆為k個(gè)分部（每一分部的大小不受限制）的分拆數(shù)等于將n分拆為最大分部為k（分部個(gè)數(shù)不限）的分拆數(shù)，該分拆數(shù)也記為 60定理 令B(n)表示正整數(shù) 的所有分拆數(shù)， Bk(n)表示 n的各分部量都不超過(guò) k的分拆數(shù)，則它們相應(yīng)的生成函數(shù)分別為(1)(2)(3)61Bk(n)表示 n的各分部量都不超過(guò) k的分拆數(shù)（1） 等于不定方程 的非負(fù)整數(shù)解的個(gè)數(shù)。因此其分拆數(shù)列的生成函數(shù)為 其中展開(kāi)式中 的系數(shù)即為n的最大分項(xiàng)不超過(guò)k的分拆個(gè)數(shù)。62（2） 根據(jù)定理 3.6.3知，將n分拆為k個(gè)分部（每一分部的大小不受限制）的分拆數(shù)等于將n分拆為最大分部為k（分部個(gè)數(shù)不限）的分拆數(shù)，其分拆數(shù)相當(dāng)于求方程的整數(shù)解的個(gè)數(shù)，其生成函數(shù)為63其中展開(kāi)式中 的系數(shù)即為n的最大分項(xiàng)等于k的分拆個(gè)數(shù).其他法易證明： ，因此若 ，則 ，因此當(dāng) ，它們對(duì)應(yīng)的生成函數(shù)的系數(shù)為零，所以64推論 n 的各分部量?jī)蓛苫ゲ幌嗤姆植饠?shù)等于 n的各分部量是奇數(shù)的分拆數(shù)。證明 n的各分部量?jī)蓛苫ゲ幌嗤姆植饠?shù)的生成函數(shù)為 而 顯然是n的各分部量是奇數(shù)的分拆 數(shù)數(shù)列的生成函數(shù)，因此結(jié)論成立.66例 用1角、2角、3角的郵票貼出面值6角，求有多少種不同的方案？ 解 這是可重復(fù)的無(wú)序分拆，相應(yīng)的生成函數(shù)為顯然所求為 的系數(shù)，為7，說(shuō)明