2022年《組合數(shù)學(xué)》教案2章

1、第 二 章 母 函 數(shù) 及 其 應(yīng) 用1. 普母函數(shù)及其在組合問題中的應(yīng)用 2. 指母函數(shù)及其在排列問題中的應(yīng)用 3. 正整數(shù)的分拆及其組合意義和應(yīng)用問題：對于不盡相異元素的部分排列和組合,用第一章的方法 比較麻煩（參見表 2.0.1）；新方法：母函數(shù)方法；表 2.0.1 條件C組合方案數(shù)r.排列方案數(shù)對應(yīng)的集合相異元素,不重復(fù)rn.r P nnn.r.Se 1,e 2,ennr.n相異元素,可重復(fù)Crr1nrSe 1,e 2,n,e n 不盡特例rn1 n.Sn1e 1,n2e 2,n 1.n2.nm.相異m m ,n me m, 元素全部r1 n 1n2 nmn,（有nrCrr1mrnk1

2、, 限重m（k1,2, , m）復(fù)）至少有一個nk滿意1nkr基本 思想：把離散的數(shù)列同多項式或冪級數(shù)一一對應(yīng)起來,從而把離散數(shù)列間的結(jié)合關(guān)系轉(zhuǎn)化為多項式或冪級數(shù)之間的運 算；2.1 母 函 數(shù)（一） 母函數(shù)（1）定義【定義 2.1.1】對于數(shù)列an,稱無窮級數(shù)Gxn0anxn為該數(shù)列的（一般型）母函數(shù),簡稱（2）例普母函數(shù) 或母函數(shù) ；【例 2.1.1】有限數(shù)列 C （r0, 1, 2, , n）的普母函數(shù)是：n rG xC n 0 C n 1 x C n 2 x 2 C n n x n1 x n【例 2.1.2】無限數(shù)列 1, 1. , 1, 的普母函數(shù)是Gx1xx2xn11x（3）說明a

3、 可以為有限個或無限個；nx2xn1xx 數(shù)列an與母函數(shù)一一對應(yīng)；0, 1, 1, , 1, 0 x 將母函數(shù)視為形式函數(shù),目的是利用其有關(guān)運算性質(zhì)完成計數(shù)問題,故不考慮“ 收斂問題”微分” 和“ 逐項積分” 的；（4）常用母函數(shù),而且始終認為它是可“ 逐項 ak ,k0,1, Gx2 ak ,k0,1, Gx ak1 1ak ak11x1axakk xakk1 11x21xakkk 1 2x3ak k2x1x1x31xak kk 1k6xxak k,任11xx11x42 意a0 0,ak ak-ln1- a x k任1exak .k,k意ak 1kak 2 k1k.cosx1.sinx2

4、kak2k1k1 xarctanak nkkxn1（二） 組合問題（1）組合的母函數(shù)【定理 2.1.1】組合的母函數(shù)：設(shè)Sn 1e 1,n2e 2,n me m,且 n1n2 nmn,就 S 的 r 可重組合的母函數(shù)為Gxmnixjnarxr其中, r 可重組合數(shù)為i1j0r0 x 之系數(shù) rra ,r0, 1, 2, , n；理論依據(jù)：多項式的任何一項與組合結(jié)果一一對應(yīng)；優(yōu)點：將無重組合與重復(fù)組合統(tǒng)一起來處理；使處理可重組合的枚舉問題變得特別簡潔；（2）特例【推論 1】Se 1,e 2,e n,就 r 無重組合的母函數(shù)為Gx 1xn組合數(shù)為r x 之系數(shù)C ；n r【推論 2】Se 1,e

5、2,e n,就 r 無限可重組合的母函數(shù)為Gxxjn11xnj0組合數(shù)為r x 之系數(shù)Cr nr1；e n,每個元素至少選一個：【推論 3】Se 1,e 2,nxn母函數(shù)Gxj1xj1x組合數(shù)Cn r1 1e n,每個元素選非負偶數(shù)個：【推論 4】Se 1,e 2,母函數(shù)Gx1x2x4x2nn11nx20,當r為奇數(shù)當r為偶數(shù)；組合數(shù)ra Cnr1,r,22【推論 5】Se 1,e 2,e n,每個元素選奇數(shù)個：母函數(shù)Gxxx3x5x2n1n1x2nx0,當rn 為奇數(shù)2n,當rn為偶數(shù)組合數(shù)arCnr2n1,r【推論 6】Sn 1e 1,n2e 2,nme m,且 n1n2 nmn,元素ie

6、 至少顯現(xiàn)ik 次：為母函數(shù)Gximjniixjrnkarxr組合數(shù)1karrk, k1, , n,kk1k2 km；（3）一般情形：設(shè)S20.a,30.b,.c,并設(shè)元素a只能顯現(xiàn) 15,10,13,16 次,b 只答應(yīng)顯現(xiàn)奇數(shù)次, c 至少顯現(xiàn) 5 次且必需顯現(xiàn)偶數(shù)次,求S的 r 可重組合的母函數(shù)；Gxxx2x5x5x10 xx13x8x16xx3x296（三） 應(yīng)用【例 2.1.3】設(shè)有 2 個紅球, 1 個黑球, 1 個白球,問（1） 共有多少種不同的選取方法,試加以枚舉？（2） 如每次從中任取3 個,有多少種不同的取法？（解）（1）元素符號化（ x,y,z 紅、黑、白球）,元素 的個

7、數(shù)以符號的指數(shù)區(qū)分；母函數(shù)Gx, y, z 1xx2 1y 1z 1xyzx2xyxzyzx2yx2zxyz x2yz 5 種情形： 數(shù)字 1 表示一個球也不取的情形,共有 1 種方案； 取 1 個球的方案有 3 種,即紅、黑、白三種球只取 1 個； 取 2 個球的方案有 4 種,即 2 紅、1 紅 1 黑、1 紅 1 白、1 黑 1 白； 取 3 個球的方案有 3 種,即 2 紅 1 黑、2 紅 1 白、三色球各一； 取 4 個球的方案有 1 種,即全取；令 xyz1,得方案總數(shù)G1,1,1 1343112 （2）只考慮每次取 令 yx,zx 3 個的方案數(shù),不需枚舉Gx1xx2 1x 1x

