組合數(shù)學(xué)講義 2章 母函數(shù)

1、組合數(shù)學(xué) 第二章 母函數(shù)第二章 母函數(shù)及其應(yīng)用問題：對于不盡相異元素的部分排列和組合，用第一章的方法是比較麻煩的（參見表2.0.1）。新方法：母函數(shù)方法。表2.0.1條件組合方案數(shù)排列方案數(shù)對應(yīng)的集合相異元素，不重復(fù)相異元素，可重復(fù)S不盡相異元素（有限重復(fù)）特例rn1S，,n1n2nmn，nk1,(k1,2, m)r1mm所有r至少有一個滿足1< r基本思想：把離散的數(shù)列同多項式或冪級數(shù)一一對應(yīng)起來，從而把離散數(shù)列間的結(jié)合關(guān)系轉(zhuǎn)化為多項式或冪級數(shù)之間的運算。2.1 母 函 數(shù)（一） 母函數(shù)（1）定義【定義2.1.1】 對于數(shù)列，稱無窮級數(shù)為該數(shù)列的（普通型）母函數(shù)，簡稱普母函數(shù)或母函數(shù)。

2、（2）例【例2.1.1】 有限數(shù)列（r0,1,2, ,n）的普母函數(shù)是?！纠?.1.2】 無限數(shù)列1，1，1，的普母函數(shù)是（3）說明 可以為有限個或無限個； 數(shù)列與母函數(shù)一一對應(yīng)；例如，無限數(shù)列0，1，1，1，的普母函數(shù)是 將母函數(shù)只看作一個形式函數(shù)，目的是利用其有關(guān)運算性質(zhì)完成計數(shù)問題，故不考慮“收斂問題”，而且始終認為它是可“逐項微分”和“逐項積分”的。（4）常用母函數(shù) ak ，k0,1, G(x) ak ，k0,1, G(x)ak1ak akakkak k1akk(k1)ak k 2ak k(k1)(k2)ak ，任意a0 0，ak -ln(1- a x)ak ，任意ak ak ak a

3、k （二） 組合問題（1）組合的母函數(shù)定理2.1.1 組合的母函數(shù)：設(shè),且n1n2nmn，則S的r可重組合的母函數(shù)為 (2.1.1)其中，r可重組合數(shù)為之系數(shù)，r0,1,2, ,n .理論依據(jù)：多項式的任何一項與組合結(jié)果一一對應(yīng)（見例2.1.3）定理2.1.1的優(yōu)點： 將無重組合與重復(fù)組合統(tǒng)一起來處理； 使處理可重組合的枚舉問題變得非常簡單。（2）特例推論1 ，則r無重組合的母函數(shù)為G(x) (1x)n (2.1.2)組合數(shù)為之系數(shù)。推論2 ，則r無限可重組合的母函數(shù)為G(x) (2.1.3)組合數(shù)為x r之系數(shù)。推論3 ，每個元素至少取一個，則r可重組合（rn）的母函數(shù)為G(x) (2.1.

4、4)組合數(shù)為xr之系數(shù)。推論4 ，每個元素出現(xiàn)非負偶數(shù)次，則r可重組合的母函數(shù)為G(x) (2.1.5)組合數(shù)為x r之系數(shù)=推論5 ，每個元素出現(xiàn)奇數(shù)次，則r可重組合的母函數(shù)為G(x) (2.1.6)組合數(shù)為x r之系數(shù)推論6 設(shè)S=,且n1n2nmn，要求元素至少出現(xiàn)次，則S的r可重組合的母函數(shù)為G(x) (2.1.7)其中，r可重組合數(shù)為之系數(shù)，rk,k1,n，kk1k2km。（3）一般情形：設(shè)S=20.a，30.b，.c，并設(shè)元素a只能出現(xiàn)15，10，13，16次，b只允許出現(xiàn)奇數(shù)次，c至少出現(xiàn)5次且必須出現(xiàn)偶數(shù)次，求S的r可重組合的母函數(shù)。G(x)（三） 應(yīng)用【例2.1.3】 設(shè)有2

5、個紅球，1個黑球，1個白球，問（1） 共有多少種不同的選取方法，試加以枚舉？（2） 若每次從中任取3個，有多少種不同的取法？解 （1）設(shè)想用x，y，z分別代表紅、黑、白三種球，兩個紅球的取法與x0，x1，x2對應(yīng)起來，即紅球的可能取法與1xx2中x的各次冪一一對應(yīng)，亦即x01表示不取，x表示取1個紅球，x2表示取兩個。對其它球，依此類推。則母函數(shù)G(x,y,z) (1xx2) (1y) (1z)1(xyz)(x2xyxzyz)(x2yx2zxyz)( x2yz)共有5種情況，即 數(shù)字1表示一個球也不取的情況，共有1種方案； 取1個球的方案有3種，分別為紅、黑、白三種球只取1個； 取2個球的方案

