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

1、1制作講授：王繼順2目錄（目錄（1）第第1章章 什么是組合數(shù)學(xué)什么是組合數(shù)學(xué)1.1引例引例1.2組合數(shù)學(xué)研究對(duì)象、內(nèi)容和方法組合數(shù)學(xué)研究對(duì)象、內(nèi)容和方法第第2章章 鴿巢原理鴿巢原理2.1 鴿巢原理：簡(jiǎn)單形式鴿巢原理：簡(jiǎn)單形式2.2 鴿巢原理：加強(qiáng)形式鴿巢原理：加強(qiáng)形式2.3 ramsey定理定理2.4 鴿巢原理與鴿巢原理與ramsey定理的應(yīng)用定理的應(yīng)用本章小結(jié) 習(xí)題第第3章章 排列與組合排列與組合3.1 兩個(gè)基本的計(jì)數(shù)原理兩個(gè)基本的計(jì)數(shù)原理3.2 集合的排列與組合集合的排列與組合3.3 多重集的排列與組合多重集的排列與組合本章小結(jié) 習(xí)題第四章第四章 二項(xiàng)式系數(shù)二項(xiàng)式系數(shù)4.1 二項(xiàng)式定理二項(xiàng)

2、式定理4.2組合恒等式組合恒等式4.3非降路徑問(wèn)題非降路徑問(wèn)題4.4牛頓二項(xiàng)式定理牛頓二項(xiàng)式定理4.5多項(xiàng)式定理多項(xiàng)式定理4.6 基本組合計(jì)數(shù)的應(yīng)用基本組合計(jì)數(shù)的應(yīng)用本章小結(jié) 習(xí)題第五章第五章 包含排斥原理包含排斥原理5.1 包含排斥原理包含排斥原理5.2 多重集的多重集的r-組合數(shù)組合數(shù)5.3錯(cuò)位排列錯(cuò)位排列5.4 有限制條件的排列問(wèn)題有限制條件的排列問(wèn)題5.5有禁區(qū)的排列問(wèn)題有禁區(qū)的排列問(wèn)題本章小結(jié) 習(xí)題目目 錄錄3目錄（目錄（2） 第六章第六章 遞推關(guān)系遞推關(guān)系6.1 fibonacci數(shù)列6.2 常系數(shù)線性齊次遞推關(guān)系的求解6.3 常系數(shù)線性非齊次遞推關(guān)系的求解6.4 用迭代和歸納法求

3、解遞推關(guān)系本章小結(jié) 習(xí)題第七章第七章 生成函數(shù)生成函數(shù)7.1生成函數(shù)的定義和性質(zhì)7.2多重集的r-組合數(shù)7.3正整數(shù)的劃分7.4指數(shù)生成函數(shù)與多重集的排列問(wèn)題7.5 catalan數(shù)和stiring數(shù)本章小結(jié) 習(xí)題 第八章第八章 polya定理定理8.1置換群中的共軛類與軌道8.2 polya定理的特殊形式及其應(yīng)用本章小結(jié) 習(xí)題*課程總結(jié)課程總結(jié)4第第7章章 生成函數(shù)生成函數(shù)本章重點(diǎn)介紹本章重點(diǎn)介紹生成函數(shù)（生成函數(shù)、指數(shù)生成函生成函數(shù)（生成函數(shù)、指數(shù)生成函數(shù)）的基本概念及其在排列組合中的應(yīng)用數(shù)）的基本概念及其在排列組合中的應(yīng)用 ： 生成函數(shù)的基本概念生成函數(shù)的基本概念 生成函數(shù)的基本運(yùn)算生成

4、函數(shù)的基本運(yùn)算 生成函數(shù)在排列、組合中的應(yīng)用生成函數(shù)在排列、組合中的應(yīng)用 整數(shù)拆分整數(shù)拆分 生成函數(shù)在組合恒等式中的應(yīng)用生成函數(shù)在組合恒等式中的應(yīng)用5第第7章章 生成函數(shù)生成函數(shù) 7.1生成函數(shù)的定義和性質(zhì)生成函數(shù)的定義和性質(zhì) 7.2多重集的多重集的r-組合數(shù)組合數(shù) 7.3正整數(shù)的劃分正整數(shù)的劃分 7.4指數(shù)生成函數(shù)與多重集的排列問(wèn)題指數(shù)生成函數(shù)與多重集的排列問(wèn)題 7.5catalan數(shù)和數(shù)和stiring第第7章章 生成函數(shù)生成函數(shù)67.1 生成函數(shù)概念4.1 生成函數(shù)的基本概念生成函數(shù)的基本概念定義定義 4.14.1.1 生成函數(shù)生成函數(shù) 注：注： f(x)是無(wú)窮級(jí)數(shù)，不管其收斂性；是無(wú)窮

5、級(jí)數(shù)，不管其收斂性； x為形式變?cè)瑸樾问阶冊(cè)?，f(x)為形式冪級(jí)數(shù)為形式冪級(jí)數(shù) ； 序列與生成函數(shù)一一對(duì)應(yīng)；序列與生成函數(shù)一一對(duì)應(yīng)； 生成函數(shù)是序列的另一表達(dá)形式；生成函數(shù)是序列的另一表達(dá)形式； 有限序列也可用生成函數(shù)表示；有限序列也可用生成函數(shù)表示； 可與二項(xiàng)式定理結(jié)合應(yīng)用可與二項(xiàng)式定理結(jié)合應(yīng)用 。給定一無(wú)窮序列給定一無(wú)窮序列(a0,a1,an,)(簡(jiǎn)記為簡(jiǎn)記為an)，稱函，稱函數(shù)數(shù) 為序列為序列an的生成函數(shù)（發(fā)生、普的生成函數(shù)（發(fā)生、普通母函數(shù)）通母函數(shù)） 。 0( )iiif xa x77.1 生成函數(shù)例17.1 生成函數(shù)的基本概念生成函數(shù)的基本概念例例 題題7.1.1 生成函數(shù)生成