8、13x4 x23 x3x4由 x3的系數(shù)即得所求方案數(shù)為 3；【例 2.1.4】有 18 張戲票分給甲、乙、丙、丁 4 個班（不考慮座位號）,其中甲、乙兩班最少 1 張,甲班最多 5 張,乙班最多 6 張,丙班最少 2 張,最多 7 張,丁班最少 4 張,最多 10 張,問有多少種不同的安排方案？（解）（1）分析： 實質(zhì)為甲、乙、丙、丁四類共 28 個元素中可重復(fù)地取 18 個元素的組合問題；S 5 e 1 , 6 e 2 , 7 e 3 , 10 e 4,m 4 , n n1 n2 n3 n4 5 6 7 10 28 , k k 1 k 2 k 3 k 4 11248,r18；（2）求解：母

9、函數(shù)5 6 7 10Gxx i x i x i x ii 1 i 1 i 2 i 4x8 140 x18 x28 （3）特別情形處理 ：戲票數(shù) r4,ik 0（i1, 2, 3, 4）5 6 7 10G1xx i x i x i x ii 0 i 0 i 0 i 01 4 x 35 x 4x 284G 2xix14i 0 1 x4 281 4 x 35 x 4495 x4 x 系數(shù)相同,用 G2x運算要比用 G1x便利得多（由于將i50i x 擴展為i x 不影響x 的系數(shù)）4i0同理, r6,可用G3x5xixj35xi1x3i0j0i0r 只（rn）,要求其代替 G1x求6 x 的系數(shù)；【

10、例 2.1.5】從 n 雙相互不同的鞋中取出中沒有任何兩只是成對的,問共有多少種不同的取法？（解）解法一 ：母函數(shù)法；視為,S,2e 1,2e 2, 2e n,但同類中的兩個ie 不一樣,即e ne n2Se 11,e 12,e 21,e 22故其 r 重組合的母函數(shù)為不同的取法共有aGx12xnrn0n2r xrrrn2 種；r本質(zhì)：每類元素最多只能顯現(xiàn)一次,但同類元素互換后方案不同；故 Gx1C1xn中不能有x 項,再由同雙的兩只鞋子 22有區(qū)分知, x 的系數(shù)應(yīng)為 2；解法二 ：排列組合；先從n 雙鞋中選取 r 雙,共有n 種選 r法,再從今 r 雙中每雙抽取一只,有2 種取法；r解法三

11、 ：排列組合；先取出k 只左腳的鞋,再在其余nk雙鞋中取出rk只右腳的鞋k01,2,r：ra nnnn1nn2nn0r0r1r12r2r得組合恒等式nnnn1nn2nn0rn2r0r1r12r2rr一般提法 ：Se 11 , e 12 , , e 1 n 1；e 21 , e 22 , , e 2 n 2；e m 1 , e m 2 , , e mn m從中取出 r 個,第 i 類元素最少 ik 個,最多 it 個,母函數(shù)：m t i n i jGxxi 1 j k i j舉例, 把 5 本相同的書分給甲、乙、丙 3 個班,再發(fā)到個人手上,每人最多發(fā)一本；考慮將分給某班的某本書發(fā)給該班的同學(xué)

12、A 與將其發(fā)給同學(xué)B 被認為是不同的分法,而且甲、乙兩班最少 1 本,甲班最多5 本,乙班最多6 本,丙班最少2 本,最多 9本,問有多少種不同的安排方案？nSe 11,e 12,e 15；e 21,e 22,e 26；e 31,e 32,k3,e 39,m3,n1n2n356920,kk1k21124,r5；母函數(shù)5 5 i 6 6 i 9 9 iGxx x xi 1 i i 1 i i 2 i5 6 9x 41 1 25 6 9 5 6 9 5 6 9x 51 1 3 1 2 2 2 1 25 6 9x 205 6 91080 x 7380 4 x x 20共有 7380 種安排方案；說明

13、：與問題“ 從 20 個相異元素中不重復(fù)地抽取 5 個元素”不等價（答案為20 15,504）；5【例 2.1.6】甲、乙、丙 3 人把 n（n3）本相同的書搬到辦公室,要求甲和乙搬的本數(shù)一樣多,問共有多少種安排的方法？（解）（1）分析：組合問題：從集合 S e 1 , e 2 , e 3中可重復(fù)地選取 n 個元素,要求 1e 與 e 的個數(shù)一樣多,求不同的 2選取方案數(shù)；特點：限制盒子之間的關(guān)系；（2）特例：n1,1 種分法,甲和乙都分 0 本（丙 1 本）；n2,2 種分法：甲和乙分 0 本（丙 2 本）或甲和乙 1 本（丙0 本）；當 n3 時,分法 2 種；當 n4 或 5,3 種分法

14、：甲和乙都分0 本、 1 本或 2 本；（3）一般情形 ：視為 2 個大盒子 A、B,且 A 又分為 2 個小 盒子；分兩步安排：第一步： A 盒子分偶數(shù)本, B 盒子分任意本；其次步：將分給 A 盒的書再給甲、乙各分一半；GA （2k 本）B（n2k 本）甲（k 本）乙（k 本）丙（n2k 本）x1x2x4x2k1xx2xk211x21x11111141x41x21x1n01n x 1n0 xn1n0nn1xn442n0n21141nxnn0n21xnn21種；不同的安排方法共有x 上整數(shù)函數(shù)；即不小于（待定系數(shù)法：分解有理多項式：1111xx11x2x2x1A1BC2x1xx 的最小整數(shù)；