6、有4種，即2紅、1紅1黑、1紅1白、1黑1白； 取3個球的方案有3種，即2紅1黑、2紅1白、三色球各一； 取4個球的方案有1種，即全取。若令xyz1，就得所有不同的選取方案總數(shù)為G(1,1,1) 1343112（2）若只考慮每次取3個的方案數(shù)，而不需枚舉，則令yx，zx，便有G(x) (1xx2) (1x) (1x) 13x4 x23 x3 x4由x3的系數(shù)即得所求方案數(shù)為3?！纠?.1.4】 有18張戲票分給甲、乙、丙、丁4個班（不考慮座位號），其中甲、乙兩班最少1張，甲班最多5張，乙班最多6張，丙班最少2張，最多7張，丁班最少4張，最多10張，問有多少種不同的分配方案？解 （1）問題分析：

7、這實質(zhì)上是由甲、乙、丙、丁四類共28個元素中可重復(fù)地取18個元素的組合問題。其中，m4，nn1n2n3n45671028，k 11248，r18。（2）求解：由推論6知相應(yīng)的母函數(shù)為G(x)x8140 x18x28所以，共有140種分配方案。（3）特殊情況處理：若將戲票數(shù)改為r4張，各班所分戲票的下限數(shù)0（i1,2,3,4），這時G1(x)與G2(x) 中的系數(shù)是一樣的，因為將擴展為并不影響的系數(shù)，故用G2(x)計算要比用G1(x)方便得多。同理，當(dāng)r6時，可以用G3(x) 來代替G1(x)求的系數(shù)。【例2.1.5】 從n雙互相不同的鞋中取出r只（），要求其中沒有任何兩只是成對的，問共有多少種

8、不同的取法？解解法一：用母函數(shù)方法。即視為，但同類中的兩個不一樣，即S應(yīng)為故其r重組合的母函數(shù)為G(x)(12x)n即不同的取法共有種。由于每類元素最多只能出現(xiàn)一次，故G(x) 中不能有項，再由同雙的兩只鞋子有區(qū)別知，x的系數(shù)應(yīng)為2。解法二：用排列組合。先從n雙鞋中選取r雙，共有種選法，再從此r雙中每雙抽取一只，有種取法，由乘法原理，即得結(jié)果同上。解法三：仍用排列組合。先取出k只左腳的鞋，再在其余雙鞋中取出只右腳的鞋，即得取法數(shù)為=由此得組合恒等式此類問題的一般提法是：設(shè)集合S中共有m類元素，其中第類有個，且同類的元素也互不相同，即S?，F(xiàn)從中取出r個，若規(guī)定第類元素不能少于個，則S的r組合的母

9、函數(shù)為G(x) 例如， 把5本相同的書分給甲、乙、丙3個班，再發(fā)到個人手上，每人最多發(fā)一本。考慮將分給某班的某本書發(fā)給該班的同學(xué)A與將其發(fā)給同學(xué)B被認為是不同的分法（每個同學(xué)最多一本），而且甲、乙兩班最少1本，甲班最多5本，乙班最多6本，丙班最少2本，最多9本，問有多少種不同的分配方案？這時，S，n56920，k1124，r5。故r組合母函數(shù)為，G(x)10807380所以，共有7380種分配方案。說明：這里不能認為此問題等價于從20個相異元素中不重復(fù)地抽取5個元素，那么，答案應(yīng)為15,504了。【例2.1.6】 甲、乙、丙3人把n（n3）本相同的書搬到辦公室，要求甲和乙搬的本數(shù)一樣多，問共有

10、多少種分配的方法？（解）（1）分析：組合問題：從集合中可重復(fù)地選取n個元素，但要求與的個數(shù)一樣多，求不同的選取方案數(shù)。核心：限制盒子之間的關(guān)系。（2）特例：n1，1種分法，甲和乙都分0本（丙1本）。n2，2種分法：甲和乙分0本（丙2本）或甲和乙1本（丙0本）。當(dāng)n3時，分法2種。當(dāng)n4或5，3種分法：甲和乙都分0本、1本或2本。（3）一般情形：視為2個大盒子A、B，且A又分為2個小盒子。分兩步分配：第一步：A盒子分偶數(shù)本，B盒子分任意本；第二步：將分給A盒的書再給甲、乙各分一半。A（2k本）B（n2k本）甲（k本）乙（k本）丙（n2k本）所以，不同的分配方法共有種。（待定系數(shù)法：分解有理多項式