6、函數(shù) 例例1、求序列求序列(c(n,0),c(n,1),c(n,2), c(n,n)的生成函數(shù)。的生成函數(shù)。 解：解：由定義由定義7.1及二項(xiàng)式定理的推論有及二項(xiàng)式定理的推論有 ( ).01(1)nnnnnf xxxn x87.1 生成函數(shù)例27.1 生成函數(shù)的基本概念生成函數(shù)的基本概念例例 題題7.1.1 生成函數(shù)生成函數(shù) 例例2、求序列求序列(c(n-1,0), -c(n,1), c(n+1,2), , (-1)kc(n+k-1,k), )的生成函數(shù)。的生成函數(shù)。 解：解：由定義由定義7.1及二項(xiàng)式定理的推論及二項(xiàng)式定理的推論3.10.2有有 200111( ).( 1).0121( 1)

7、(1)kkkkkknknnnnkf xxxxknk =xkn =xxk 97.1 生成函數(shù)例34.1 生成函數(shù)的基本概念生成函數(shù)的基本概念例例 題題4.1.1 生成函數(shù)生成函數(shù) 例例3、證明證明(1-4x)-1/2是序列是序列(c(0,0), c(2,1), c(4,2), , c(2n,n),)的生成函數(shù)。的生成函數(shù)。 證明：證明：由牛頓二項(xiàng)式定理有由牛頓二項(xiàng)式定理有 由定義知，由定義知，(1-4x)-1/2是序列是序列(c(0,0), c(2,1), c(4,2), , c(2n,n),)的生成函數(shù)。的生成函數(shù)。1 211111 2(14 )1( 4 )1 21 211 22 .1 211

8、( 4 )!41 3 . (21)12!2! 1 3 . (21)1! !2 4 . (2 )1 3 . (21kkkkkkkkkkkxxkk +xkk +xkkkxk kkk 11121)! !(2 )!211! !0242.012kkkkkkkxk kkk xxkk kk xxxk 107.1 生成函數(shù)例47.1 生成函數(shù)的基本概念生成函數(shù)的基本概念例例 題題7.1.1 生成函數(shù)生成函數(shù) 例例4、求序列求序列(0, 123, 234, n(n+1)(n+2),)的生成函數(shù)。的生成函數(shù)。 nnnnnnnnnxxn nxxn nnxxxxn nnxxxxn nnxxf xx0232343402

9、11.10.412(1)(1)6(1)(2)(1)6(1)(2)(1)01 2 32 3 4.(1)(2).6( )(1 由由牛牛頓頓二二項(xiàng)項(xiàng)式式定定理理的的推推論論，有有 將將上上式式兩兩端端同同時(shí)時(shí)微微分分兩兩次次得得 將將上上式式兩兩端端再再微微分分得得 兩兩邊邊同同乘乘解解以以 得得 因因此此 ：n nn4(0 1 2 3 2 3 4,., (1)(2),.) 是是序序列列 ，的的普普通通母母函函數(shù)數(shù)。117.1 指數(shù)生成函數(shù)概念7.1 生成函數(shù)的基本概念生成函數(shù)的基本概念定義定義 7.27.1.2 指數(shù)生成函數(shù)指數(shù)生成函數(shù) 注：注： fe(x)也是形式冪函數(shù)。也是形式冪函數(shù)。 經(jīng)常可

10、結(jié)合以下公式運(yùn)算：經(jīng)?？山Y(jié)合以下公式運(yùn)算：給定一無(wú)窮序列給定一無(wú)窮序列(a0,a1,an,)（簡(jiǎn)記為（簡(jiǎn)記為an），稱函），稱函數(shù)數(shù) 為序列為序列an的指數(shù)生成函數(shù)。的指數(shù)生成函數(shù)。 ieiixfxai0( )!nxnxxxen221.1!2! nxnxxxen21.( 1).1!2! nxxxxxeexn321sin.1!3!(21)!2127.1 指數(shù)生成函數(shù)例57.1 生成函數(shù)的基本概念生成函數(shù)的基本概念例例 題題7.1.2 指數(shù)生成函數(shù)指數(shù)生成函數(shù) 例例5、設(shè)設(shè)n是整數(shù)，求序列是整數(shù)，求序列(p(n,0), p(n,1), p(n,n)的指數(shù)生成函數(shù)的指數(shù)生成函數(shù)fe(x)。 解：解：

11、由定義由定義7.2及公式及公式p(n,r)=r!c(n,r),以及例以及例1的的結(jié)論，有結(jié)論，有 nennxxfxp np np n nnnnn xxn x( )( ,0)( ,1).( , )1!.01(1)137.1 指數(shù)生成函數(shù)例67.1 生成函數(shù)的基本概念生成函數(shù)的基本概念例例 題題7.1.2 指數(shù)生成函數(shù)指數(shù)生成函數(shù) 例例6、求序列求序列(p(0,0), p(2,1), p(4,2), p(2n,n),)的指數(shù)生成函數(shù)的指數(shù)生成函數(shù)fe(x)。 解：解：由定義由定義7.2及公式及公式p(n,r)=r!c(n,r)，以及例，以及例3的結(jié)論，有的結(jié)論，有 nenxxxfxppppn nn

12、n xxxn x221 2( )(0,0)(2,1)(4,2).(2 , ).1!2!0242.012(14 )147.1 指數(shù)生成函數(shù)例77.1 生成函數(shù)的基本概念生成函數(shù)的基本概念例例 題題7.1.2 指數(shù)生成函數(shù)指數(shù)生成函數(shù) 例例7、求序列求序列1,2,n,的指數(shù)生成函的指數(shù)生成函數(shù)數(shù)fe(x)。其中。其中是實(shí)數(shù)。是實(shí)數(shù)。 解：解：由定義由定義7.2，有，有 特別地：若特別地：若 =1，則序列，則序列(1,1,1,)的指數(shù)生成函數(shù)為的指數(shù)生成函數(shù)為ex 。nnxexxxfxen22( )1.1!2! 157.1 指數(shù)生成函數(shù)例87.1 生成函數(shù)的基本概念生成函數(shù)的基本概念例例 題題7.1

13、.2 指數(shù)生成函數(shù)指數(shù)生成函數(shù) 例例8、求序列求序列(1, 14, 147, 147(3n+1),)的指數(shù)生成函的指數(shù)生成函數(shù)。數(shù)。 解：解：由定義由定義7.2和二項(xiàng)式定理，有和二項(xiàng)式定理，有 nennnnnnnnnxxxfxnnnxnnxnnxnxnx2011143( )1(14)(147).147. (31).1!2!147. (31)!3147.33313!4441.13331( 3 )!41( 3 )3(13 ) 167.1 生成函數(shù)定理17.1 生成函數(shù)的基本概念生成函數(shù)的基本概念定理定理 7.17.1.2 指數(shù)生成函數(shù)指數(shù)生成函數(shù) 設(shè)設(shè)f(x)、fe(x)分別為序列分別為序列an的

14、普通、指數(shù)生的普通、指數(shù)生成函數(shù)，則成函數(shù)，則 xef xefsx ds0( )()解：解：由指數(shù)生成函數(shù)的定義由指數(shù)生成函數(shù)的定義7.2，有，有 將上式兩邊同乘以將上式兩邊同乘以e-s并從并從0到到 積分得積分得由分部積分法有由分部積分法有故故0()()!nennsxfsxan00000()!nnnsssnennnns xxefsx dse adsae s dsnn0!sne s dsn00()( )snennefsx dsa xf x17設(shè)設(shè)a(x), b(x), c(x)分別是序列分別是序列an, bn和和cn的生成的生成函數(shù)，則函數(shù)，則c(x)=a(x)+b(x)當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)ci=

15、ai+bi, (i=0,1,r,)c(x)=a(x)b(x)當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) , (i=0,1,r,)7.2 生成函數(shù)運(yùn)算定理27.2 生成函數(shù)的基本運(yùn)算生成函數(shù)的基本運(yùn)算定理定理 7.2iiki kkca b0187.2 生成函數(shù)運(yùn)算例17.2 生成函數(shù)的基本運(yùn)算生成函數(shù)的基本運(yùn)算例例 題題例例1、設(shè)設(shè)a(x)是序列是序列an的生成函數(shù)，則的生成函數(shù)，則a(x)/(1-x)是序列是序列a0,a0+a1,a0+a1 +an,的生成函數(shù)。的生成函數(shù)。nnnnxxxxxb xxcaacaaaacaaaaaaa xxa xb xa aaaa20001010101010010111.1-1 (1)(1

16、,1,.,1,.)( )1 (1),111.11.1.( ) (1)( )( )(,.,. 由由牛牛頓頓二二項(xiàng)項(xiàng)式式定定理理知知故故是是序序列列的的普普通通母母函函數(shù)數(shù)。令令根根據(jù)據(jù)上上述述定定理理有有故故是是明明：序序列列證證na ,.)的的普普通通母母函函數(shù)數(shù)。197.2 生成函數(shù)運(yùn)算例24.2 生成函數(shù)的基本運(yùn)算生成函數(shù)的基本運(yùn)算例例 題題例例2、求和求和 的值。的值。 rii2022210203203222231(0 ,1 ,.,.)(1-),1(1) 1(1) 1(0 ,1 ,.,.)(1)111iiiiiirrirxxxxxxixxxxxxi xxxxrxxcix先先求求序序列列的

17、的普普通通母母函函數(shù)數(shù)。由由牛牛頓頓二二項(xiàng)項(xiàng)式式定定理理知知將將上上式式兩兩端端對(duì)對(duì) 微微分分再再乘乘以以 得得（）再再將將上上式式兩兩端端對(duì)對(duì) 微微分分再再乘乘以以 得得（）故故（）是是序序列列的的普普通通母母函函數(shù)數(shù)。故故的的普普通通母母函函數(shù)數(shù)（）解解為為： 244400421114131.10 2(1-)(1)1(2)(1)(1) (1)(1)(21)213!3!6(1)(21)6iiiirrrixxxxxiixxxiixxxxrrrrr rr rrrrrrr rrci （） （）由由推推論論. . 知知故故的的展展開(kāi)開(kāi)式式中中的的系系數(shù)數(shù)為為（）故故207.2 生成函數(shù)運(yùn)算推論17.

18、2 生成函數(shù)的基本運(yùn)算生成函數(shù)的基本運(yùn)算六六個(gè)個(gè)推推論論推論推論7.2.1：0( )( )lkk lklbb xx a xakl若若，則則0110111101111012012.0,.,.( ).00.0.(.)( )lllkk lllllllllllbbbba babab xbb xbxb xbxa xa xx aa xa xx a x證證明明：217.2 生成函數(shù)運(yùn)算推論27.2 生成函數(shù)的基本運(yùn)算生成函數(shù)的基本運(yùn)算六六個(gè)個(gè)推推論論推論推論7.2.1：推論推論7.2.2：0( )( )lkk lklbb xx a xakl若若，則則10( )( )lklkk lkkbab xa xa xx

19、若若，則則20122121212121012110( ).1.1( ).1( )llllllllllllllkklkb xbb xb xaaxaxa xaxaxxa xaa xa xaxxa xa xx證證明明：227.2 生成函數(shù)運(yùn)算推論37.2 生成函數(shù)的基本運(yùn)算生成函數(shù)的基本運(yùn)算六六個(gè)個(gè)推推論論推論推論7.2.1：推論推論7.2.2：推論推論7.2.3：0( )( )lkk lklbb xx a xakl若若，則則10( )( )lklkk lkkbab xa xa xx若若，則則0( )( ) (1)kkiibab xa xx若若，則則見(jiàn)本節(jié)例見(jiàn)本節(jié)例1。237.2 生成函數(shù)運(yùn)算推論4

20、7.2 生成函數(shù)的基本運(yùn)算生成函數(shù)的基本運(yùn)算六六個(gè)個(gè)推推論論推論推論7.2.4：0( )(1)( ) (1)kkjkj kabab xaxa xx若若收收斂斂，則則20120012112022201( ). 1:.(1) : .(1) : .(1).( )(1)(1b xbb xb xbaaaax baaaaxbaaaab xax對(duì)對(duì)進(jìn)進(jìn)行行形形式式演演算算，有有 ： 證證明明22022122012.)(1.) (1.). =(1)(.) (1.) =(1)( ) (1)xa xxxa xxxax aa xa xxxaxa xx2401( )( )1xkkabb xa x dxkx若若，則則7

21、.2 生成函數(shù)運(yùn)算推論5、67.2 生成函數(shù)的基本運(yùn)算生成函數(shù)的基本運(yùn)算六六個(gè)個(gè)推推論論推論推論7.2.5：推論推論7.2.4：推論推論7.2.6：0( )(1)( ) (1)kkjkj kabab xaxa xx若若收收斂斂，則則( )( )kkbkab xxa x若若，則則25設(shè)設(shè)a(x), b(x), c(x)分別是序列分別是序列an, bn和和cn的指的指數(shù)生成函數(shù)，則數(shù)生成函數(shù)，則c(x)=a(x)+b(x)當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)ci=ai+bi, (i=0,1,r,)c(x)=a(x)b(x)當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) , (i=0,1,r,)7.2 生成函數(shù)定理37.2 生成函數(shù)的基本運(yùn)算生成函

