《組合數(shù)學(xué)》教案2章(母函數(shù))分享

文檔供參考，可復(fù)制、編制，期待您的好評(píng)與關(guān)注！ 第二章 母函數(shù)及其應(yīng)用1. 普母函數(shù)及其在組合問(wèn)題中的應(yīng)用2. 指母函數(shù)及其在排列問(wèn)題中的應(yīng)用3. 正整數(shù)的分拆及其組合意義和應(yīng)用問(wèn)題：對(duì)于不盡相異元素的部分排列和組合，用第一章的方法比較麻煩（參見(jiàn)表2.0.1）。新方法：母函數(shù)方法。表2.0.1條件組合方案數(shù)排列方案數(shù)對(duì)應(yīng)的集合相異元素，不重復(fù)相異元素，可重復(fù)S不盡相異元素（有限重復(fù)）特例rn1S，,n1n2nmn，nk1,（k1,2, m）r1mm所有r至少有一個(gè)滿(mǎn)足基本思想：把離散的數(shù)列同多項(xiàng)式或冪級(jí)數(shù)一一對(duì)應(yīng)起來(lái)，從而把離散數(shù)列間的結(jié)合關(guān)系轉(zhuǎn)化為多項(xiàng)式或冪級(jí)數(shù)之間的運(yùn)算。2.1 母函數(shù)（一） 母函數(shù)（1）定義【定義2.1.1】對(duì)于數(shù)列，稱(chēng)無(wú)窮級(jí)數(shù)為該數(shù)列的（普通型）母函數(shù)，簡(jiǎn)稱(chēng)普母函數(shù)或母函數(shù)。（2）例【例2.1.1】有限數(shù)列（r0, 1, 2, , n）的普母函數(shù)是：【例2.1.2】無(wú)限數(shù)列1, 1. , 1, 的普母函數(shù)是（3）說(shuō)明 可以為有限個(gè)或無(wú)限個(gè)。 數(shù)列與母函數(shù)一一對(duì)應(yīng)。0, 1, 1, , 1, 將母函數(shù)視為形式函數(shù)，目的是利用其有關(guān)運(yùn)算性質(zhì)完成計(jì)數(shù)問(wèn)題，故不考慮“收斂問(wèn)題”，而且始終認(rèn)為它是可“逐項(xiàng)微分”和“逐項(xiàng)積分”的。（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 ak （二） 組合問(wèn)題（1）組合的母函數(shù)【定理2.1.1】組合的母函數(shù)：設(shè),且n1n2nmn，則S的r可重組合的母函數(shù)為其中，r可重組合數(shù)為之系數(shù)，r0, 1, 2, , n。理論依據(jù)：多項(xiàng)式的任何一項(xiàng)與組合結(jié)果一一對(duì)應(yīng)。優(yōu)點(diǎn)：l 將無(wú)重組合與重復(fù)組合統(tǒng)一起來(lái)處理；l 使處理可重組合的枚舉問(wèn)題變得非常簡(jiǎn)單。（2）特例【推論1】，則r無(wú)重組合的母函數(shù)為G(x) (1x)n組合數(shù)為之系數(shù)?！就普?】，則r無(wú)限可重組合的母函數(shù)為G(x) 組合數(shù)為之系數(shù)。【推論3】，每個(gè)元素至少選一個(gè)：母函數(shù) G(x)組合數(shù) 【推論4】，每個(gè)元素選非負(fù)偶數(shù)個(gè)：母函數(shù) G(x)組合數(shù) ?！就普?】，每個(gè)元素選奇數(shù)個(gè)：母函數(shù) G(x)組合數(shù) 【推論6】S，且n1n2nmn，元素至少出現(xiàn)次：為母函數(shù) G(x)組合數(shù) rk, k1, , n，kk1k2km。（3）一般情形：設(shè)S20.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個(gè)紅球，1個(gè)黑球，1個(gè)白球，問(wèn)（1） 共有多少種不同的選取方法，試加以枚舉？（2） 若每次從中任取3個(gè)，有多少種不同的取法？（解）（1）元素符號(hào)化（x，y，z紅、黑、白球），元素的個(gè)數(shù)以符號(hào)的指數(shù)區(qū)分。母函數(shù)G(x, y, z) (1xx2) (1y) (1z)1(xyz)(x2xyxzyz)(x2yx2zxyz)( x2yz)5種情況： 數(shù)字1表示一個(gè)球也不取的情況，共有1種方案； 取1個(gè)球的方案有3種，即紅、黑、白三種球只取1個(gè)； 取2個(gè)球的方案有4種，即2紅、1紅1黑、1紅1白、1黑1白； 取3個(gè)球的方案有3種，即2紅1黑、2紅1白、三色球各一； 取4個(gè)球的方案有1種，即全取。令xyz1，得方案總數(shù)G(1,1,1) 1343112（2）只考慮每次取3個(gè)的方案數(shù)，不需枚舉令yx，zxG(x)(1xx2) (1x) (1x)13x4 x23 x3x4由x3的系數(shù)即得所求方案數(shù)為3?！纠?.1.4】有18張戲票分給甲、乙、丙、丁4個(gè)班（不考慮座位號(hào)），其中甲、乙兩班最少1張，甲班最多5張，乙班最多6張，丙班最少2張，最多7張，丁班最少4張，最多10張，問(wèn)有多少種不同的分配方案？（解）（1）分析：實(shí)質(zhì)為甲、乙、丙、丁四類(lèi)共28個(gè)元素中可重復(fù)地取18個(gè)元素的組合問(wèn)題。，m4，nn1n2n3n45671028，k 11248，r18。（2）求解：母函數(shù)G(x)x8140 x18x28（3）特殊情況處理：戲票數(shù)r4，0（i1, 2, 3, 4）G1(x)G2(x) 系數(shù)相同，用G2(x)計(jì)算要比用G1(x)方便得多（因?yàn)閷U(kuò)展為不影響的系數(shù)）同理，r6，可用G3(x) 代替G1(x)求的系數(shù)?！纠?.1.5】從n雙互相不同的鞋中取出r只（），要求其中沒(méi)有任何兩只是成對(duì)的，問(wèn)共有多少種不同的取法？（解）解法一：母函數(shù)法。視為，但同類(lèi)中的兩個(gè)不一樣，即故其r重組合的母函數(shù)為G(x)(12x)n不同的取法共有種。本質(zhì)：每類(lèi)元素最多只能出現(xiàn)一次，但同類(lèi)元素互換后方案不同。故G(x) 中不能有項(xiàng)，再由同雙的兩只鞋子有區(qū)別知，x的系數(shù)應(yīng)為2。解法二：排列組合。先從n雙鞋中選取r雙，共有種選法，再?gòu)拇藃雙中每雙抽取一只，有種取法。解法三：排列組合。先取出k只左腳的鞋，再在其余雙鞋中取出只右腳的鞋：得組合恒等式一般提法：S從中取出r個(gè)，第類(lèi)元素最少個(gè)，最多個(gè)，母函數(shù)：G(x) 舉例， 把5本相同的書(shū)分給甲、乙、丙3個(gè)班，再發(fā)到個(gè)人手上，每人最多發(fā)一本?？紤]將分給某班的某本書(shū)發(fā)給該班的同學(xué)A與將其發(fā)給同學(xué)B被認(rèn)為是不同的分法，而且甲、乙兩班最少1本，甲班最多5本，乙班最多6本，丙班最少2本，最多9本，問(wèn)有多少種不同的分配方案？S，n56920，k1124，r5。母函數(shù)G(x)10807380共有7380種分配方案。說(shuō)明：與問(wèn)題“從20個(gè)相異元素中不重復(fù)地抽取5個(gè)元素” 不等價(jià)（答案為15,504）?！纠?.1.6】甲、乙、丙3人把n（n3）本相同的書(shū)搬到辦公室，要求甲和乙搬的本數(shù)一樣多，問(wèn)共有多少種分配的方法？（解）（1）分析：組合問(wèn)題：從集合中可重復(fù)地選取n個(gè)元素，要求與的個(gè)數(shù)一樣多，求不同的選取方案數(shù)。特點(diǎn)：限制盒子之間的關(guān)系。（2）特例：n1，1種分法，甲和乙都分0本（丙1本）。n2，2種分法：甲和乙分0本（丙2本）或甲和乙1本（丙0本）。當(dāng)n3時(shí)，分法2種。當(dāng)n4或5，3種分法：甲和乙都分0本、1本或2本。（3）一般情形：視為2個(gè)大盒子A、B，且A又分為2個(gè)小盒子。分兩步分配：第一步：A盒子分偶數(shù)本，B盒子分任意本；第二步：將分給A盒的書(shū)再給甲、乙各分一半。A（2k本）B（n2k本）甲（k本）乙（k本）丙（n2k本）不同的分配方法共有種。上整數(shù)函數(shù)。即不小于x的最小整數(shù)。（待定系數(shù)法：分解有理多項(xiàng)式：，比較同次冪系數(shù)得方程組，解之得AB1/4，C1/2）【例2.1.7】證明組合等式（1）（2）（3）， nm（證）（1）二項(xiàng)式 兩端求導(dǎo) （*）令x1即可。（2）（*）式兩端同乘以x后求導(dǎo)令x1。（3） 兩邊展開(kāi) 比較兩邊的常數(shù)項(xiàng)。2.2 母函數(shù)的性質(zhì)母函數(shù)與生成數(shù)列一一對(duì)應(yīng)若兩個(gè)母函數(shù)之間存在某種關(guān)系，則對(duì)應(yīng)的生成數(shù)列之間也必然存在相應(yīng)的關(guān)系。反之亦然。設(shè)：數(shù)列a k、b k、c k的母函數(shù)分別為A(x)、B(x)、C(x)，且都可逐項(xiàng)微分和積分?！拘再|(zhì)1】若（即），則B(x)。（證）B(x) 分析：向右移r個(gè)位置且前面補(bǔ)0 【性質(zhì)2】若，則B(x) （證）B(x)b0b1 xb2 x 2arar1 x ar2x 2( ar x rar1 x r1 ar2x r2)分析：向左移r個(gè)位置且前面舍掉 【性質(zhì)3】若，則B(x)。（證）等式兩端乘以對(duì)k求和：k0: k1: k2: kn: )即 B(x)例，已知A(x)1xx 2x n，（1）令k1B(x)12x3x 2或 B(x)同理，令ck12(k1)，可得C(x)13x6x 210x315x 4C(x)B(x)A(x)(12x3x 2)( 1xx 2)類(lèi)推：D(x)C(x) A(x)(13x6x 210x3)( 1xx 2)【性質(zhì)4】若收斂，且b k，則B(x) （證）首先由條件知b k存在，按定義b0a0a1a2A(1) b1a1a2a3A(1)a0bkakak1ak2A(1)a0a1a2ak-1給bk對(duì)應(yīng)的等式兩端都乘以xk并分別按左右求和，得左端B(x) 右端A(1)xx 2x 3A(1)1xx 2a0x1xx 2a1x 2 1xx 2【性質(zhì)5】若bkkak，則B(x)xA'(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對(duì)應(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)A(x) B(x)2.3 指數(shù)型母函數(shù)回顧：普通型母函數(shù)較好地解決了各種組合的計(jì)數(shù)問(wèn)題。分析：組合數(shù)數(shù)列的母函數(shù)在解決計(jì)數(shù)問(wèn)題和證明組合恒等式時(shí)之有用的原因：具有有限封閉形式。啟發(fā)：對(duì)排列問(wèn)題也采用母函數(shù)方式。尤其是n個(gè)不盡相異元素中取r個(gè)的排列問(wèn)題。困難：對(duì)于排列數(shù)數(shù)列 P(n，r) ，采用普通型母函數(shù)十分不便。原因：它不能表為初等函數(shù)形式。改進(jìn)：n集的r無(wú)重排列數(shù)和r無(wú)重組合數(shù)之間的關(guān)系：C(n，r) (1x)n總結(jié)：在(1x)n的展開(kāi)式中，項(xiàng)的系數(shù)恰好是排列數(shù)。啟發(fā)：排列數(shù)數(shù)列的母函數(shù)為。（一） 數(shù)列的指母函數(shù)（1）定義【定義2.3.1】對(duì)于數(shù)列 a 0，a 1，a 2，把形式冪級(jí)數(shù)a 0a1a2an稱(chēng)為數(shù)列 a k 的指數(shù)型母函數(shù)，簡(jiǎn)稱(chēng)為指母函數(shù)，而數(shù)列 a k 則稱(chēng)為指母函數(shù)的生成序列。（2）例1 1 ，Ge(x) 。2 ，Ge(x)(1x)n（3）說(shuō)明1可以為有限個(gè)或無(wú)限個(gè)；2數(shù)列指母函數(shù)。例0,1,1,1,3將母函數(shù)視為形式函數(shù)，且始終是收斂的。4同一數(shù)列數(shù)列，一般G(x)Ge(x)。例 1 的普母函數(shù)為G(x)，指母函數(shù)為Ge(x)。例外：當(dāng)0時(shí)（k2），G(x)Ge(x)5對(duì)同一函數(shù)，令f(x)Ge(x)或 f(x)G(x)則一般。例外。視G(x)為普母函數(shù)，則視Ge(x)為指母函數(shù)，則（二） 排列問(wèn)題【定理2.3.1】設(shè)重集,且n1n2nmn，則S的r可重排列的指母函數(shù)為Ge(x)其中，r可重排列數(shù)為之系數(shù)，r0,1,2, ,n 。【例2.3.1】盒中有3個(gè)紅球，2個(gè)黃球，3個(gè)籃球，從中取4個(gè)球，排成一列，問(wèn)共有多少種不同排列方案？（解）m3，3，2，3，r4 13x1326取4個(gè)球的排列方案數(shù)為70。枚舉：令Ge(r,y,b)Ge(r,y,b)1( )詳細(xì)枚舉：取1個(gè)球的3種排列方案為紅、黃、藍(lán)各分別取1個(gè)。取2個(gè)球的9種排列方案為：紅紅、黃黃、藍(lán)藍(lán)、紅黃、黃紅、紅藍(lán)、藍(lán)紅、黃藍(lán)、藍(lán)黃。說(shuō)明：（1）利用普母函數(shù)能枚舉到每一種組合情況，但指母函數(shù)做不到，只能對(duì)排列進(jìn)行分類(lèi)枚舉。（2）一個(gè)問(wèn)題的普目函數(shù)和指目函數(shù)可以互相轉(zhuǎn)換。例：在令每一項(xiàng)系數(shù)為1，即得普母函數(shù)。（3）已知問(wèn)題的普母函數(shù)，可利用其生成指母函數(shù)。（三） 特例【推論1】 指母函數(shù) 排列數(shù)為之系數(shù)?！就普?】指母函數(shù) 排列數(shù)為 nr【特例】每個(gè)元素至少選一個(gè)（即rn）方案數(shù) ?！就普?】，ei至少取ki個(gè)（ki0）指母函數(shù) 【推論4】，rn，全排列數(shù)（四） 應(yīng)用 【例2.3.2】五個(gè)數(shù)字1，1，2，2，3能組成多少個(gè)四位數(shù)？（解）用表示組成r位數(shù)的個(gè)數(shù)，的指母函數(shù)為138183030能組成30個(gè)四位數(shù)?！纠?.3.3】求1，3，5，7，9五個(gè)數(shù)字組成的n位數(shù)的個(gè)數(shù)（每個(gè)數(shù)字可重復(fù)出現(xiàn)），要求其中3，7出現(xiàn)的次數(shù)為偶數(shù)，1，5，9出現(xiàn)的次數(shù)不加限制。（解）設(shè)滿(mǎn)足條件的n位數(shù)的個(gè)數(shù)為，指母函數(shù)： 【例2.3.4】把上例的條件改為要求1、3、7出現(xiàn)的次數(shù)一樣多，5和9出現(xiàn)的次數(shù)不加限制。求這樣的n位數(shù)的個(gè)數(shù)。（解）設(shè)滿(mǎn)足條件的數(shù)有個(gè)，類(lèi)似例2.1.6Ge(x) 即：1，2，4，14，64，272，1114一般情形，當(dāng)n時(shí)理解（按排列）： 【例2.3.5】在例2.1.5中，若把所取出的r 只鞋再排成一列，問(wèn)共有多少種結(jié)果？（解）即從集合的n類(lèi)共2n個(gè)元素中不重復(fù)地取出r個(gè)元素排成一列，且同一類(lèi)元素，不能同時(shí)出現(xiàn)（1in）。指母函數(shù)：不同的排列數(shù)為。與例2.1.5類(lèi)似，本問(wèn)題的排列數(shù)也可以從排列的角度理解為：先從n雙鞋子中不重復(fù)地選出r雙排成一列，共有種排列情況，再?gòu)乃x的每雙鞋中抽取一只，有種取法。由乘法原理，即得所求結(jié)果。分配問(wèn)題：將r個(gè)不同的球放入n個(gè)不同的盒子，每個(gè)盒子最多放一個(gè)球，而且每個(gè)盒子中有兩個(gè)相異的格子，故還需要進(jìn)行二次分配。如果某個(gè)盒子中放進(jìn)一個(gè)球，那么，二次分配時(shí)有兩種可選的方案。一般提法：集合S中有m類(lèi)元素，第i類(lèi)元素有個(gè)，且同一類(lèi)元素也互不相同，從S中取出r個(gè)元素排成一列，問(wèn)共有多少種排列結(jié)果？其中要求第i類(lèi)元素最少，最多個(gè)，則此排列問(wèn)題的指母函數(shù)為即得問(wèn)題的答案（r0，1，n）。2.4 正整數(shù)的分拆問(wèn)題：將一個(gè)正整數(shù)分拆成若干個(gè)正整數(shù)之和。關(guān)聯(lián)問(wèn)題：分配問(wèn)題、一次方程整數(shù)解的個(gè)數(shù)問(wèn)題。（一） 概念【定義2.4.1】稱(chēng)該分解是n的一個(gè)k分拆，并稱(chēng)為分量（或分項(xiàng)）。（二） 分類(lèi)l 有序分拆 考慮間的順序。例 521111211l 無(wú)序分拆 不考慮順序（可把分項(xiàng)按大小排序）。例 52111323112.4.1 有序分拆求n的k有序分拆的個(gè)數(shù)求一次不定方程全體正整數(shù)解的組數(shù)?？蓪?duì)每個(gè)分量加以條件限制：1（1, 2, , k）?！径ɡ?.4.1】n的k有序分拆分拆數(shù)列的母函數(shù)：組合意義（分配問(wèn)題）：把n個(gè)相同的球放入k個(gè)不同的盒子里，第個(gè)盒的容量為（1,2, ,k），且使每盒非空。【推論】若對(duì)n的k有序分拆的各分量沒(méi)有限制，則其k有序分拆數(shù)列的母函數(shù)是，且。2.4.2 無(wú)序分拆（一） 問(wèn)題簡(jiǎn)稱(chēng)分拆，分拆數(shù)記作，稱(chēng)為最大分項(xiàng)。問(wèn)題轉(zhuǎn)換：將n分拆為k項(xiàng)（每一項(xiàng)的大小不受限制）的分拆數(shù)等于將n分拆為最大分項(xiàng)為k（分項(xiàng)個(gè)數(shù)不限）的分拆數(shù)。設(shè)滿(mǎn)足后一種條件的k分拆數(shù)也為。（二） 最大分項(xiàng)k的分拆分拆數(shù)不定方程整數(shù)解的組數(shù)即整數(shù)n由1，2，k允許重復(fù)且k至少出現(xiàn)一次的所有組合數(shù)。母函數(shù)：（三） 最大分項(xiàng)k的分拆分拆數(shù)不定方程整數(shù)解的組數(shù)分拆數(shù)列的母函數(shù)：2.4.3 Ferrers圖（一） 定義一個(gè)從上而下的k層格子，設(shè)為第層的格子數(shù)，當(dāng)（1，2，n-1），即上層的格子數(shù)不少于下層的格子數(shù)時(shí)，稱(chēng)為Ferrers圖。 （a） （b）44 / 44（二） 性質(zhì)（1）每一層至少有一個(gè)格子（2）Ferrers圖與無(wú)序分拆對(duì)應(yīng)關(guān)系：第1層的格子數(shù)對(duì)應(yīng)分項(xiàng)，第2層的格子數(shù)對(duì)應(yīng)分項(xiàng)，。圖（a）2075521（3）“轉(zhuǎn)置”的圖仍為Ferrers圖，稱(chēng)為原Ferrers圖的共軛圖，或者說(shuō)這兩個(gè)圖是一對(duì)共軛的Ferrers圖。若某個(gè)Ferrers圖與其共軛圖形狀相同，則稱(chēng)其是自共軛的。共軛圖對(duì)應(yīng)的分拆叫做共軛分拆圖（b）共軛分拆205433311（三） 應(yīng)用【定理2.4.2】（1）n的所有k分拆的個(gè)數(shù)等于把n分拆成最大分項(xiàng)等于k的所有分拆數(shù)；（2）把n分拆成最多不超過(guò)k個(gè)數(shù)之和的分拆數(shù)等于把n分拆成最大分項(xiàng)不超過(guò)k的所有分拆數(shù)。（證）兩種分拆一一對(duì)應(yīng)關(guān)系。【推論】正整數(shù)n分拆成互不相同的若干個(gè)奇數(shù)的和的分拆數(shù)，與n分拆成有自共軛的Ferrers圖的分拆數(shù)相等。（證）建立一一對(duì)應(yīng)關(guān)系。設(shè)，F(xiàn)errers圖特點(diǎn)：第i行、第i列元素為個(gè)；是自共軛的。反之亦然。179532.4.4 分拆數(shù)的估計(jì)令 p(n)n的全部無(wú)序分拆數(shù)（稱(chēng)作n的分拆數(shù)）【定理2.4.3】正整數(shù)n的全部分拆總數(shù)數(shù)列的母函數(shù)是當(dāng)n較大時(shí)，計(jì)算p(n)是非常困難的。p(1)1， p(5)7， p(10)42， p(15)176， p(20)627， p(25)1958， p(200)39729990293884萬(wàn)億p(n)的漸進(jìn)公式和估值不等式：【例2.4.4】關(guān)于的計(jì)算，有（1）（2）（3），n2.利用二元遞歸函數(shù)計(jì)算p(n)的算法：【定理2.4.5】令正整數(shù)n的最大分項(xiàng)n1m的所有分拆數(shù)：實(shí)質(zhì)上是函數(shù)Q(n,m)的一種遞歸定義。(1) 顯然有Q(1,n) Q(m,1)1；(2) 因?yàn)樽畲蠓至縩1實(shí)際上不能大于n，故m >n時(shí)，Q(n,m) Q(n,n)；(3) 由于在n的所有分拆中，其1分拆只有一個(gè)，即nn1，而其它的分拆都是n1n-1；(4) N的最大分項(xiàng)為m的分拆數(shù)分為兩部分：以m作為第一分項(xiàng)，其余分項(xiàng)之和等于nm，且最大分項(xiàng)n2不超過(guò)m的分拆數(shù)Q(n-m,m)；最大分項(xiàng)n1m-1的分拆數(shù)Q (n，m-1)。2.4.5 應(yīng)用【例2.4.1】（各分項(xiàng)不同，即不重復(fù)）設(shè)有1克、2克、3克、4克的砝碼各一枚，若要求各砝碼只能放在天平的一邊。問(wèn)能稱(chēng)出那幾種重量？有哪幾種可能方案？（解）典型的正整數(shù)分拆問(wèn)題。例：6克物品32142分拆條件：最大分項(xiàng)不超過(guò)4時(shí)，6的無(wú)序不重復(fù)分拆有兩種一般條件：將整數(shù)n分拆為最大分項(xiàng)不超過(guò)4，且各分項(xiàng)最多只能出現(xiàn)一次的分拆。母函數(shù)： 結(jié)論：可稱(chēng)出從1克到10克共10種重量，冪的系數(shù)即為稱(chēng)出n克重量的方案數(shù)。枚舉：分拆數(shù)的母函數(shù)：1xy2(xy2z3)(xz3w4)y2z3w4xy2z3w4規(guī)律：若（0或）中各因子的指數(shù)之和為n，則單項(xiàng)式對(duì)應(yīng)一種稱(chēng)n克重量的方案。例：對(duì)應(yīng)稱(chēng)7克重量的方案之一，而且用的是3克和4克的砝碼。另一方案為xy2w4對(duì)應(yīng)的用1克、2克和4克的砝碼。說(shuō)明：a) 取12324，重量相同，元素個(gè)數(shù)不同，對(duì)應(yīng)所取元素個(gè)數(shù)不同的組合方案。b) 若取兩個(gè)元素，如235，347，元素個(gè)數(shù)相同，但重量不同，是不同的整數(shù)的分拆方案。c) 組合關(guān)心的是元素的個(gè)數(shù)，分拆關(guān)心的是元素的加權(quán)和（每個(gè)元素賦予一定的權(quán)值）。對(duì)于組合而言，其母函數(shù)應(yīng)為 1(xyzw)(xyxzxwyzywzw)(xyzxywxzwyzw)xyzw【例2.4.2】（各分項(xiàng)無(wú)限重復(fù)）求用1分、2分、3分的郵票貼出不同面值的方案數(shù)。（解）分項(xiàng)可（無(wú)限）重復(fù)的無(wú)序分拆。母函數(shù)：G(x)(1xx2)(1x2x4)(1x3x6)例：系數(shù)為4，貼出4分面值的方案有4種，即41111， 4211， 422， 431說(shuō)明：本題是按照郵票總面值的不同來(lái)區(qū)別并統(tǒng)計(jì)方案數(shù)的。若將郵票貼成一行，不同面值的郵票互換位置后算作另一種方案，則問(wèn)題將成為有序分拆。【例2.4.3】（有序分拆）在例2.4.2中，按照有序分拆，貼成總面值等于4分的方案數(shù)是多少？（解）例：無(wú)序分拆方案4211、431分別對(duì)應(yīng)3個(gè)和2個(gè)有序分拆方案（總的方案數(shù)為7）：4211121112， 43113求解：利用有序分拆求方案數(shù)（分類(lèi)計(jì)算）：4的1有序分拆數(shù)為 C(4-1，1-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。各項(xiàng)求和，即得4的全部有序分拆數(shù)為8，但本題中無(wú)4分面值的郵票，故不算，恰為7種方案。困難性：不能一次計(jì)算到位?！纠?.4.4】（各分項(xiàng)有限不重復(fù)）若有1克的砝碼3枚，2克的4枚，4克的2枚，問(wèn)能稱(chēng)出多少種重量？各有幾種方案？（解）分析：無(wú)序分拆中處于不重復(fù)分拆（例2.4.1）和無(wú)限重復(fù)分拆（例2.4.2）之間的有限重復(fù)分拆問(wèn)題。母函數(shù)G(x)1x2x22x33 x43x54x64x75x85x95x105 x114 x124 x133 x143 x152 x162 x17x18x19結(jié)果：共能稱(chēng)出19種重量例：稱(chēng)8克重量（即8的分項(xiàng)為1、2、4的無(wú)序分拆）8444224211222222211擴(kuò)展：若將1克的砝碼改為4枚，方案增加841111221111【例2.4.5】（擴(kuò)展）在例2.4.4中，若砝碼可以放在天平的兩邊，但兩邊不能同時(shí)有同樣重量的砝碼，請(qǐng)給出問(wèn)題的母函數(shù)。問(wèn)要秤出2克重的物體，有多少種不同的秤法？并給出每一種秤法。（解）分析：物體一邊的砝碼抵消了天平另一邊砝碼重量。G(x) 2233434 3434343433 2213171316結(jié)果：秤2克重物體的不同秤法有13種。枚舉：用不同符號(hào) x、y、z代表不同砝碼：G(x) （1 ）（ ）例：稱(chēng)2克的重量，有13種方法（負(fù)數(shù)表示砝碼放在左邊，正數(shù)表示砝碼放在右邊）112(-1)(-1)22(-1)(-1)4(-2)411(-2)(-2)4222(-4)1122(-4)(-1)(-1)(-2)(-2)44(-1)(-1)2222(-4) (-2)(-2)(-2)4411(-2)(-2)(-2)(-2)44112222(-4)(-4)反例：用上邊的母函數(shù)反映不出來(lái)的稱(chēng)法（即天平兩邊放有同一重量的砝碼，使得相同砝碼抵消）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個(gè)骰子，點(diǎn)數(shù)之和為n（3n18），其方案有多少種？骰子的情況如下：（1）3個(gè)骰子相異；（2）3個(gè)骰子相同。（解）（1）3個(gè)骰子不同（3個(gè)骰子分別為紅、蘭、黃色），問(wèn)題等價(jià)于n的每個(gè)分項(xiàng)都有限制的特殊有序3-分拆。即由定理2.4.1知，相應(yīng)的母函數(shù)為25273骰子的點(diǎn)數(shù)之和等于n的投擲方案?jìng)€(gè)數(shù)就是的系數(shù)。例如點(diǎn)數(shù)之和等于15的方案有10種，即663636366654645564546465456555原理：假設(shè)和式中的第一個(gè)加數(shù)為紅色骰子的點(diǎn)數(shù)，后兩個(gè)加數(shù)分別為蘭色和黃色骰子的點(diǎn)數(shù)，而這也恰好反映了15的每個(gè)分項(xiàng)值不超過(guò)6的全部有序3分拆。（2）3個(gè)骰子相同，問(wèn)題等價(jià)于n的特殊無(wú)序3-分拆。其特殊性體現(xiàn)在對(duì)每個(gè)分量的值都限制在16之間，即利用Ferrers圖，問(wèn)題又可轉(zhuǎn)化為求n的最大分項(xiàng)等于3，且項(xiàng)數(shù)不超過(guò)6的分拆數(shù)，即求方程的非負(fù)整數(shù)解的個(gè)數(shù)。母函數(shù)2345666 65432其中點(diǎn)數(shù)之和等于n的方案數(shù)就是的系數(shù)（3n18）。例如點(diǎn)數(shù)之和等于10的方案有6種，即10631622541 532442433這也是10的每個(gè)分項(xiàng)值不超過(guò)6的無(wú)序3分拆數(shù)。習(xí) 題 二（1）基本題：1，3，69，1315，18（2）加強(qiáng)題：2，5，1011（3）提高題：4，12，16，171. 求下列數(shù)列的母函數(shù)（n0,1,2，）：（1）； （2） n5 （3） n(n1) ； （4） n(n2) （解）（1）（2）（3）（4）2. 證明序列C(n，n)，C(n1，n)，C(n2，n)，的母函數(shù)為（證）已知集合的r-組合的母函數(shù)為所以序列，的母函數(shù)為3. 設(shè)S，求序列的母函數(shù)，其中an是S的滿(mǎn)足下列條件的n組合數(shù)：（1） S的每個(gè)元素都出現(xiàn)奇數(shù)次；（2） S的每個(gè)元素出現(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的每個(gè)元素至少出現(xiàn)10次。（解）（1）；（2）；（3）；（4）；（5）。4. 投擲兩個(gè)骰子，點(diǎn)數(shù)之和為r（2r12），其組合數(shù)是多少？（解）相應(yīng)的母函數(shù)為其中點(diǎn)數(shù)之和為n的方案數(shù)就是的系數(shù)。5. 居民小區(qū)組織義務(wù)活動(dòng)，號(hào)召每家出一到兩個(gè)人參加。設(shè)該小區(qū)共有n個(gè)家庭，現(xiàn)從中選出r人，問(wèn)：（1）設(shè)每個(gè)家庭都是3口之家，有多少種不同的選法？當(dāng)n50時(shí)，選法有多少種？（2）設(shè)n個(gè)家庭中兩家有4口人，其余家庭都是3口人，有多少種選法？6. 把n個(gè)相同的小球放入編號(hào)為的m個(gè)盒子中，使得每個(gè)盒子內(nèi)的球數(shù)不小于它的編號(hào)數(shù)。已知，求不同的放球方法數(shù)。7. 紅、黃、藍(lán)三色的球各8個(gè)，從中取出9個(gè)，要求每種顏色的球至少一個(gè)，問(wèn)有多少種不同的取法？（解）設(shè)從中取r個(gè)的不同取法有種，那么，數(shù)列的母函數(shù)為因此所求方案數(shù)為28另法：原問(wèn)題等價(jià)于從集合S中取出9個(gè)元素，且每個(gè)元素至少取一個(gè)?，F(xiàn)在先把元素a、b、c各取一個(gè)，然后再隨意選出6個(gè)，則問(wèn)題轉(zhuǎn)變?yōu)閺募现腥〕?個(gè)元素，且每個(gè)元素個(gè)數(shù)不限，求重復(fù)組合的方案數(shù)。又由于每個(gè)元素的個(gè)數(shù)大于6，故從中取6個(gè)元素與從集合中取出6個(gè)元素的組合數(shù)一樣多，從而知不同的取法為8. 將幣值為2角的人民幣，兌換成硬幣（壹分、貳分和伍分）可有多少種兌換方法？（解）這是求正整數(shù)n的分項(xiàng)只能等于1、2、5的分拆數(shù)。設(shè)n的分拆數(shù)為 ，則的母函數(shù)為所以，共有29種兌換方法。9. 有1克重砝碼2枚，2克重砝碼3枚，5克重砝碼3枚，要求這8個(gè)砝碼只許放在天平的一端。能稱(chēng)幾種重量的物品？有多少種不同的稱(chēng)法？（解）設(shè)秤r克重的物體有種秤法，那么數(shù)列的母函數(shù)是展開(kāi)后得因此，能稱(chēng)122克共22種重量的物品，所有不同的稱(chēng)法總數(shù)為3×4×44810. 證明不定方程 的正整數(shù)解組的個(gè)數(shù)為 。（證）問(wèn)題可以視為將r個(gè)相同的1放入n個(gè)盒子。由于將之間的值互換，對(duì)應(yīng)不同的解，所以盒子不同。設(shè)共有個(gè)解，則由式（2.1.1）知的母函數(shù)為所以11. 求方程24 的大于1的整數(shù)解的個(gè)數(shù)。（解）原方程即 ，令 ，可得等價(jià)方程由上題知后者共有190組正整數(shù)解，從而知原不定方程的大于1的整數(shù)解的個(gè)數(shù)為190。12. 設(shè)an，bn其中a01，b00，（1） 試證an1anbn1， bn1anbn；（2） 求出 an ， bn 之母函數(shù)A(x)，B(x)。（解），13. 設(shè)S，求序列的母函數(shù)，其中pn是S的滿(mǎn)足下列條件的n排列數(shù)：（1）S的每個(gè)元素都出現(xiàn)奇數(shù)次；（2）S的每個(gè)元素至少出現(xiàn)4次；（3）ei至少出現(xiàn)i次（i1,2, ,k）；（4）ei至多出現(xiàn)i次（i1,2, ,k）。（解）（1）；（2）；（3）；（4）14. 把23本書(shū)分給甲、乙、丙、丁四人，要求這四個(gè)人得到的書(shū)的數(shù)量分別不得超過(guò)9本、8本、7本、6本，問(wèn)（1） 若23本書(shū)相同，有多少種不同的分法？（2） 若23本書(shū)都不相同，又有多少種不同的分法？15. 8臺(tái)計(jì)算機(jī)分給3個(gè)單位，第一個(gè)單位的分配量不超過(guò)3臺(tái)，第二單位不超過(guò)4臺(tái)，第三單位不超過(guò)5臺(tái)，問(wèn)共有幾種分配方案？（解）設(shè)分配n臺(tái)計(jì)算機(jī)的分配方案有種，則的母函數(shù)為1所以分配8臺(tái)計(jì)算機(jī)共有14種方案。16. 用母函數(shù)證明等式（1）。（2）17. 證明：自然數(shù)n分拆為互異的正整數(shù)之和的分拆數(shù)等于n分拆為奇數(shù)之和的分拆數(shù)。（證）將n分拆為互異的正整數(shù)之和的分拆數(shù)的母函數(shù)為將n分拆為奇數(shù)之和的分拆數(shù)的母函數(shù)為所以，兩種分拆的方案數(shù)相同。18. 求自然數(shù)50的分拆總數(shù)，要求分拆的每個(gè)分項(xiàng)不超過(guò)3。（解）方法一 用母函數(shù)。設(shè)正整數(shù)n的分項(xiàng)不超過(guò)3的分拆數(shù)為 ，則的母函數(shù)為所以，50滿(mǎn)足要求的分拆數(shù)為234種方法。另外，可以看出，對(duì)一般的n，記， mod 3 則故當(dāng)時(shí)，t16，r2，代入上式即得235689111221232426（123423242526）（147102225）234方法二 利用遞推公式（2.1.3）求解。這里是求 。首先由公式（2.1.3）知對(duì)任何正整數(shù)n，有。其次，由遞推關(guān)系 知1直接迭代，并利用初值1和2得，即，最后對(duì)m3，有令n50，代入上式得262624262423211211986532234