11、。例= = =，比較同次冪系數(shù)得方程組，解之得A=B=1/4，C=1/2）【例2.1.7】 證明組合等式（1）n2n1 (2.1.8)（2）n(n1)2n2 (2.1.9)（3），nm (2.1.10)證 (1)在二項式 的兩端對x求導(dǎo)可得 (2.1.11)令x1,即得式(2.1.8)。（2）再給式(2.1.11)兩端同乘以x后并求導(dǎo)得也令x1,即得式(2.1.9)。（3） 因為 即比較兩邊的常數(shù)項，即得公式(2.1.10)。2.2 母函數(shù)的性質(zhì)由于母函數(shù)與它的生成數(shù)列之間是一一對應(yīng)的，因此，若兩個母函數(shù)之間存在某種關(guān)系，則對應(yīng)的生成數(shù)列之間也必然存在相應(yīng)的關(guān)系。反之亦然。利用這類對應(yīng)關(guān)系，常

12、常能幫助我們構(gòu)造出某些指定數(shù)列的母函數(shù)的有限封閉形式。特別地，還能得到一些求和的新方法。設(shè)數(shù)列a k、b k、c k的母函數(shù)分別為A(x)、B(x)、C(x)，且都可逐項微分和積分。性質(zhì)1 若（即），則B(x)。（證）B(x) 分析：向右移r個位置且前面補0性質(zhì)2 若，則B(x) 證 B(x)b0b1 xb2 x 2arar1 x ar2x 2( ar x rar1 x r1 ar2x r2)分析：向左移r個位置且前面舍掉性質(zhì)3 若，則B(x) 。（證） 給等式的兩端都乘以并分別相加，得k0: k1: k2: kn: )即 B(x)例，已知A(x)1xx 2x n， (1)令k1那么易得B(x

13、)12x3x 2即 B(x)同理，令ck12(k1)，可得C(x)13x6x 210x315x 4即C(x)B(x)A(x)(12x3x 2)( 1xx 2)依此類推：D(x)C(x) A(x)(13x6x 210x3)( 1xx 2)性質(zhì)4 若收斂，且b k，則B(x) 證 首先由條件知b k存在，按定義b0a0a1a2A(1) b1a1a2a3A(1)a0 bkakak1ak2A(1) a0a1a2ak-1 給bk對應(yīng)的等式兩端都乘以xk并分別按左右求和，得左端B(x) 右端A(1)xx 2x 3A(1)1xx 2a0x 1xx 2a1x 2 1xx 2性質(zhì)5 若bkkak，則B(x)xA

14、'(x) 。證 B(x) xA(x) a0 'xA'(x)性質(zhì)6 若b k，則B(x) 證 B(x) 性質(zhì)7 若c k，則C(x)A(x) B(x) 。證 c0a0b0c1a0b1a1b0c2a0b2a1b1a2b0cna0bna1bn-1anb0給ck對應(yīng)的等式兩端都乘以xk后左右兩邊分別求和，得C(x)a0b0(a0b1a1b0)x(a0b2a1b1a2b0)x2(a0bna1bn-1anb0)xna0 (b0b1xb2 x2)a1x(b0b1xb2 x2)a2x2 (b0b1xb2 x2)(a0a1xa2 x2) (b0b1xb2 x2)所以 C(x)A(x) B

15、(x)2.3 指數(shù)型母函數(shù)回顧：普通型母函數(shù)較好地解決了各種組合的計數(shù)問題。分析：組合數(shù)數(shù)列的母函數(shù)在解決計數(shù)問題和證明組合恒等式時之所以成為一個有力工具，究其原因，是因為它具有有限封閉形式。啟發(fā)：對排列問題也采用母函數(shù)方式。尤其是n個不盡相異元素中取r個的排列問題。困難：對于排列數(shù)數(shù)列 P(n，r) ，若采用普通型母函數(shù)，則使用起來十分不便。這是因為它不能表為初等函數(shù)形式的緣故。改進：n集的r無重排列數(shù)和r無重組合數(shù)之間有如下關(guān)系：C(n，r) 從而有(1x)n總結(jié)：在(1x)n的展開式中，項的系數(shù)恰好是排列數(shù)。由此受到啟發(fā)，排列數(shù)數(shù)列的母函數(shù)應(yīng)該采用形如的冪級數(shù)為好。由于這種類型的冪級數(shù)很