15、A1x2B1xx1xx2C1x,112ABx2xABC12ACx1x2BC1A比較同次冪系數(shù)得方程組AAC0,B0解之得 AB1/4,C1/2）【例 2.1.7】證明組合等式（1）n2n3nnnnnnn 211n 22nmm,123n（2）n22n32n2nnn123n（ 3）nmnmmnm m001122mnm（證）（1）二項式1xnnnxnx2nxn012n兩端求導(dǎo)n1xn1n2nx3nx2nnxn1（* ）123n令 x1 即可；（2）（* ）式兩端同乘以 x 后求導(dǎo)nn1xn13nn1x1xn2xn122nx2nx2n2n123n令 x1；（3）1xn11mxm1xmnx兩邊綻開nn0

16、 xn 2x21nnxnmx101mnmm1.01x2x2mxmxmmnmnxm2n21mnxmmnxmmmn比較兩邊的常數(shù)項；2.2 母 函 數(shù) 的 性 質(zhì)母函數(shù)與生成數(shù)列一一對應(yīng)如兩個母函數(shù)之間存在某種關(guān)系,就對應(yīng)的生成數(shù)列之間也必定存在相應(yīng)的關(guān)系；反之亦然；設(shè)：數(shù)列 a k、b k、c k的母函數(shù)分別為 Ax、Bx、Cx,且都可逐項微分和積分；【性質(zhì)1】 如b k0,rkrrr（即akb kr）,就Bxak,kxrAx；b r1xr1b rxrb r1xr1（證） Bxb 0b 1xb 2x2000b rxrb r1xr1r個向右移 r 個位置且前面補0 a0 xra1xr1xrAx分析

17、 ：a ka 0,a 1,ar1,a r,00 ,0 ,a 0a 1,b kb 0,b 1,b r1,b r,b r1,【性質(zhì) 2】如b ka kr,就1aixixrBxAxi0（證） Bxb0b1 xb2 x 2 arar 1 x ar 2x 2分析 ：a k,x 1 ar x rar1 x r 1 ar 2x r2 rrAxa0a1xa2x2ar1xr1xa 0,a 1,a k,向左移 r 個位置且前面舍掉b kb 0b 1,b k,ar,ar1,akr,【性質(zhì) 3】如bkiik0ai,就 BxAx；xn1x（證）等式b kkai兩端乘以k x 對 k 求和：k0:b 0 x00a0k1:

18、b 1xa 0 xa 1xk2:b 2x2a0 x2a 1x2a2x2kn:b nxna 0 xna 1xna 2xna n b nxnnxnxinxnaninxiain0n0i0即 Bxa 0 xia 1xia2i0i1xii2axia0 xia1xi0i0i0a0aa 1xxa2x2anxn11x1x1x1x0a1a2x2anxn1 Ax x1x例,已知Ax1xx 2 x n 11x,（a 1）kx x1令b kaik1 i0Bx12x3x 2 k0k1xkA11x2或Bxk0kxkk0 xkk0 xkk0 xk11213x同理,令 ckkib12 k1,可得i0Cx13x6x 210 x

19、315x4k0k1k2xk1132x1CxBxAx12x3x 2 1xx 2 x類推：DxCx Ax13x6x 210 x3 1xx 2 0k1k2k3ixk1146xk【性質(zhì) 4】如iia 收斂,且 b kkia ,就0BxA11xAxx（證）第一由條件知b k 存在,按定義b0a0a1a2 A1 b1a1a2a3 A1a0 bkakak 1ak 2 A1a0a1a2 ak-1 給 bk 對應(yīng)的等式兩端都乘以左端k0b kxkBx xk并分別按左右求和,得右 端 A1 xA1a1a0 x 2A1a0a1 x 3A1a02aA11xx 2 a0 x1xx 2 a1x2 1xx 2 A1 x1

20、xxa 0a 1xa2x2x1 AxAx1Ax 1xA1x1x1【性質(zhì) 5】如 bkkak,就 BxxA x ；（證） Bx k1b kxk0kakxkxk1kakxk1k0 xakxkxka kxkk1xAx a0 xAx 【性質(zhì) 6】如 b kakk,就 Bx1xAxdxdx1x0（證 ）Bx k0b kxkk01akkxkk0a k1xxkx01xk0akxkdx1xAxdxx0 x0【性質(zhì) 7】如 c kkaib ki,就 CxAx Bx ；i0（證）c0a0b0 c1a0b1a1b0 c2a0b2a1b1a2b0 cna0bna1bn-1 anb0給 ck 對應(yīng)的等式兩端都乘以xk后

21、左右兩邊分別求和,得Cxa0b0a0b1a1b0 xa0b2a1b1a2b0 x2 a0bna1bn-1 anb0 xna0 b0b1xb2 x2 a1xb0b1xb2 x2 a2x2b0b1xb2 x2 a0a1xa2 x2 b0b1xb2 x2 Ax Bx 2.3 指 數(shù) 型 母 函 數(shù)回憶：一般型母函數(shù)較好地解決了各種組合的計數(shù)問題；分析：組合數(shù)數(shù)列的母函數(shù)在解決計數(shù)問題和證明組合恒等式時之有用的緣由：具有有限封閉形式；啟示：對排列問題也采納母函數(shù)方式；特別是 n 個不盡相異元素中取 r 個的排列問題；困難：對于排列數(shù)數(shù)列 Pn,r ,采納一般型母函數(shù)特別不便；緣由：它不能表為初等函數(shù)形