22、數(shù)的基本運(yùn)算定理定理 7.3 0iiki kkica bk26276.5 母函數(shù)在遞推關(guān)系中的應(yīng)用6.5 母函數(shù)在遞推關(guān)系中的應(yīng)用母函數(shù)在遞推關(guān)系中的應(yīng)用 母函數(shù)法是求解遞推關(guān)系的一種重要方法，不僅可母函數(shù)法是求解遞推關(guān)系的一種重要方法，不僅可以求解常系數(shù)線性（非）齊次遞推關(guān)系，也可以求解非以求解常系數(shù)線性（非）齊次遞推關(guān)系，也可以求解非線性、非常系數(shù)的遞推關(guān)系線性、非常系數(shù)的遞推關(guān)系 。 求解的求解的方法和步驟方法和步驟為：為： 用用f(x)表示序列表示序列an的普通母函數(shù)；的普通母函數(shù)；利用遞推關(guān)系利用遞推關(guān)系an的表達(dá)式代入母函數(shù)的右端，或采用的表達(dá)式代入母函數(shù)的右端，或采用多項(xiàng)式形式算

23、法，轉(zhuǎn)化為關(guān)于多項(xiàng)式形式算法，轉(zhuǎn)化為關(guān)于f(x)的方程的方程g(f(x)=0；1. 解出解出f(x)再展開(kāi)成冪級(jí)數(shù)，即可求得再展開(kāi)成冪級(jí)數(shù)，即可求得an的初等表達(dá)式。的初等表達(dá)式。286.5 母函數(shù)的應(yīng)用例1-16.5 母函數(shù)在遞推關(guān)系中的應(yīng)用母函數(shù)在遞推關(guān)系中的應(yīng)用例例 題題例例1、求遞歸關(guān)系求遞歸關(guān)系 nnnfffnff1201(2)1,1nnnnnnnnnnnnnnnnnnnnnnnf xf xf ffffff xf xff xffxff xxfxxfxff xxf xfxf xxf xx f xf x01012011221220112222010002( )(,.,.)( )( )()

24、1( )( )1( )1 設(shè)設(shè)為為序序列列的的普普通通母母函函數(shù)數(shù)，并并將將式式代代入入有有解解之之得得解解：xxx xxx221215151-0,22而而有有兩兩個(gè)個(gè)根根296.5 母函數(shù)的應(yīng)用例1-26.5 母函數(shù)在遞推關(guān)系中的應(yīng)用母函數(shù)在遞推關(guān)系中的應(yīng)用例例 題題例例1、求遞歸關(guān)系求遞歸關(guān)系 nnnfffnff1201(2)1,12121212121211220011120111111211( )1(1)(1)1115(15),2 552 5555( )1155555151525nniinnninnnnnnabf xxxx xx xx xx xxxabxxf xx xx xxx xxx

25、xxxxfxx故故用用待待定定系系數(shù)數(shù)法法解解之之得得故故（） （）306.5 母函數(shù)的應(yīng)用例26.5 母函數(shù)在遞推關(guān)系中的應(yīng)用母函數(shù)在遞推關(guān)系中的應(yīng)用例例 題題例例2、求遞歸關(guān)系求遞歸關(guān)系 112(1)(2)2nnaannannnnnnnnnnnnnnnnnnnf xa xa aaaanf xf xa xanxxxaxxnxxxxa xxxxf xxxxfnxxx1211112122122222102( )(,.,.)2(1)( )( )2(1)22(11)2222( )(1)22( )1(1)設(shè)設(shè)為為序序列列的的普普通通母母函函數(shù)數(shù)，并并將將式式代代入入有有解解之之得得解解： kkkkkk

26、nkknnkxxxxxknxxxnann32111200) 22 222 122 2 12222因因此此316.5 母函數(shù)的應(yīng)用例3-16.5 母函數(shù)在遞推關(guān)系中的應(yīng)用母函數(shù)在遞推關(guān)系中的應(yīng)用例例 題題例例3、求遞歸關(guān)系求遞歸關(guān)系 nnkn kkaaanaa1112(2)1,1nnnnnnnnnkn kknnnnkn knnnknnf xa xa aafxa xa xa aa axa axa axa xa xa x1122211223112211112121( )(,.,.)( ) . 這這是是一一個(gè)個(gè)非非線線性性的的遞遞推推解解：關(guān)關(guān)系系，設(shè)設(shè)為為序序列列的的普普通通母母函函數(shù)數(shù)，則則f x