16、象指數(shù)函數(shù)的展開式，故取名為指數(shù)型母函數(shù)。（一） 數(shù)列的指母函數(shù)（1）定義【定義2.3.1】 對于數(shù)列 a 0，a 1，a 2，把形式冪級數(shù)a 0a1a2an稱為數(shù)列 a k 的指數(shù)型母函數(shù)，簡稱為指母函數(shù)，而數(shù)列 a k 則稱為指母函數(shù)的生成序列。（2）例1 1 ，Ge(x)。2 ，Ge(x)(1x)n（3）說明1可以為有限個或無限個；2數(shù)列與母函數(shù)一一對應(yīng)，即給定數(shù)列便得知它的母函數(shù)；反之，求得母函數(shù)則數(shù)列也隨之而定；例如，無限數(shù)列0,1,1,1,的指母函數(shù)是 3這里將母函數(shù)只看作一個形式函數(shù)，目的是利用其有關(guān)運算性質(zhì)完成計數(shù)問題，故不考慮“收斂問題”，即認為它始終是收斂的。4對同一數(shù)列數(shù)

17、列，一般G(x)Ge(x)。例如1 的普母函數(shù)為G(x)，而其指母函數(shù)則為Ge(x)。例外：當(dāng)0時（k2），G(x)Ge(x)5對同一函數(shù)，令f(x)Ge(x)或 f(x)G(x)則一般。例外。例如視G(x)為普母函數(shù)，則視Ge(x)為指母函數(shù)，則（二） 排列問題定理2.3.1 設(shè)重集,且n1n2nmn，則S的r可重排列的指母函數(shù)為Ge(x) (2.3.1)其中，r可重排列數(shù)為之系數(shù)，r0,1,2, ,n 。例2.3.1 盒中有3個紅球，2個黃球，3個籃球，從中取4個球，排成一列，問共有多少種不同排列方案？解 m3，n 1 3，n 2 2，n 3 3，r4，由定理知Ge(x)（）（）（）13x

18、1326所以，從中取4個球的排列方案有70種。枚舉各種排列方案。令Ge(r,y,b)則有Ge(r,y,b)1( )詳細枚舉：取1個球的3種排列方案為紅、黃、藍各分別取1個。取2個球的9種排列方案為：紅紅、黃黃、藍藍、紅黃、黃紅、紅藍、藍紅、黃藍、藍黃。說明：（1）利用普母函數(shù)能枚舉到每一種組合情況，但指母函數(shù)做不到，只能對排列進行分類枚舉。（2）一個問題的普目函數(shù)和指目函數(shù)可以互相轉(zhuǎn)換。在中，令每一項的系數(shù)為1，即得該問題的普母函數(shù)。（3）已知問題的普母函數(shù)，可以利用其生成該問題的指母函數(shù)。（三） 特例推論1 若，則r無重排列的指母函數(shù)為 (2.3.2)排列數(shù)為之系數(shù)。推論2 若，則r無限可重

19、排列的指母函數(shù)為 (2.3.3)排列數(shù)為nr。特例若每個元素ei至少出現(xiàn)一次（即rn），則，從中取r 個的排列數(shù)為 。推論3 ，元素ei至少取ki個(ki0)，則有 (2.3.4)推論4 ，令rn，即得全排列數(shù)（四） 應(yīng)用例2.3.2 五個數(shù)字1，1，2，2，3能組成多少個四位數(shù)？解 用表示組成r位數(shù)的個數(shù)，的指母函數(shù)為138183030由a430知能組成30個四位數(shù)。同時還知道能組成3個一位數(shù)，8個兩位數(shù)，18個三位數(shù)等。例2.3.3 求1，3，5，7，9五個數(shù)字組成的n位數(shù)的個數(shù)（每個數(shù)字可重復(fù)出現(xiàn)），要求其中3，7出現(xiàn)的次數(shù)為偶數(shù)，1，5，9出現(xiàn)的次數(shù)不加限制。解 設(shè)滿足條件的n位數(shù)的個

20、數(shù)為，則數(shù)列對應(yīng)的指母函數(shù)為 例2.3.4 把上例的條件改為要求1、3、7出現(xiàn)的次數(shù)一樣多，5和9出現(xiàn)的次數(shù)不加限制。求這樣的n位數(shù)的個數(shù)。解 設(shè)滿足條件的數(shù)有個，與2.1節(jié)類似的組合問題一樣，本問題的指母函數(shù)為Ge(x) 即：1， 2， 4， 14， 64， 272， 1114一般情形，當(dāng)n時從排列組合理解：例2.3.5 在例2.1.5中，若把所取出的r 只鞋再排成一列，問共有多少種結(jié)果？解 此問題即是從集合的n類共2n個元素中不重復(fù)地取出r個元素排成一列，且同一類元素，不能同時出現(xiàn)（1in）。因此，其r無重排列的指母函數(shù)應(yīng)為即不同的排列共有。與例2.1.5類似，本問題的排列數(shù)也可以從排列的