22、式；改進：n 集的 r 無重排列數(shù)和 r 無重組合數(shù)之間的關(guān)系：Cn,r P n , rr .1xnnC n , r x rnP n , r x rr 0 r 0 r .x r總結(jié)：在1xn的綻開式中,項 的系數(shù)恰好是排列數(shù)；啟示：r .x k排列數(shù)數(shù)列的母函數(shù)為k 0 a k k .；（一） 數(shù)列的指母函數(shù)（1）定義數(shù)【定義 2.3.1】對于數(shù)列 a a 0,a 1,a 2, ,把形式冪級G e xn 0 a n xn n.a 0a1 . x a2 x2 2. an xn n.稱為數(shù)列 a k 的指數(shù)型母函數(shù) ,簡稱為 指母函數(shù) ,而數(shù)列 a k 就稱為指母函數(shù)Gex的生成序列 ；（2）例1

23、a 1 ,Gex r0r x r .e ；x2a P n k,Gexn0r xP n rr .1xn r（3）說明1a 可以為有限個或無限個；nxnex12數(shù)列an指母函數(shù)；例0,1,1, ,1, 0 xx2.1.2n .3將母函數(shù)視為形式函數(shù),且始終是收斂的；4同一數(shù)列數(shù)列 a ,一般 Gx Gex；例 a 1 的普母函數(shù)為 Gx1x,指母函數(shù)為 Gexx e ；1例外：當a 0 時（ k2）,a 1x .1Gex Gxa0a 1xa05對同一函數(shù)fx,令k0ax k kk1x4i3.fxGex.或fxGxk0bkxk就一般akbk；例外fxa0a1x；sinxxx3x5x7x4i1.1.3

24、.5.7,04i1 .4i3視sinxGx為普母函數(shù),就1,0 ,b n0,1,0 ,1,.1.3.5.7視sinxGex為指母函數(shù),就,0,1,0,1a n,0,1,0,1（二） 排列問題【 定 理 2.3.1 】 設(shè) 重 集 S n 1 e 1 , n 2 e 2 , , n me m , 且n 1 n 2 n m n n1n2 nmn,就 S 的 r 可重排列的指母函數(shù)為Gexi m1 j n i0 xj . jr n0 a r r x. r其中, r 可重排列數(shù)為 xr .r 之系數(shù) ra ,r0,1,2, ,n ；【例 2.3.1】盒中有 3 個紅球, 2 個黃球, 3 個籃球,從中

25、取 4個球,排成一列,問共有多少種不同排列方案？（解） m3,n 3,n 2,n 3,r4 xx2x3Gex1xx2x31xx211.2.3.1.2.12.3.13x9 x 28 x 1 x 872 7213 x 335 x 1217x 1235 x 7213x 1 .9x226x370 x4170 x52.4.5.3350 x6560 x7560 x86.78.取 4 個球的排列方案數(shù)為70；枚舉：令Ger,y,b 1rr2r31yy21bb2b31.2.3.1.2.1.2.3.1Ger,y,b1r y.11 r 2 y 2 b 2 2 ry.21 r 3 b 3 3 r 2 y 3 r.3

26、3 y 2 b ryb2b3yb22 rb2ybb3ry 23rb 2 560r3y2 b38.1 個；具體枚舉：取 1 個球的 3 種排列方案為紅、黃、藍各分別取取 2 個球的 9 種排列方案為：紅紅、黃黃、藍藍、紅黃、黃紅、紅藍、藍紅、黃藍、藍黃；說明：（1）利用普母函數(shù)能枚舉到每一種組合情形,但指母 函數(shù)做不到,只能對排列進行分類枚舉；（2）一個問題的普目函數(shù)和指目函數(shù)可以相互轉(zhuǎn)換；例：在Ger,y,b令每一項系數(shù)為 1,即得普母函數(shù)；（3）已知問題的普母函數(shù)Gr,y ,b,可利用其生成指母函數(shù)；.3.0r3.0.3.0b3.3r2y.3r2 b.1.3ry2.3 .0.3.2 .1 0

27、 .2 . .1.0.2.0.1.3rb2.0.3y2b.3yb2.3ryb.0.2.2 .10 .1.2.1 .1.1（三） 特例【推論 1】Se 1,e 2,e nrxr指母函數(shù)Gex1xnrn0P n r r xr.1.排列數(shù)為xr之系數(shù)P ；n r.r【推論 2】Se 1,e 2,e n指母函數(shù)Gexj0 xjnenxr0nrxrj.r.排列數(shù)為nr【特例】每個元素至少選一個（即rn）ex1nnCne inix1inCi1innr.i0i0r0r0in01iCinirxrnr.ki 個（ki方案數(shù)in1iCi nnir；0【推論 3】Sn1e 1,n2e 2,nme m,ei 至少取0

28、）指母函數(shù)Gexn1im,jn ixj,nme m,rn,全排列數(shù)1kij.【推論 4】Se 1n2e 2,n .n 1.n2.n m.（四） 應(yīng)用【例 2.3.2】五個數(shù)字 1,1,2,2,3 能組成多少個四位數(shù)？（解）用 ra 表示組成 r 位數(shù)的個數(shù), ra 的指母函數(shù)為x x 2 x x 2 xG e x 1 1 11 . 2 . 1 . 2 . .11 3 x 4 x 2 3 x 3 5x 4 1x 54 413 x 8 x 218 x 330 x 430 x 51 . 2 . 3 . 4 . 5 .能組成 30 個四位數(shù)；【例 2.3.3】求 1,3,5,7,9 五個數(shù)字組成的 n

29、 位數(shù)的個數(shù)（每個數(shù)字可重復(fù)顯現(xiàn)）,要求其中 3,7 顯現(xiàn)的次數(shù)為偶數(shù), 1,5,9顯現(xiàn)的次數(shù)不加限制；（解）設(shè)滿意條件的n 位數(shù)的個數(shù)為a ,nan3指母函數(shù)：Gex1x2x421xx2x32.4.1.2.3.ex2ex2e3x1e5x52e3xexnxnn0 xn14nxn321n0.4n .nnn0n23n5nn5n1xn4n .2301an4【例 2.3.4】把上例的條件改為要求 5 和 9 顯現(xiàn)的次數(shù)不加限制；求這樣的1、3、7 顯現(xiàn)的次數(shù)一樣多,n 位數(shù)的個數(shù)；（解）設(shè)滿意條件的數(shù)有b 個,類似例 2.1.6 .1x5Gex11.3 .1.x32.6 .2.x61.3 .2.6 .