27、xxxfxfxfffxxf xfx12112( )114114( ),( )22(0)0(0)0( )114 ( )( )2解解之之得得因因，而而，故故舍舍去去，有有326.5 母函數(shù)的應(yīng)用例3-26.5 母函數(shù)在遞推關(guān)系中的應(yīng)用母函數(shù)在遞推關(guān)系中的應(yīng)用例例 題題例例3、求遞歸關(guān)系求遞歸關(guān)系 nnkn kkaaanaa1112(2)1,1注：注：通常，稱滿足上述遞推關(guān)系的序列通常，稱滿足上述遞推關(guān)系的序列(a1,a2,an,)為為catalan序列，稱序列中的數(shù)序列，稱序列中的數(shù) 為為catalan數(shù)。數(shù)。這個(gè)數(shù)很重要，它在各種不同的范圍里經(jīng)常出現(xiàn)，許多有意這個(gè)數(shù)很重要，它在各種不同的范圍里經(jīng)

28、常出現(xiàn)，許多有意義的計(jì)數(shù)問(wèn)題都與這個(gè)數(shù)有關(guān)。義的計(jì)數(shù)問(wèn)題都與這個(gè)數(shù)有關(guān)。kkkknnnnnnnnnkzzzkkzxnxxnnnxnnxnf xxnnnann1211121111( 1)22110 5 | |1,11124 ,( 1)22141( 4 )1222211114122 ( )12122 1 根根據(jù)據(jù)推推論論 .有有令令有有故故因因此此nnann1221336.5 母函數(shù)的應(yīng)用例4-16.5 母函數(shù)在遞推關(guān)系中的應(yīng)用母函數(shù)在遞推關(guān)系中的應(yīng)用例例 題題例例4、求遞歸關(guān)系求遞歸關(guān)系 nnnnanaa na a-1-201( -1)( -2)2(2)0,1nnnnnnnnnnnnnf xa

29、xa aaf xfxna xxxfxna xaaxfxf xna xx xfxf x012111012( )(,.,.)( ) ( ) ( )0,1 ( )( )(1) ( )( )這這是是一一個(gè)個(gè)非非常常系系數(shù)數(shù)的的線線性性齊齊次次遞遞推推關(guān)關(guān)系系，設(shè)設(shè)為為序序列列的的普普通通母母函函數(shù)數(shù)。將將微微分分有有將將上上式式兩兩端端同同乘乘以以 有有因因此此（注注意意初初值值條條件件）有有解解：nnnnnnnnnnnnnnnnnna xnaxx f xa xaxx xfxxxf xnanaax11222220222122(1)(2) 2( )22()( ) (12) ( )(1)(2)20 而而將

30、將以以上上三三個(gè)個(gè)式式子子兩兩端端分分別別相相加加，并并由由遞遞推推關(guān)關(guān)系系得得346.5 母函數(shù)的應(yīng)用例4-26.5 母函數(shù)在遞推關(guān)系中的應(yīng)用母函數(shù)在遞推關(guān)系中的應(yīng)用例例 題題例例4、求遞歸關(guān)系求遞歸關(guān)系 nnnnanaa na a-1-201( -1)( -2)2(2)0,1xnnxnnnnnxnn innnnnnninxxfxxxf xxf xcexxxexnxnnxxf xcexcxnxcixnnia222200022000022()( )(12) ( )( )(1)( 2 )( 2)!(1)( )(1)( 2)( 2)!()! 故故有有解解此此微微分分方方程程得得而而，因因此此有有故

31、故n inin inniciniacaini010( 2)()!11( 2)()!根根據(jù)據(jù)初初值值條條件件，可可得得，故故有有356.5 母函數(shù)的應(yīng)用例5-16.5 母函數(shù)在遞推關(guān)系中的應(yīng)用母函數(shù)在遞推關(guān)系中的應(yīng)用例例 題題例例5、求求n位十進(jìn)制正整數(shù)中出現(xiàn)偶數(shù)位十進(jìn)制正整數(shù)中出現(xiàn)偶數(shù)個(gè)個(gè)5的數(shù)的個(gè)數(shù)。的數(shù)的個(gè)數(shù)。解解i：令令an=n位十進(jìn)制數(shù)中出現(xiàn)偶數(shù)個(gè)位十進(jìn)制數(shù)中出現(xiàn)偶數(shù)個(gè)5的數(shù)的個(gè)數(shù)的數(shù)的個(gè)數(shù) bn=n位十進(jìn)制數(shù)中出現(xiàn)奇數(shù)個(gè)位十進(jìn)制數(shù)中出現(xiàn)奇數(shù)個(gè)5的數(shù)的個(gè)數(shù)的數(shù)的個(gè)數(shù)建立遞推關(guān)系如下建立遞推關(guān)系如下 這是關(guān)于序列這是關(guān)于序列an和和 bn的聯(lián)立關(guān)系。的聯(lián)立關(guān)系。設(shè)序列設(shè)序列an,bn的普