21、角度理解為：先從n雙鞋子中不重復(fù)地選出r雙排成一列，共有種排列情況，再從所選的每雙鞋中抽取一只，有種取法。由乘法原理，即得所求結(jié)果。分配問題：將r個不同的球放入n個不同的盒子，每個盒子最多放一個球，而且每個盒子中有兩個相異的格子，故還需要進行二次分配。如果某個盒子中放進一個球，那么，二次分配時有兩種可選的方案。一般提法：集合S中有m類元素，第i類元素有個，且同一類元素也互不相同，今從S中取出r個元素排成一列，問共有多少種排列結(jié)果？其中要求第i類元素最少，最多個，則此排列問題的指母函數(shù)為將其整理為指母函數(shù)的標(biāo)準(zhǔn)形式即得問題的答案（r0，1，n）。2.4 正整數(shù)的分拆在一些組合計數(shù)問題里，常會遇到

22、將一個正整數(shù)分拆成若干個正整數(shù)之和。它和分配問題以及一次方程整數(shù)解的個數(shù)有密切關(guān)系。（一） 概念定義2.4.1 將一個正整數(shù)n分解成k個正整數(shù)之和 （2.4.1）稱該分解是n的一個k分拆，并稱為分量（或分項）。（二） 分類l 有序分拆 考慮間的順序。例 521111211l 無序分拆 不考慮順序。這時可把各分項按大小重新排列。例 52111323112.4.1 有序分拆求n的k有序分拆的個數(shù)，相當(dāng)于求一次不定方程（2.4.1）全體正整數(shù)解的組數(shù)，可對每個分量加以條件限制，例如1（1,2, ,k），于是可得如下結(jié)果。定理2.4.1 對于n的k有序分拆 （2.4.2）其k有序分拆數(shù)列的母函數(shù)是組合

23、意義（分配問題）：把n個相同的球放入k個不同的盒子里，第個盒的容量為（1,2, ,k），且使每盒非空。推論 若對n的k有序分拆的各分量沒有限制，則其k有序分拆數(shù)列的母函數(shù)是，且C(n-1，k-1)。2.4.2 無序分拆（一） 問題在n的分拆中，不考慮各分量的順序，把分拆后的各項數(shù)值從大到小加以排列，即有 （2.4.3）滿足以上條件的每一組正整數(shù)解就代表了一個n的k無序分拆，簡稱分拆，其分拆數(shù)記作，稱為最大分項。問題轉(zhuǎn)換：將n分拆為k項（每一項的大小不受限制）的分拆數(shù)等于將n分拆為最大分項為k（分項個數(shù)不限）的分拆數(shù)。設(shè)滿足后一種條件的k分拆數(shù)也為。（二） 最大分項k的分拆把n分拆為最大分項等于

24、k，其分拆數(shù)相當(dāng)于求不定方程 （2.4.4）的整數(shù)解的組數(shù)。即整數(shù)n由1，2，k允許重復(fù)且k至少出現(xiàn)一次的所有（由條件式（2.4.4）限制的）組合數(shù)，其母函數(shù)為 （2.4.5）其中展開式中的系數(shù)即為n的最大分項等于k的分拆個數(shù)。（三） 最大分項k的分拆若最大分項小于或等于k，其分拆數(shù)相當(dāng)于解不定方程 （2.4.6）其分拆數(shù)列母函數(shù)為 （2.4.7）其中展開式中的系數(shù)即為n的最大分項不超過k的分拆個數(shù)。2.4.3 Ferrers圖（一） 定義一個從上而下的k層格子，設(shè)為第層的格子數(shù)，當(dāng)（1，2，n-1），即上層的格子數(shù)不少于下層的格子數(shù)時，稱之為Ferrers圖（見圖2.4.1）。50/50 (

25、a) (b)圖 2.4.1 共軛Ferrers圖（二） 性質(zhì)（1）每一層至少有一個格子；（2）Ferrers圖與式（2.4.3）說明的無序分拆是一一對應(yīng)的，其中的對應(yīng)關(guān)系是：第1層的格子數(shù)對應(yīng)分項，第2層的格子數(shù)對應(yīng)分項，依此類推。圖 2.4.1（a）就代表20的一種分拆2075521.(3)將圖形“轉(zhuǎn)置”，即把行與列對調(diào)所得的圖仍然是Ferrers圖，稱為原Ferrers圖的共軛圖（圖2.4.1中的(b)是(a)的共軛圖），或者說這兩個圖是一對共軛的Ferrers圖。若某個Ferrers圖與其共軛圖形狀相同，則稱其是自共軛的。反過來，共軛圖對應(yīng)的分拆相應(yīng)地叫做共軛分拆，如圖 2.4.1(b)