30、1xx2x321.2.3.11.x31.2.x62.2 ex1.2 .11.x31 .2.x62.1.2.12x22x223x31.2.3.12x22x2231 .31.x31.2.1.3.2421.41.x425221.51.4.21 .5.26231.61.2.62.x6.31.2.6.1 2 x4 x 214 x 364 x 4272 x 51114 x 61 . 2 . 3 . 4 . 5 . 6 .即：b 1,b 2, 2 b 4, 3 b 14, 4 b 64, 5 b 272, 6 b 1114 一般情形,當 n3 k i 時 i 0,2；k 0,n 3 n 6 ib n 2 n

31、 2 n . 2 n . 2 n .n 3 . 1 . 1 . 1 . n 6 . 2 . 2 . 2 . i . k . k . k .懂得（按排列）：【例 2.3.5】在例 2.1.5 中,如把所取出的 r 只鞋再排成一列,問共有多少種結(jié)果？（解）即從集合 S e 11 , e 12 , e 21 , e 22 , , e ne n 2 的 n 類共 2n 個元素中不重復(fù)地取出 r 個元素排成一列, 且同一類元素 ie ,ie 不能同時顯現(xiàn)（ 1in）；指母函數(shù)：Ge x1 P 2 1x nn n2 r x rn n2 r r . x rr 0 r r 0 r r .不同的排列數(shù)為 n2

32、r r .P 2 ；n r rr與例 2.1.5 類似,本問題的排列數(shù)也可以從排列的角度懂得為：先從 n 雙鞋子中不重復(fù)地選出 r 雙排成一列,共有 P 種排列情形,n r再從所選的每雙鞋中抽取一只,有 2 種取法；由乘法原理,即得 r所求結(jié)果；安排問題 ：將 r 個不同的球放入n 個不同的盒子,每個盒子最多放一個球,而且每個盒子中有兩個相異的格子,故仍需要進 行二次安排；假如某個盒子中放進一個球,那么,二次安排時有 兩種可選的方案；一般提法 ：集合 S 中有 m 類元素,第 i 類元素有 in 個,且同 一類元素也互不相同,從 S 中取出 r 個元素排成一列,問共有多 少種排列結(jié)果？其中要求

33、第 i 類元素最少 ik ,最多 it 個,就此排列 問題的指母函數(shù)為GeximjtiP n jixjrn0ax r rr1kj.即得問題的答案ra （r0,1, , n）；2.4 正 整 數(shù) 的 分 拆 問題：將一個正整數(shù)分拆成如干個正整數(shù)之和；關(guān)聯(lián)問題：安排問題、一次方程整數(shù)解的個數(shù)問題；（一） 概念【定義 2.4.1】nin1,n2,12 ,nk,k1n1i,k稱該分解是 n 的一個 k 分拆,并稱（二） 分類有序分拆考慮in 間的次序；n 為重量（或分項）；例 521111211無序分拆 不考慮次序（可把分項按大小排序） ；例 52111323112.4.1 有 序 分 拆求 n 的

34、k 有序分拆的個數(shù) 的組數(shù)；求一次不定方程全體正整數(shù)解可對每個重量in 加以條件限制： 1in ir （ i 1, 2, , k）；【定理 2.4.1】n 的 k 有序分拆分拆數(shù)列qknnn1n2i1 ,n k,k11niri;2 ,k的母函數(shù)：k r ix j x x 2 x r 1x x 2 x r 2i 1 j 1x x 2x kr組合意義（安排問題）：把 n 個相同的球放入 k 個不同的盒子里,第 i 個盒的容量為 ir （ i 1,2, ,k）,且使每盒非空；【推論】如對 n 的 k 有序分拆的各重量in 沒有限制, 就其 k 有序分拆數(shù)列qkn的母函數(shù)是1xxk,且qknCk1；n

35、12.4.2 無 序 分 拆（一） 問題nn1n2nnk,k1n1n2pknk1簡稱分拆,分拆數(shù)記作,n 稱為 最大分項 ；1問題轉(zhuǎn)換：將 n 分拆為 k 項（每一項的大小不受限制）的分拆數(shù)等于將 n 分拆為最大分項為k（分項個數(shù)不限）的分拆數(shù)；設(shè)滿意后一種條件的k 分拆數(shù)也為pkn；（二） 最大分項n k 的分拆 1分拆數(shù)不定方程整數(shù)解的組數(shù)1x12x2i1,kxk,kn1,xk1xi0,2,即整數(shù) n 由 1,2, , k 答應(yīng)重復(fù)且 k 至少顯現(xiàn)一次的全部組合 數(shù)；母函數(shù)：1xx21x2xxx22xk3n1nx3x32k2xk1x1xk1knp kxx2k（三） 最大分項 n k 的分拆

36、 1分拆數(shù)不定方程整數(shù)解的組數(shù)1 x 1 2 x 2 kx k nx i 0 ; i 1 , 2 , , k分拆數(shù)列 rk n 的母函數(shù)：1 x x 2 1 x 2 x 2 21 x 3 x 3 21 x k x k 2x k 31 x 1 x 12 1 x kn k r k n x n2.4.3 Ferrers 圖（一） 定義一個從上而下的 k 層格子,設(shè) m 為第 i 層的格子數(shù),當 i m im i 1（ i 1,2, ,n-1）,即上層的格子數(shù)不少于下層的格子數(shù)時,稱為 Ferrers 圖；（a）（b）（二） 性質(zhì)（1）每一層至少有一個格子（2）Ferrers 圖與 無序分拆對應(yīng)關(guān)系：