32、通母函數(shù)分別為的普通母函數(shù)分別為a(x),b(x)。其中。其中nnnnnnaabbbaab111111998,1a xaa xa x b xbb xb x a xa a x a x xa x a xa x xb x b x b x x a x221231232123212212( ).,( ).( ).9( )99.)( ).(19 ) (進(jìn)進(jìn)行行計(jì)計(jì)算算如如下下xb x x b xxa x)( )8(19 ) ( )( )1同同理理可可得得366.5 母函數(shù)的應(yīng)用例5-26.5 母函數(shù)在遞推關(guān)系中的應(yīng)用母函數(shù)在遞推關(guān)系中的應(yīng)用例例 題題例例5、求求n位十進(jìn)制正整數(shù)中出現(xiàn)偶數(shù)位十進(jìn)制正整數(shù)中出

33、現(xiàn)偶數(shù)個(gè)個(gè)5的數(shù)的個(gè)數(shù)。的數(shù)的個(gè)數(shù)。a xb xx a xxb xx b xxa xxxdxxxxxxa xxxxxxxxb xxxxxxa xxx( )( )(19 ) ( )( )8(19 ) ( )( )119(18 )(1 10 )1917188( )119(18 )(1 10 )(18 )(1 10 )11198( )1(18 )(1 10 )(18 )(1 10 )179( )2 181 10故故可可得得關(guān)關(guān)于于普普通通母母函函數(shù)數(shù)和和聯(lián)聯(lián)立立方方程程組組nnnnnnnxa01(7 89 10 )21(7 89 10 )2 376.5 母函數(shù)的應(yīng)用例5-36.5 母函數(shù)在遞推關(guān)系中

34、的應(yīng)用母函數(shù)在遞推關(guān)系中的應(yīng)用例例 題題例例5、求求n位十進(jìn)制正整數(shù)中出現(xiàn)偶數(shù)位十進(jìn)制正整數(shù)中出現(xiàn)偶數(shù)個(gè)個(gè)5的數(shù)的個(gè)數(shù)。的數(shù)的個(gè)數(shù)。解解ii： n-1位的十進(jìn)制數(shù)的全體共位的十進(jìn)制數(shù)的全體共 9 10n-2, 從中去掉含有偶數(shù)個(gè)從中去掉含有偶數(shù)個(gè)5的數(shù)，余下的便是的數(shù)，余下的便是n-1位中含有奇數(shù)個(gè)位中含有奇數(shù)個(gè)5的數(shù)。故有：的數(shù)。故有：nnnnnnbaaaaa xaa xa xxa xa xa xx a xaaxaax2112112123212221329 1089 108 ( ) . ) 8( ) 88. (18 ) ( )8(8)(8). (1 ，結(jié)結(jié)合合上上述述遞遞推推關(guān)關(guān)系系建建立立

35、新新的的遞遞推推關(guān)關(guān)系系進(jìn)進(jìn)行行計(jì)計(jì)算算如如下下nnnnnnnxxx a xxxxxxa xxxxa2098718 ) ( )899 10.81 101 108711( )(7 89 10 )(18 )(1 10 )21 (7 89 10 )2 386.5 母函數(shù)的應(yīng)用例66.5 母函數(shù)在遞推關(guān)系中的應(yīng)用母函數(shù)在遞推關(guān)系中的應(yīng)用例例 題題例例6、求遞歸關(guān)系（求遞歸關(guān)系（hanoi塔）塔） 1121(2)1nnaana解：解：設(shè)序列設(shè)序列an的普通母函數(shù)為的普通母函數(shù)為a xa xa xa xa xa xa xa xxa xa xa xx a xa xaaxaa23123231232312212

36、132 ( ). ( ) . 2( ) 22. (1-2 ) ( )(2)(2)進(jìn)進(jìn)行行計(jì)計(jì)算算如如下下）nnnnna xxxxxx a xxxxxxxxxa3230( )(12 )1. (1-2 ) ( ).111(21)(1)12 21397.3 排列組合概述7.3 在排列組合中的應(yīng)用在排列組合中的應(yīng)用 生成函數(shù)有著極其廣泛的應(yīng)用，從本節(jié)開(kāi)始介紹生生成函數(shù)有著極其廣泛的應(yīng)用，從本節(jié)開(kāi)始介紹生成函數(shù)在某些組合數(shù)學(xué)的問(wèn)題中的應(yīng)用。成函數(shù)在某些組合數(shù)學(xué)的問(wèn)題中的應(yīng)用。 本節(jié)介紹生成函數(shù)在本節(jié)介紹生成函數(shù)在組合組合中的應(yīng)用和指數(shù)生成函數(shù)中的應(yīng)用和指數(shù)生成函數(shù)在在排列排列中的應(yīng)用，主要是計(jì)數(shù)問(wèn)題，也

37、有部分方案方法中的應(yīng)用，主要是計(jì)數(shù)問(wèn)題，也有部分方案方法問(wèn)題。問(wèn)題。 考慮三個(gè)不同的物體考慮三個(gè)不同的物體a、b、c的選取方法。的選取方法。 如果對(duì)選取方法的個(gè)數(shù)感興趣，而不是對(duì)不同的選如果對(duì)選取方法的個(gè)數(shù)感興趣，而不是對(duì)不同的選取方法感興趣，則可令取方法感興趣，則可令a=b=c=1，有，有 23 (1)(1)(1)1()()()axbxcxabc xabbcca xabc x 323 (1)(1)(1)(1)133xxxxxxx 407.3 組合應(yīng)用例17.3 在排列組合中的應(yīng)用在排列組合中的應(yīng)用7.3.1 在組合中的應(yīng)用在組合中的應(yīng)用 例例 題題例例1、有紅球兩只，白球、黃球各一只，試求有

38、紅球兩只，白球、黃球各一只，試求有多少種不同的組合方案。有多少種不同的組合方案。隨機(jī)組合隨機(jī)組合 解：解：設(shè)設(shè)r, w, y分別代表紅球，白球和黃球。分別代表紅球，白球和黃球。由此可見(jiàn)，除一個(gè)球也不取的情況外，有：由此可見(jiàn)，除一個(gè)球也不取的情況外，有：(a)取一個(gè)球的組合取一個(gè)球的組合數(shù)為三，即分別取紅，白，黃，三種；數(shù)為三，即分別取紅，白，黃，三種；(b)取兩個(gè)球的組合數(shù)為取兩個(gè)球的組合數(shù)為四，即兩個(gè)紅的，一紅一黃，一紅一白，一白一黃；四，即兩個(gè)紅的，一紅一黃，一紅一白，一白一黃；(c)取三個(gè)取三個(gè)球的組合數(shù)為三，即兩紅一黃，兩紅一白，一紅一黃一白；球的組合數(shù)為三，即兩紅一黃，兩紅一白，一紅

39、一黃一白；(d)取四個(gè)球的組合數(shù)為一，即兩紅一黃一白。取四個(gè)球的組合數(shù)為一，即兩紅一黃一白。令取令取i個(gè)球的組合數(shù)為個(gè)球的組合數(shù)為ai，則序列，則序列a0,a1,a2,a3,a4的生成函數(shù)為的生成函數(shù)為故共有故共有1+3+4+3+1=12（或（或322=12）種組合方式。）種組合方式。22222222234(1)(1)(1)(1)(1)1()()()( )(1)(1)1343rrwyrrywywrywrryrwywr yr wrywr ywf xxxxxxxx 417.3 組合應(yīng)用例27.3 在排列組合中的應(yīng)用在排列組合中的應(yīng)用7.3.1 在組合中的應(yīng)用在組合中的應(yīng)用 例例 題題例例2、n個(gè)完