26、對應(yīng)分拆205433311，是圖(a)對應(yīng)的分拆2075521的共軛分拆。（三） 應(yīng)用定理2.4.2（1）n的所有k分拆的個數(shù)等于把n分拆成最大分項等于k的所有分拆數(shù)；（2）把n分拆成最多不超過k個數(shù)之和的分拆數(shù)等于把n分拆成最大分項不超過k的所有分拆數(shù)。顯然，從共軛圖對的一一對應(yīng)關(guān)系即可得到兩種分拆要求的一一對應(yīng)關(guān)系，從而知定理的結(jié)論成立。例如，由圖 2.4.1知，20的5分拆對應(yīng)的Ferrers圖必為5行的Ferrers圖，而其共軛圖的最長的行必為5列，即20的最大分項等于5的一種分拆。到此，關(guān)于正整數(shù)的無序分拆數(shù)的計數(shù)問題，已經(jīng)得到解決。推論 正整數(shù)n分拆成互不相同的若干個奇數(shù)的和的分拆

27、數(shù)，與n分拆成有自共軛的Ferrers圖的分拆數(shù)相等。證 設(shè)n(21)(21)(21)， > >>構(gòu)造一個Ferrers圖，其第一行、第一列都是1，對應(yīng)于21，第二行、第二列都是1，對應(yīng)于21，依此類推。由此所得的Ferrers圖是自共軛的。反過來也一樣。例如17953對應(yīng)的Ferrers圖如圖2.4.2所示。圖 2.4.2 n分拆為不同的奇數(shù)及其對應(yīng)的自共軛的Ferrers圖2.4.4 分拆數(shù)的估計對于n的k無序分拆，當(dāng)k任意時（k1,2,n），n的所有分拆的個數(shù)稱作n的分拆數(shù)，記作p(n)，即定理2.4.3 正整數(shù)n的全部分拆總數(shù)數(shù)列的母函數(shù)是 （2.4.8）當(dāng)n較大時，

28、計算p(n)是非常困難的，例如p(1)1， p(5)7， p(10)42， p(15)176，p(20)627， p(25)1958， p(200)39729990293884萬億下面給出p(n)的漸進公式和估值不等式。定理2.4.4 關(guān)于的計算，有（1）（2）（3）， n2 .還有一種利用二元遞歸函數(shù)來計算p(n)的算法，描述如下。定理2.4.5 設(shè)函數(shù)表示正整數(shù)n的最大分項n1m的所有分拆數(shù)，則有 （2.4.9）定理2.4.5實質(zhì)上是函數(shù)Q(n,m)的遞歸定義，其原因如下：(1) 顯然有Q(1,n) Q(m,1)1；(2) 因為最大分量n1實際上不能大于n，故m >n時，Q(n,m)

29、 Q(n,n)；(3) 由于在n的所有分拆中，其1分拆只有一個，即n n1，而其它的分拆都是n1n-1；(4) 因為對于正整數(shù)n，最大分項為m的分拆數(shù)由以下兩部分組成：一個是以m作為第一分項，其余分項之和等于nm，且最大分項n2不超過m的分拆數(shù)Q(n-m,m)；另一個是最大分項n1m-1的分拆數(shù)(n，m-1)。根據(jù)以上定義，可看出。因此計算的問題便歸結(jié)為計算遞歸函數(shù)。2.4.5 應(yīng)用例2.4.1 （各分項不同，即不重復(fù)）設(shè)有1克、2克、3克、4克的砝碼各一枚，若要求各砝碼只能放在天平的一邊。問能稱出那幾種重量？有哪幾種可能方案？（解）這是典型的正整數(shù)分拆問題。比如說可以稱6克重的物品，使用的砝