37、 第 1 層的格子數(shù)對應(yīng)分項 分項 n , ；n ,第 2 層的格子數(shù)對應(yīng) 1圖（a）2075521 （3）“ 轉(zhuǎn)置” 的圖仍為Ferrers 圖,稱為原 Ferrers 圖的共軛圖,或者說這兩個圖是 一對共軛的 Ferrers 圖；如某個 Ferrers 圖與其共軛圖外形相同,就稱其是 自共軛 的；共軛圖對應(yīng)的分拆叫做 共軛分拆圖（ b）共軛分拆 205433311 （三） 應(yīng)用【定理 2.4.2】（1）n 的全部 k 分拆的個數(shù)等于把n 分拆成最大分項等于k的全部分拆數(shù)；（2）把 n 分拆成最多不超過k 個數(shù)之和的分拆數(shù)等于把n 分拆成最大分項不超過k 的全部分拆數(shù)；（證）兩種分拆一一對應(yīng)

38、關(guān)系；【推論】正整數(shù) n 分拆成互不相同的如干個奇數(shù)的和的分拆數(shù),與 n 分拆成有自共軛的Ferrers 圖的分拆數(shù)相等；（證）建立一一對應(yīng)關(guān)系；設(shè)n2n 112 n212nkk1,n1n2nkFerrers 圖特點：第 i 行、第 i 列元素為n1個；是自共軛的；反之亦然；17953 2.4.4 分 拆 數(shù) 的 估 計令 pnn 的全部無序分拆數(shù)（稱作 npnk1p k nn 的分拆數(shù) ）【定理 2.4.3】正整數(shù) n 的全部分拆總數(shù)數(shù)列pn的母函數(shù)是Pxn0pnxn1x1x11xk2當 n 較大時,運算 pn是特別困難的；p11,p57,p1042,p15176, p20627,p2519

39、58,p20039729990293884 萬億pn的漸進公式和估值不等式：【例 2.4.4】關(guān)于pn的運算,有2n,n（1）pne20n3（2）pn13e34 n（3）2npnn3n,n2. 利用二元遞歸函數(shù)運算 pn的算法：【定理 2.4.5】令 Q n , m正整數(shù) n 的最大分項 n1m 的全部分拆數(shù)：Qn,m1,n,n,n1,nm,mm1 或n1Qmn1Qn,mnQn,m1Q,1mn實質(zhì)上是函數(shù) Qn,m的一種遞歸定義；pnQn ,n；明顯有 Q1,n Qm,11；12 由于最大重量 n1 實際上不能大于 Qn,n；n,故 m n 時,Qn,m3 由于在 n 的全部分拆中, 其 1

40、分拆只有一個, 即 nn1,而其它的分拆都是 n1n- 1；4 N 的最大分項為 m 的分拆數(shù)分為兩部分：以 m 作為第一分項,其余分項之和等于nm,且最大分項 n2 不超過 m 的分拆數(shù) Qn- m,m；最大分項 n1m- 1 的分拆數(shù) Q n,m- 1；2.4.5 應(yīng) 用【例 2.4.1】（各分項不同,即不重復(fù) ）設(shè)有 1 克、2 克、3 克、4 克的砝碼各一枚,如要求各砝碼只能放在天平的一邊；問能稱出 那幾種重量？有哪幾種可能方案？（解）典型的正整數(shù)分拆問題；例：6 克物品 32142 分拆條件：最大分項不超過 4 時,6 的無序不重復(fù)分拆有兩種 一般條件：將整數(shù) n 分拆為最大分項不超

41、過 4,且各分項最多 只能顯現(xiàn)一次的分拆；母函數(shù)：1x1x21x31x48x9x101xx22x32x42x52x62x7x結(jié)論：可稱出從1 克到 10 克共 10 種重量,冪n x 的系數(shù)即為稱出 n 克重量的方案數(shù)；枚舉：分拆數(shù)的母函數(shù)：2 3 41 x 1 y 1 z 1 w 1 x y2xy2 z3xz3w4xy 2 z 3 y 2 w 4xw 4 y 2 z 3xy 2 w 4 z 3 w 4xz 3w 4 y2z3w4xy2z3w4規(guī)律：如 x n 1 y n 2 z n 3 w n 4（in 0 或 i ）中各因子的指數(shù)之和為n,就單項式 x n 1 y n 2 z n 3 w

42、n 4 對應(yīng)一種稱 n 克重量的方案；例：z 3w 4對應(yīng)稱 7 克重量的方案之一,而且用的是 3 克和 4克的砝碼；另一方案為 xy 2w 4xy2w4對應(yīng)的用 1 克、2 克和 4 克的砝碼；說明：a 取 12324,重量相同, 元素個數(shù)不同, 對應(yīng)所取元素個數(shù)不同的組合方案；b 如取兩個元素,如 235,347,元素個數(shù)相同,但重量不同,是不同的整數(shù)的分拆方案；c 組合關(guān)懷的是元素的個數(shù), 分拆關(guān)懷的是元素的加權(quán)和 （每個元素給予肯定的權(quán)值） ；對于組合而言,其母函數(shù)應(yīng)為1 x 1 y 1 z 1 w1xyzwxyxzxwyzywzw xyzxywxzwyzwxyzw 【例 2.4.2】

43、（各分項無限重復(fù) ）求用 1 分、2 分、3 分的郵票貼出不同面值的方案數(shù)；（解）分項可（無限）重復(fù)的無序分拆；母函數(shù)：Gx1xx2 1x2x4 1x3x6 1 1 11 x 1 x 2 1 x 33 14 5 61 x x x x x1 x 2 x 23 x 34 x 45 x 57 x 6例：x 系數(shù)為 4,貼出 4 分面值的方案有 4 種,即 441111,4211,422,431 說明：此題是根據(jù)郵票總面值的不同來區(qū)分并統(tǒng)計方案數(shù)的；如將郵票貼成一行, 不同面值的郵票互換位置后算作另一種方案,就問題將成為有序分拆；【例 2.4.3】（有序分拆 ）在例 2.4.2 中,根據(jù)有序分拆,貼成