40、全一樣的球放到個(gè)完全一樣的球放到m個(gè)有標(biāo)志的盒個(gè)有標(biāo)志的盒子中，不允許有空盒，問(wèn)有多少種不同的方子中，不允許有空盒，問(wèn)有多少種不同的方案？其中案？其中nm 重復(fù)組合重復(fù)組合 解：解：由于不允許有空盒，令由于不允許有空盒，令n個(gè)球放到個(gè)球放到m個(gè)有標(biāo)志的盒子的方案?jìng)€(gè)有標(biāo)志的盒子的方案數(shù)為數(shù)為an，序列，序列an對(duì)應(yīng)的生成函數(shù)為對(duì)應(yīng)的生成函數(shù)為f(x)。則。則222000( )(.)(.).(.)1 (1)11 11 1111mmnmnn mnnn mnnn mnnf xxxxxxxxmnxxnxmnnxxnnmnnxxmmnam故故427.3 組合應(yīng)用例37.3 在排列組合中的應(yīng)用在排列組合中的

41、應(yīng)用7.3.1 在組合中的應(yīng)用在組合中的應(yīng)用 例例 題題例例3、某單位有某單位有8個(gè)男同志，個(gè)男同志，5個(gè)女同志，現(xiàn)要個(gè)女同志，現(xiàn)要組織一個(gè)由數(shù)目為偶數(shù)的男同志，和數(shù)目不少組織一個(gè)由數(shù)目為偶數(shù)的男同志，和數(shù)目不少于于2的女同志組成的小組，試求有多少種組成的女同志組成的小組，試求有多少種組成方式。方式。隨機(jī)組合隨機(jī)組合 解：解：令令an為從為從8位男同志中抽取出位男同志中抽取出n個(gè)的允許組合數(shù)。由于要男個(gè)的允許組合數(shù)。由于要男同志的數(shù)目必須是偶數(shù)，故序列同志的數(shù)目必須是偶數(shù)，故序列an對(duì)應(yīng)的生成函數(shù)為對(duì)應(yīng)的生成函數(shù)為f(x)=(1+x)8+(1-x)8/2類似女同志的允許組合數(shù)對(duì)應(yīng)的生成函數(shù)為類

42、似女同志的允許組合數(shù)對(duì)應(yīng)的生成函數(shù)為g(x)=(1+x)5-(1+5x)令令cn為為符合要求的為為符合要求的n個(gè)人組成的小組的數(shù)目，個(gè)人組成的小組的數(shù)目，由乘法法則，由乘法法則，序序列列cn對(duì)應(yīng)的生成函數(shù)為對(duì)應(yīng)的生成函數(shù)為h(x)=f(x)g(x)=(1+x)8+(1-x)8(1+x)5-(1+5x)/2故總的組成方式數(shù)目故總的組成方式數(shù)目為為12826=3328。437.3 組合應(yīng)用例47.3 在排列組合中的應(yīng)用在排列組合中的應(yīng)用7.3.1 在組合中的應(yīng)用在組合中的應(yīng)用 例例 題題例例4、證明從證明從n個(gè)不同的物體中允許重個(gè)不同的物體中允許重復(fù) 地 選 取復(fù) 地 選 取 r 個(gè) 物 體 的

43、方 式 數(shù) 為個(gè) 物 體 的 方 式 數(shù) 為f(n,r)=c(n+r-1,r) 。 證明：證明：設(shè)設(shè)ar表示從表示從n個(gè)不同的物體中允許重復(fù)的選取個(gè)不同的物體中允許重復(fù)的選取r個(gè)物體的個(gè)物體的方式數(shù)。序列方式數(shù)。序列ar的生成函數(shù)為的生成函數(shù)為20001( )(1.)(1)1(1).(1)()!(1).(1)!11( , )nnnrrrrrrrf xxxxxnnnrxrn nnrxrnrxrnraf n rr 故故447.3 組合應(yīng)用例57.3 在排列組合中的應(yīng)用在排列組合中的應(yīng)用7.3.1 在組合中的應(yīng)用在組合中的應(yīng)用 例例 題題例例5、求從求從n個(gè)不同物體中允許重復(fù)地選取個(gè)不同物體中允許重

44、復(fù)地選取r個(gè)個(gè)物體，但每個(gè)物體出現(xiàn)偶數(shù)次的方式數(shù)。物體，但每個(gè)物體出現(xiàn)偶數(shù)次的方式數(shù)。 解：解：設(shè)設(shè)ar為所求的方式數(shù)。由于每個(gè)物體出現(xiàn)偶數(shù)次，故可用為所求的方式數(shù)。由于每個(gè)物體出現(xiàn)偶數(shù)次，故可用因子因子(1+x2+x4+)示某一物體可以不選，或選取示某一物體可以不選，或選取2次，或選取次，或選取4次，次，。因此序列。因此序列ar的生成函數(shù)為的生成函數(shù)為 24222462202( )(1.)1(1)11211.12311nnnrrrrf xxxxxnnnnrxxxxrnrxrnrar 故故457.3 組合應(yīng)用例67.3 在排列組合中的應(yīng)用在排列組合中的應(yīng)用7.3.1 在組合中的應(yīng)用在組合中的應(yīng)

45、用 例例 題題例例6、在一個(gè)書(shū)架上共有在一個(gè)書(shū)架上共有16本書(shū)，其中本書(shū)，其中4本是高等數(shù)學(xué)，本是高等數(shù)學(xué)，3本是普通物理，本是普通物理，4本是本是數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)，5本是離散數(shù)學(xué)。求從中選取本是離散數(shù)學(xué)。求從中選取r本數(shù)的方式數(shù)，其中本數(shù)的方式數(shù)，其中r=12。解：解：這實(shí)際上是求重集這實(shí)際上是求重集4*m,3*p,4*s,5*d的的12組合數(shù)。組合數(shù)。設(shè)設(shè)ar是選取是選取r本書(shū)的方式數(shù)。由于高等數(shù)學(xué)最多只能選取本書(shū)的方式數(shù)。由于高等數(shù)學(xué)最多只能選取4本，本，普通物理最多只能選取普通物理最多只能選取3本，數(shù)據(jù)結(jié)構(gòu)最多只能選取本，數(shù)據(jù)結(jié)構(gòu)最多只能選取4本，離散本，離散數(shù)學(xué)最多只能選取數(shù)學(xué)最多

46、只能選取5本，故序列本，故序列ar的生成函數(shù)為的生成函數(shù)為取取f(x)展開(kāi)式中展開(kāi)式中xr的系數(shù)即為所求的方式數(shù)。當(dāng)?shù)南禂?shù)即為所求的方式數(shù)。當(dāng)r=12時(shí)，時(shí)，x12的系的系數(shù)為數(shù)為34，即，即 a12=34。2342323423452345678910111213141516( )(1)(1)(1)(1)14102034506576807665503420104f xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 467.3 組合應(yīng)用例77.3 在排列組合中的應(yīng)用在排列組合中的應(yīng)用4.3.1 在組合中的應(yīng)用在組合中的應(yīng)用 例例 題題例例7、現(xiàn)有現(xiàn)有2n個(gè)個(gè)a，2n個(gè)個(gè)b，2n