30、碼可以是1克、2克、3克的三個砝碼放在一起，也可以是2克和4克的兩個砝碼放在一起來稱。即當(dāng)最大分項不超過4時，6的無序不重復(fù)分拆只有兩種632142首先，將整數(shù)n分拆為最大分項不超過4，且各分項最多只能出現(xiàn)一次的分拆數(shù)數(shù)列的母函數(shù)為（即在式（2.4.6）中令01而得到的式（2.4.7）的特殊情形） 從右端的母函數(shù)知可稱出從1克到10克共10種重量，冪的系數(shù)即為稱出n克重量的方案數(shù)。若要枚舉出具體的稱重方案，則分拆數(shù)的母函數(shù)應(yīng)為 （2.4.10）1xy2(xy2z3)(xz3w4)y2z3w4xy2z3w4從式中可以看出， 若（0或）中各因子的指數(shù)之和為n，則該單項式就對應(yīng)一種稱n克重量的方案。

31、如z3w4就是稱7克重量的方案之一，而且用的是3克和4克的砝碼。稱7克重量的另一方案則是xy2w4對應(yīng)的用1克、2克和4克的砝碼。說明：（1） 取12324，重量相同，元素個數(shù)不同，對應(yīng)所取元素個數(shù)不同的組合方案。（2） 若取兩個元素，如235，347，元素個數(shù)相同，但重量不同，是不同的整數(shù)的分拆方案。（3） 組合關(guān)心的是元素的個數(shù)，本題關(guān)心的是元素的加權(quán)和（每個元素賦予一定的權(quán)值）。對于組合而言，其母函數(shù)應(yīng)為 1（xyzw）（xyxzxwyzywzw） （xyzxywxzwyzw）xyzw例2.4.2 （各分項無限重復(fù)）求用1分、2分、3分的郵票貼出不同面值的方案數(shù)。解 這是可重復(fù)的無序分拆

32、，相應(yīng)的母函數(shù)為G(x)(1xx2)(1x2x4)(1x3x6)以為例，其系數(shù)等于4，說明貼出4分面值的方案有4種，即41111， 4211， 422， 431這里是按照郵票總面值的不同來區(qū)別并統(tǒng)計方案數(shù)的。若將郵票貼成一行，不同面值的郵票互換位置后算作另一種方案，則問題將成為有序分拆。例2.4.3 （有序分拆）在例2.4.2中，按照有序分拆，貼成總面值等于4分的方案數(shù)是多少？解 這時，在無序分拆中的分拆方案4211、431將分別對應(yīng)3個和2個有序分拆方案4211121112， 43113所以，總的方案數(shù)應(yīng)為7。這里也可以利用定理2.4.1的推論來計算方案數(shù)：4的1有序分拆數(shù)為 C(4-1，1

33、-1)1，即44分拆為自身；4的2有序分拆數(shù)為 C(4-1，2-1)3，即4311322；4的3有序分拆數(shù)為 C(4-1，3-1)3，即4211121112；4的4有序分拆數(shù)為C(4-1，4-1)1，即41111。各項求和，即得4的全部有序分拆數(shù)為8，但本題中無4分面值的郵票，故不算，恰為7種方案。例2.4.4 （各分項有限不重復(fù)）若有1克的砝碼3枚，2克的4枚，4克的2枚，問能稱出多少種重量？各有幾種方案？解 這是無序分拆中處于不重復(fù)分拆（見例2.4.1）和無限重復(fù)分拆（見例2.4.2）之間的有限重復(fù)分拆問題，作為式（2.4.7）的特例，其母函數(shù)為G(x)1x2x22x33 x43x54x6

34、4x75x85x95x105 x114 x124 x133 x143 x152 x162 x17x18x19共能稱出19種重量，各種重量的方案數(shù)即為各的的系數(shù)。例如，稱8克重量，即8的分項為1、2、4的無序分拆有8 444224211222222211若將1克的砝碼改為4枚，顯然，稱8克重量的方案還有8 41111221111相應(yīng)的母函數(shù)以及稱其它重量的方案情況。例2.4.5 (擴展)：在例2.4.4中，若砝碼可以放在天平的兩邊，但兩邊不能同時有同樣重量的砝碼，請給出問題的母函數(shù)。問要秤出2克重的物體，有多少種不同的秤法？并給出每一種秤法。解 此時，物體一邊的砝碼實際起了抵消天平另一邊砝碼重量

35、的作用。故稱重量問題的母函數(shù)為G(x) 2233434 3434343433 2213171316可以看出，秤2克重物體的不同秤法有13種。枚舉每一種方案（可用3個符號 x、y、z分別代表不同的砝碼，構(gòu)造該問題的母函數(shù)如下）：G(x) （）（ ） （ ） （1 ）（） （ ） （ ） （）（）（ ）（）（）（）（）（）（ ）（1）（）（）（）（）（）（）（）（）（）·（1 ）（ ）例如，稱2克的重量，有13種方法，具體稱法為（負數(shù)表示砝碼放在左邊，正數(shù)表示砝碼放在右邊）112 (-1)(-1)22 (-1)(-1)4 (-2)411(-2) (-2) 4222(-4)1122(-4)