44、總面值等于 4 分的方案數(shù)是多少？（解）例：無序分拆方案 4211、431 分別對應(yīng) 3個和 2 個有序分拆方案（總的方案數(shù)為 7）：4211121112,43113 求解：利用有序分拆求方案數(shù)（分類運算）：4 的 1 有序分拆數(shù)為 q 1 4C4- 1,1-11,即 44 分拆為自身；4 的 2 有序分拆數(shù)為q24C4- 1,2- 13,即 4311322；4 的 3 有序分拆數(shù)q34C4- 1,3- 13,即 4211121112；4 的 4 有序分拆數(shù) q 4 4C4- 1,4- 11,即 41111；各項 iq 4 求和,即得 4 的全部有序分拆數(shù)為 8,但此題中無 4分面值的郵票,故

45、不算 q 1 4,恰為 7 種方案；困難性：不能一次運算到位；【例 2.4.4】（各分項有限不重復(fù) ）如有 1 克的砝碼 3 枚,2 克的4 枚, 4 克的 2 枚,問能稱出多少種重量？各有幾種方案？（解）分析：無序分拆中處于不重復(fù)分拆（例 2.4.1）和無限重 復(fù)分拆（例 2.4.2）之間的有限重復(fù)分拆問題；母函數(shù)Gx1xx2x31x2x4x6x81x4x81x2x22x33 x43x54x64x75x85x95x105 x114 x124 x133 x143 x152 x162 x17x18x19 結(jié)果：共能稱出 19 種重量 例：稱 8 克重量（即 8 的分項為 1、2、4 的無序分拆）

46、8444224211222222211 擴展：如將 1 克的砝碼改為 4 枚,方案增加 841111221111 【例 2.4.5】（擴展） 在例 2.4.4 中,如砝碼可以放在天平的兩邊,但兩邊不能同時有同樣重量的砝碼,請給出問題的母函數(shù)；問要 秤出 2 克重的物體,有多少種不同的秤法？并給出每一種秤法；（解）分析：物體一邊的砝碼抵消了天平另一邊砝碼重量；Gx1111xx2x3x x3x2x11111x2x4x6x8x8x6x4x2111x4x8x8x4x11x102x92x83x73x64x53x44x33x24x134 x 3x 434 x 45 x 36 x 3x728 x 29 x

47、x10 x11x8x41x4x8x19x19 1317 x 132 x 163 x 結(jié)果：秤 2 克重物體的不同秤法有13 種；枚舉：用不同符號x、y、z 代表不同砝碼：Gxx3x2x11xx2x362y8y8y6y4y21y2y4yz8z414 z8 z2y64 z 4 zy xy 24 z x3y8z8（x2y68 z y88 z xy6zx2x2y 1 x2y2x24y4z4y2z4y8z8x2y6z8） （x2y48 z y68 z x2y88 z x24 z y624 z x2y4z 4y 8yx2y y x x2z4z4x2y8z8）x2y4z4 x3y8z 8例：稱 2 克的重量

48、,有 13 種方法（負數(shù)表示砝碼放在左邊,正數(shù)表示砝碼放在右邊）2 x 11 y 2 x x y2y - 1- 122 24z - 1- 14 24z - 24 x2y44z 11- 2- 24y6z4222- 4x2y4z41122- 4x x y2y48z - 1- 1- 2- 244 2y8z4-1-12222- 468z- 2- 2- 244 x 2 y 8 8z 11- 2- 2- 2- 244 x 2 y 8 z 8112222- 4- 4 反例：用上邊的母函數(shù)反映不出來的稱法（即天平兩邊放有 同一重量的砝碼,使得相同砝碼抵消）2- 112 - 1- 2122- 1- 214 -

49、4114 - 424 - 1- 1- 4224 - 2- 4224 - 1- 1- 2- 42224 - 1- 1- 2- 2- 2244 【例 2.4.6】投擲 3 個骰子,點數(shù)之和為 有多少種？骰子的情形如下：（1）3 個骰子相異；（2）3 個骰子相同；n（3n18）,其方案（解）（1）3 個骰子不同（ 3 個骰子分別為紅、蘭、黃色） ,問題等價于 n 的每個分項都有限制的特別有序nn1n2n33-分拆；即1ni6,i1 ,2,3由定理 2.4.1 知,相應(yīng)的母函數(shù)為Gxxx2x63x33x46x510 x61315x71421x825x 27 9 x 106 x 1631727x1125

50、x1221x15x10 x15x18n 的投擲方案個數(shù)就是xn的系數(shù)骰子的點數(shù)之和等于2n18；例如點數(shù)之和等于15 的方案有 10 種,即663636366654645564546465456555 原理：假設(shè)和式中的第一個加數(shù)為紅色骰子的點數(shù),后兩個加數(shù)分別為蘭色和黃色骰子的點數(shù),而這也恰好反映了15 的每個分項值不超過 6 的全部有序 3 分拆；（2）3 個骰子相同,問題等價于 殊性表達在對每個重量的值都限制在n 的特別無序 3-分拆；其特 16 之間,即nn1n2n313,且6n1n2n3利用 Ferrers 圖,問題又可轉(zhuǎn)化為求n 的最大分項等于項數(shù)不超過 6 的分拆數(shù),即求方程11