47、個(gè)個(gè)c，求從它們，求從它們之中選出之中選出3n個(gè)字生成的不同的方式數(shù)。個(gè)字生成的不同的方式數(shù)。解：解：這個(gè)問(wèn)題實(shí)際上是求重集這個(gè)問(wèn)題實(shí)際上是求重集2n*a,2n*b,2n*c的的3n組合數(shù)。組合數(shù)。設(shè)設(shè)ar為所求的方式數(shù)。則序列為所求的方式數(shù)。則序列ar的生成函數(shù)為的生成函數(shù)為2233213210214263021426303( )(1.)1( 3)( 4).( 31)11()1!3 4 . (2)1 331!21 332321322nnnkknnnkknnnkknf xxxxxkxxxkkxxxxkkxxxxnnxr 顯顯然然，上上式式中中的的系系數(shù)數(shù)為為故故33213322nnnna時(shí)時(shí)，

48、有有477.3 排列應(yīng)用例87.3 在排列組合中的應(yīng)用在排列組合中的應(yīng)用4.3.2 在排列中的應(yīng)用在排列中的應(yīng)用 例例 題題例例8、由由1,2,3,4四個(gè)數(shù)字組成的五位數(shù)中，四個(gè)數(shù)字組成的五位數(shù)中，要求數(shù)要求數(shù)1出現(xiàn)次數(shù)不超過(guò)出現(xiàn)次數(shù)不超過(guò)2次，但不能不出現(xiàn)；次，但不能不出現(xiàn)；2出現(xiàn)不超過(guò)出現(xiàn)不超過(guò)1次；次；3出現(xiàn)次數(shù)可達(dá)出現(xiàn)次數(shù)可達(dá)3次，也可次，也可不出現(xiàn)；不出現(xiàn)；4出現(xiàn)次數(shù)為偶數(shù)。求滿足上述條出現(xiàn)次數(shù)為偶數(shù)。求滿足上述條件的數(shù)的個(gè)數(shù)。件的數(shù)的個(gè)數(shù)。容斥原理容斥原理 解：解：設(shè)滿足條件的設(shè)滿足條件的r位數(shù)的個(gè)數(shù)為位數(shù)的個(gè)數(shù)為ar，序列，序列ar的指數(shù)母函數(shù)為的指數(shù)母函數(shù)為由此可見(jiàn)滿足條件的由

49、此可見(jiàn)滿足條件的5位數(shù)位數(shù)ar=215個(gè)。個(gè)。exxxxxxxfx xxx xxxxxxxx xxxxxx xxxx 22324672323452345678910( )()(1)(1)(1)1!2!1!2!3!2!4!31271()(1)223248481445843433232448171114828848288xxxxxx xxxx 2345678910518642156451!2!3!4!5!6!17851407650126007!8!9!10!487.3 排列應(yīng)用例97.3 在排列組合中的應(yīng)用在排列組合中的應(yīng)用4.3.2 在排列中的應(yīng)用在排列中的應(yīng)用 例例 題題例例9、求求1,3,5

50、,7,9五個(gè)數(shù)字組成的五個(gè)數(shù)字組成的n位數(shù)的個(gè)位數(shù)的個(gè)數(shù)，要求其中數(shù)，要求其中3,7出現(xiàn)的次數(shù)為偶數(shù)，其他出現(xiàn)的次數(shù)為偶數(shù)，其他1,5,9出現(xiàn)的次數(shù)不加限制出現(xiàn)的次數(shù)不加限制。 解：解：設(shè)滿足上述條件的設(shè)滿足上述條件的r位數(shù)的個(gè)數(shù)為位數(shù)的個(gè)數(shù)為ar，序列，序列ar的指數(shù)母函數(shù)為的指數(shù)母函數(shù)為exxxxxxxxxxxxennnnnnnnxxxxfx xxxexxx eefx eeeeeeeeexx xnnn24232323242322353000( )(1.) (1.)2!4!2!3!1.2!3!11.()2!4!2111( )()(2)(2)444153(24! nnnnnnnxn a01)(

51、52 31)4!1(52 31)4 497.3 排列應(yīng)用例107.3 在排列組合中的應(yīng)用在排列組合中的應(yīng)用7.3.2 在排列中的應(yīng)用在排列中的應(yīng)用 例例 題題例例10、證明從證明從n個(gè)不同的物體中允許重復(fù)地個(gè)不同的物體中允許重復(fù)地選取選取r個(gè)物體的排列數(shù)為個(gè)物體的排列數(shù)為nr。 證明：證明：這個(gè)問(wèn)題實(shí)際上是證明重集這個(gè)問(wèn)題實(shí)際上是證明重集b=*b1,*b2,*bn的的r排列數(shù)為排列數(shù)為nr。設(shè)。設(shè)ar為所求的排列數(shù)。則序列為所求的排列數(shù)。則序列ar的指數(shù)母函數(shù)為的指數(shù)母函數(shù)為rnerxnnxrrrrxxfxxrx eenr an20( )(1.)2!()!故故有有507.3 排列應(yīng)用例114.

52、3 在排列組合中的應(yīng)用在排列組合中的應(yīng)用4.3.2 在排列中的應(yīng)用在排列中的應(yīng)用 例例 題題例例11、用紅、白、綠三種顏色給用紅、白、綠三種顏色給1n棋盤(pán)棋盤(pán)中的正方形著色，要求偶數(shù)個(gè)正方形著紅中的正方形著色，要求偶數(shù)個(gè)正方形著紅色，而著白色和綠色的正方形個(gè)數(shù)不加限色，而著白色和綠色的正方形個(gè)數(shù)不加限制，求不同的著色方式數(shù)。制，求不同的著色方式數(shù)。 證明：證明：若用若用r,w和和g分別表示紅、白和綠三種顏色，則該問(wèn)題分別表示紅、白和綠三種顏色，則該問(wèn)題實(shí)際上是求重集實(shí)際上是求重集b=*r,*w,*g的的n排列數(shù)，其中要求排列數(shù)，其中要求r出出現(xiàn)偶數(shù)次。設(shè)現(xiàn)偶數(shù)次。設(shè)an為所求的排列數(shù)。則序列為

53、所求的排列數(shù)。則序列an的指數(shù)母函數(shù)為的指數(shù)母函數(shù)為exxxxxnnnnnnnnnnxxxfxx eeeeexx nnx n a242223000( )(1.)(1.)2!4!2!11()()22132!1312!1312故故有有517.3 排列應(yīng)用例127.3 在排列組合中的應(yīng)用在排列組合中的應(yīng)用7.3.2 在排列中的應(yīng)用在排列中的應(yīng)用 例例 題題例例12、在所有的在所有的n位數(shù)中，包含數(shù)字位數(shù)中，包含數(shù)字3,8,9，但不包含數(shù)字但不包含數(shù)字0,4的數(shù)有多少？的數(shù)有多少？ 解：解：這個(gè)問(wèn)題實(shí)際上是求重集這個(gè)問(wèn)題實(shí)際上是求重集b=*1,*2,*3,*5,*6,*7,*8, *9的的n排列數(shù)，其