36、 (-1)(-1)(-2)(-2)44 (-1)(-1) 2222(-4) (-2)(-2)(-2)44 11 (-2)(-2)(-2) (-2) 441122 22(-4)(-4)象下邊這些稱法，用上邊的母函數(shù)是反映不出來的（即天平兩邊放有同一重量的砝碼，使得相同砝碼抵消）2(-1)12(-1)(-2)122(-1)(2)14(4)114(4)24(1)(1)(4)224(2)(4)224(1)(1)(2)(4)2224(1)(1)(2)(2)(2)244例2.4.6 投擲3個骰子，點數(shù)之和為n（3n18），其方案有多少種？骰子的情況如下：（1）3個骰子相異；（2）3個骰子相同。解 （1）3

37、個骰子不同（比如3個骰子的顏色分別為紅色、蘭色和黃色），則問題等價于n的每個分量值都有限制的特殊有序3-分拆。即由定理2.4.1知，相應(yīng)的母函數(shù)為361015212527272521151063骰子的點數(shù)之和等于n的投擲方案個數(shù)就是的系數(shù)。例如點數(shù)之和等于15的方案有10種，即663636366654645564546465456555其中假設(shè)和式中的第一個加數(shù)為紅色骰子的點數(shù)，后兩個加數(shù)分別為蘭色和黃色骰子的點數(shù)，而這也恰好反映了15的每個分項值不超過6的全部有序3分拆。（2）3個骰子相同，則問題等價于n的特殊無序3-分拆。其特殊性體現(xiàn)在對每個分量的值都限制在16之間，即利用Ferrers圖

38、，此問題又可轉(zhuǎn)化為求n的最大分項等于3，且項數(shù)不超過6的分拆數(shù)，即求方程的非負整數(shù)解的個數(shù)。相應(yīng)的母函數(shù)為2345666 65432其中點數(shù)之和等于n的方案數(shù)就是的系數(shù)（3n18）。例如點數(shù)之和等于10的方案有6種，即10631622541532442433這也是10的每個分項值不超過6的無序3分拆數(shù)。習(xí) 題 二1、 基本題：13，69，13152、 加強題：5，10113、 提高題：4，12，16，154、 關(guān)聯(lián)題： 141. 求下列數(shù)列的母函數(shù)（n0,1,2，）：（1）； （2） n5 （3） n(n1) ； （4） n(n2) （解）（1）（2）（3）（4）2. 證明序列C(n，n)，C

39、(n1，n)，C(n2，n)，的母函數(shù)為（證）已知集合的r-組合的母函數(shù)為所以序列，的母函數(shù)為3. 設(shè)S，求序列的母函數(shù)，其中an是S的滿足下列條件的n組合數(shù)：（1） S的每個元素都出現(xiàn)奇數(shù)次；（2） S的每個元素出現(xiàn)3的倍數(shù)次；（3） e1不出現(xiàn)，e2至多出現(xiàn)一次；（4） e1只出現(xiàn)1、3或11次，e2只出現(xiàn)2、4或5次；（5） S的每個元素至少出現(xiàn)10次。（解）（1）；（2）；（3）；（4）；（5）。4. 投擲兩個骰子，點數(shù)之和為r(2r12)，其組合數(shù)是多少？（解）相應(yīng)的母函數(shù)為其中點數(shù)之和為n的方案數(shù)就是的系數(shù)。5. 居民小區(qū)組織義務(wù)活動，號召每家出一到兩個人參加。設(shè)該小區(qū)共有n個家庭，現(xiàn)從中選出r人，問：（1）設(shè)每個家庭都是3口之家，有多少種不同的選法？當(dāng)n=50時，選法有多少種？（2）設(shè)n個家庭中兩家有4口人，其余家庭都是3口人，有多少種選法？6. 把n個相同的小球放入編號為的m個盒子中，使得每個盒子內(nèi)的球數(shù)不小于它的編號數(shù)。已知，求不同的放球方法數(shù)。7. 紅、黃、藍三色的球各8個，從中取出9個，要求每種顏色的球至少一個，問有多少種不同的取法？（解）設(shè)從中取r個的不同取法有種，那么，數(shù)列的母函數(shù)為因此所求方案數(shù)為28另法：原問題等價于從集合S中取出9個元素，且每個元素至少取一個?，F(xiàn)在先把元素a、b、c各取一個，