51、x10 ,2x23x33nx 1x2x36xx20 ,x,1的非負整數(shù)解的個數(shù)；母函數(shù)Gxx51xx2x3x4x21xx2x3x221x1x25x321xx2x221xx41xx2x3x1xx231x24x321xx221x23x331xx2x31xx2x21xx21xx21x22x341x1x2x35x 6x 6x106x111x36x 2x 3x 4x 5x 6x125x134x143x152x x17x18x 的系數(shù)（ 3n18）；其中點數(shù)之和等于n 的方案數(shù)就是例如點數(shù)之和等于10 的方案有 6 種,即10631622541 532442433 這也是 10 的每個分項值不超過6 的無

52、序 3 分拆數(shù)；習(xí)題二（1）基此題： 1,3,69,1315,18 （2）加強題： 2,5,1011 （3）提高題： 4,12,16,17 1.求以下數(shù)列的母函數(shù)（ n0,1,2, ）：nn0 xn（1）1nn；（2） n5 （3） nn1 ；（4） nn2 （解）（1）Gxn01nxnn0 xn1xnn（2）Gxn5xnn1xn4xnn0n0n0n0 xn114xn0 xn114x11x114x11214xx54x1x2（3）Gxn0nn1xn00 x2n2nn1xn2x2n2n1xnx2xn2n0n0 x2n0 xn2x21x2x2x231x（4）Gxn0nn2xnn0n1n2xnn0n1

53、xn0 xn2n0 xn111xx n 2 x n 1 1n 0 n 0 1 xx 2 x 11 x 1 x 1 x1 2x 31 1x 2 1 1x31 xx x3 22. 證明序列 Cn,n,Cn1,n,Cn2,n, 的母函數(shù)1為 n 11 x（證）已知集合 S e 1,e 2,e n 的 r-組合的母函數(shù)為1 n r 11 x nr 0 r x r所以序列 C n , n,C n ,1 n,C n 2 , n, 的母函數(shù)為G xnx 0 n 1x 1 n 2x 2 n rx rn n n nn rx rr 0 rn 1 r 1rxr 0 r11 x n 13. 設(shè) Se 1 , e 2

54、, e 3 , e 4,求序列 a n 的母函數(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 次；4（解）（1）G xx x 3x 5 4x2 4；1 x（2）G x1 x 3 x 6 x 9 413 4；1 x（3）G x1 x 1 x x 2x 3 21 x2；1 x（4）G xx x 3x 11x 2x 4x 51 x x 2x 3 2x 3 2 x 5

55、 x 6 x 7 x 82 x 13 x 15 x 16；1 x（5）G xx 10 x 11x 12 4x 404；1 x4. 投擲兩個骰子,點數(shù)之和為 r（2r12）,其組合數(shù)是多少？（解）相應(yīng)的母函數(shù)為Gx1xx2x5x2n1xx2x3x4x221xx2x3x231xx2x241xx25x26x2x32x42x53x63x73x8293x10 x11x12其中點數(shù)之和為 n 的方案數(shù)就是x 的系數(shù)；5.居民小區(qū)組織義務(wù)活動,號召每家出一到兩個人參與；設(shè)該小區(qū)共有 n 個家庭,現(xiàn)從中選出r 人,問：（1）設(shè)每個家庭都是3 口之家,有多少種不同的選法？當50 時,選法有多少種？（2）設(shè) n

56、個家庭中兩家有 4 口人,其余家庭都是 3 口人,有多少種選法？6.把 n 個相同的小球放入編號為1 ,2,m的 m 個盒子中,使得每個盒子內(nèi)的球數(shù)不小于它的編號數(shù)；已知 n m 2 m,求不同2的放球方法數(shù) g n , m；7. 紅、黃、藍三色的球各 8 個,從中取出 9 個,要求每種顏色的球至少一個,問有多少種不同的取法？（解）設(shè)從中取 r 個的不同取法有a 種,那么,數(shù)列a 的母函數(shù)為Gx2x2x2x37xx83997x1010 x16x242x33x488xxx3xxx3x8828x35x3x46x521x因此所求方案數(shù)為a 28 9a,8b,8c中取出 9 個元另法：原問題等價于從集

57、合S8素,且每個元素至少取一個；現(xiàn)在先把元素a、b、c 各取一個,然后再隨便選出 6 個,就問題轉(zhuǎn)變?yōu)閺募蟂 7a,7b ,7c中取出 6 個元素,且每個元素個數(shù)不限,求重復(fù)組合的方案數(shù)；又由于每個元素的個數(shù)大于 6,故從 S 中取 6 個元素與從集合 S a , b , c 中取出 6 個元素的組合數(shù)一樣多, 從而知不同的取法為8.C661C22838將幣值為 2 角的人民幣,兌換成硬幣（壹分、貳分和伍分）可有多少種兌換方法？（解）這是求正整數(shù)n 的分項只能等于1、2、5 的分拆數(shù)；設(shè) n 的分拆數(shù)為a ,就a 的母函數(shù)為x5x10Gx1xx21x2x4121xn1x2x22x33x43x

58、5n1x5x101 x 2 x 22 x 33 x 44 x 529 x 20所以,共有 a 2029 種兌換方法；9. 有 1 克重砝碼 2 枚,2 克重砝碼 3 枚,5 克重砝碼 3 枚,要求這 8 個砝碼只許放在天平的一端；能稱幾種重量的物品？有多少種不同的稱法？（解）設(shè)秤r 克重的物體有a 種秤法,那么數(shù)列 ra的母函數(shù)是Gx1xx21x2x4x61x5x10 x14綻開后得Gx112x22x23x32x42x5163x6173x7x2x8192x9x2x10213x113xx13x142x154x2x318x220 xx22因此,能稱 122 克共 22 種重量的物品,全部不同的稱法總數(shù)為G 13 4 448 10. 證明不定方程 x 1 x 2 x n r 的正整數(shù)解組的個數(shù)為 C r 1 n 1；（證）問題可以視為將 r 個相同的 1 放入 n 個盒子；由于將 ix之間的