54、中要排列數(shù)，其中要求求3,8,9至少出現(xiàn)一次，而其他的數(shù)不加限制。設(shè)符合題意的數(shù)至少出現(xiàn)一次，而其他的數(shù)不加限制。設(shè)符合題意的數(shù)有有an個(gè)。則序列個(gè)。則序列an的指數(shù)生成函數(shù)為的指數(shù)生成函數(shù)為exxxxxxxxxxnnnnnnnnnnnxxxfxxx eeeeee eeeex n a352323532587650( ).1.2!3!2!(1)(331)3383 73 65!83 73 65 故故有有527.3 排列應(yīng)用例134.3 在排列組合中的應(yīng)用在排列組合中的應(yīng)用4.3.2 在排列中的應(yīng)用在排列中的應(yīng)用 例例 題題例例13、求求1,2,3,4,5五個(gè)數(shù)字組成的五個(gè)數(shù)字組成的r位數(shù)位數(shù)的個(gè)數(shù)

55、，要求其中的個(gè)數(shù)，要求其中1出現(xiàn)的次數(shù)與出現(xiàn)的次數(shù)與2出現(xiàn)出現(xiàn)的次數(shù)的和必須是偶數(shù)。的次數(shù)的和必須是偶數(shù)。 解：解：設(shè)設(shè)an為符合題意的個(gè)數(shù)。由于為符合題意的個(gè)數(shù)。由于1出現(xiàn)的次數(shù)與出現(xiàn)的次數(shù)與2出現(xiàn)的次數(shù)出現(xiàn)的次數(shù)的和為偶數(shù)，可分為兩種情況：的和為偶數(shù)，可分為兩種情況：1出現(xiàn)的次數(shù)與出現(xiàn)的次數(shù)與2出現(xiàn)的次數(shù)都為偶數(shù)；出現(xiàn)的次數(shù)都為偶數(shù)；1出現(xiàn)的次數(shù)與出現(xiàn)的次數(shù)與2出現(xiàn)的次數(shù)都為奇數(shù)。出現(xiàn)的次數(shù)都為奇數(shù)。由加法法則知，序列由加法法則知，序列an的指數(shù)生成函數(shù)為的指數(shù)生成函數(shù)為exxxxxxxxnnnnnxxxfxxxxx xxeeeeee eex n a2324223352225330( )1

56、.1.2!4!2!.1.3!5!2!2221512!1512 故故有有53 這是生成函數(shù)的應(yīng)用實(shí)例之一。整數(shù)的拆分就是把整數(shù)這是生成函數(shù)的應(yīng)用實(shí)例之一。整數(shù)的拆分就是把整數(shù)分成若干個(gè)正整數(shù)部分，并且不考慮各部分的次序，不同的分成若干個(gè)正整數(shù)部分，并且不考慮各部分的次序，不同的拆分方法的總數(shù)叫拆分方法的總數(shù)叫拆分?jǐn)?shù)拆分?jǐn)?shù)p(n) 。相當(dāng)于把。相當(dāng)于把n個(gè)無(wú)區(qū)別的球放個(gè)無(wú)區(qū)別的球放到到1mn個(gè)無(wú)標(biāo)志的盒子中的方法數(shù)。個(gè)無(wú)標(biāo)志的盒子中的方法數(shù)。 7.4 整數(shù)的拆分概念7.4 整數(shù)的拆分整數(shù)的拆分xxxxxxxxxxxxxxx23224362345611111.1.1.123457.如如： 547.4

57、 整數(shù)的拆分定理47.4 整數(shù)的拆分整數(shù)的拆分定理定理 7.4設(shè)設(shè)a,b,c.為大于為大于0的整數(shù)，則的整數(shù)，則1/(1-xa)(1-xb)(1-xc)的級(jí)數(shù)展開(kāi)式中的級(jí)數(shù)展開(kāi)式中xn的系數(shù)等于把正整數(shù)的系數(shù)等于把正整數(shù)n拆分為拆分為a,b,c的和的方法數(shù)的和的方法數(shù)p(n) 。證明：證明：注意到注意到如果項(xiàng)如果項(xiàng)xn是由是由x3a, xb, x2c,的乘積所組成的的乘積所組成的 ，則，則于是，每當(dāng)于是，每當(dāng)n可以拆分為可以拆分為a,b,c的和時(shí)，的和時(shí)， xn就會(huì)出現(xiàn)，這就證明了就會(huì)出現(xiàn)，這就證明了定理的結(jié)論。定理的結(jié)論。abcaabbccxxxxxxxxx22211111.1.1.naaa

58、bcc.557.4 整數(shù)的拆分例17.4 整數(shù)的拆分整數(shù)的拆分例例 題題例例1、若有若有1克、克、2克、克、3克、克、4克的砝克的砝碼各一枚，問(wèn)能稱出哪幾種重量？有碼各一枚，問(wèn)能稱出哪幾種重量？有幾種可能方案？幾種可能方案？ 證明：證明：我們采用如下辦法來(lái)產(chǎn)生拆分?jǐn)?shù)的生成函數(shù)：我們采用如下辦法來(lái)產(chǎn)生拆分?jǐn)?shù)的生成函數(shù)：從右端的生成函數(shù)知從右端的生成函數(shù)知能能稱出從稱出從1克到克到10克的克的重量重量，系數(shù)便是方案，系數(shù)便是方案數(shù)。數(shù)。例如右端有例如右端有2x5 項(xiàng)，即稱出項(xiàng)，即稱出5克的方案有克的方案有2種種，5=2+3=1+4。同樣同樣6=1+2+3=2+4，10=1+2+3+4，即稱出，即稱

59、出6克的方案有克的方案有2種種，稱，稱出出10克的方案有克的方案有1種種。234233472345678910(1)(1)(1)(1)(1)(1)122222xxxxxxxxxxxxxxxxxxxx 567.4 整數(shù)的拆分例27.4 整數(shù)的拆分整數(shù)的拆分例例2、求用求用1分、分、2分、分、3分的郵票貼分的郵票貼出不同數(shù)值的方案數(shù)。出不同數(shù)值的方案數(shù)。 解：解：因郵票允許重復(fù)，故生成函數(shù)為因郵票允許重復(fù)，故生成函數(shù)為以其中以其中x4為例，其系數(shù)為為例，其系數(shù)為4，即，即4拆分成拆分成1、2、3之和的拆分?jǐn)?shù)為之和的拆分?jǐn)?shù)為4，即即f xxxxxxxxxxxxxxxxxxxxx12224362324

60、56234563( )(1.)(1.)(1.)11111111123457. 分分分分分分41 1 1 11 121322 例例 題題577.4 整數(shù)的拆分例37.4 整數(shù)的拆分整數(shù)的拆分例例3、若有若有1克的砝碼克的砝碼3枚，枚，2克的克的4枚，枚，4克克的的2枚，問(wèn)能稱出哪些重量？各有幾種方枚，問(wèn)能稱出哪些重量？各有幾種方案？案？ 解：解：上面的上面的1+x4 +x8項(xiàng)表示項(xiàng)表示4克砝碼只有兩枚，或不取，或取一枚，或克砝碼只有兩枚，或不取，或取一枚，或取取2枚。枚。x8項(xiàng)的系數(shù)為項(xiàng)的系數(shù)為5，說(shuō)明稱，說(shuō)明稱8克的方案有克的方案有5種種 ：f xxxxxxxxxx xxxxxx xxxxxx