組合數學第七章生成函數PPT課件

1、1制作講授：王繼順2目錄（目錄（1）第第1章章 什么是組合數學什么是組合數學1.1引例引例1.2組合數學研究對象、內容和方法組合數學研究對象、內容和方法第第2章章 鴿巢原理鴿巢原理2.1 鴿巢原理：簡單形式鴿巢原理：簡單形式2.2 鴿巢原理：加強形式鴿巢原理：加強形式2.3 ramsey定理定理2.4 鴿巢原理與鴿巢原理與ramsey定理的應用定理的應用本章小結 習題第第3章章 排列與組合排列與組合3.1 兩個基本的計數原理兩個基本的計數原理3.2 集合的排列與組合集合的排列與組合3.3 多重集的排列與組合多重集的排列與組合本章小結 習題第四章第四章 二項式系數二項式系數4.1 二項式定理二項

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

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

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

5、級數，不管其收斂性； x為形式變元，為形式變元，f(x)為形式冪級數為形式冪級數 ； 序列與生成函數一一對應；序列與生成函數一一對應； 生成函數是序列的另一表達形式；生成函數是序列的另一表達形式； 有限序列也可用生成函數表示；有限序列也可用生成函數表示； 可與二項式定理結合應用可與二項式定理結合應用 。給定一無窮序列給定一無窮序列(a0,a1,an,)(簡記為簡記為an)，稱函，稱函數數 為序列為序列an的生成函數（發(fā)生、普的生成函數（發(fā)生、普通母函數）通母函數） 。 0( )iiif xa x77.1 生成函數例17.1 生成函數的基本概念生成函數的基本概念例例 題題7.1.1 生成函數生成

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

7、(1)kkkkkknknnnnkf xxxxknk =xkn =xxk 97.1 生成函數例34.1 生成函數的基本概念生成函數的基本概念例例 題題4.1.1 生成函數生成函數 例例3、證明證明(1-4x)-1/2是序列是序列(c(0,0), c(2,1), c(4,2), , c(2n,n),)的生成函數。的生成函數。 證明：證明：由牛頓二項式定理有由牛頓二項式定理有 由定義知，由定義知，(1-4x)-1/2是序列是序列(c(0,0), c(2,1), c(4,2), , c(2n,n),)的生成函數。的生成函數。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 生成函數例47.1 生成函數的基本概念生成函數的基本概念例例 題題7.1.1 生成函數生成函數 例例4、求序列求序列(0, 123, 234, n(n+1)(n+2),)的生成函數。的生成函數。 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 由由牛牛頓頓二二項項式式定定理理的的推推論論，有有 將將上上式式兩兩端端同同時時微微分分兩兩次次得得 將將上上式式兩兩端端再再微微分分得得 兩兩邊邊同同乘乘解解以以 得得 因因此此 ：n nn4(0 1 2 3 2 3 4,., (1)(2),.) 是是序序列列 ，的的普普通通母母函函數數。117.1 指數生成函數概念7.1 生成函數的基本概念生成函數的基本概念定義定義 7.27.1.2 指數生成函數指數生成函數 注：注： fe(x)也是形式冪函數。也是形式冪函數。 經常可

10、結合以下公式運算：經常可結合以下公式運算：給定一無窮序列給定一無窮序列(a0,a1,an,)（簡記為（簡記為an），稱函），稱函數數 為序列為序列an的指數生成函數。的指數生成函數。 ieiixfxai0( )!nxnxxxen221.1!2! nxnxxxen21.( 1).1!2! nxxxxxeexn321sin.1!3!(21)!2127.1 指數生成函數例57.1 生成函數的基本概念生成函數的基本概念例例 題題7.1.2 指數生成函數指數生成函數 例例5、設設n是整數，求序列是整數，求序列(p(n,0), p(n,1), p(n,n)的指數生成函數的指數生成函數fe(x)。 解：解：

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

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

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

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

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

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

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

18、2 生成函數的基本運算生成函數的基本運算六六個個推推論論推論推論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 生成函數運算推論27.2 生成函數的基本運算生成函數的基本運算六六個個推推論論推論推論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 生成函數運算推論37.2 生成函數的基本運算生成函數的基本運算六六個個推推論論推論推論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é)例見本節(jié)例1。237.2 生成函數運算推論4

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

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

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

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

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

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

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

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

28、常出現(xiàn)，許多有意義的計數問題都與這個數有關。義的計數問題都與這個數有關。kkkknnnnnnnnnkzzzkkzxnxxnnnxnnxnf xxnnnann1211121111( 1)22110 5 | |1,11124 ,( 1)22141( 4 )1222211114122 ( )12122 1 根根據據推推論論 .有有令令有有故故因因此此nnann1221336.5 母函數的應用例4-16.5 母函數在遞推關系中的應用母函數在遞推關系中的應用例例 題題例例4、求遞歸關系求遞歸關系 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) ( )( )這這是是一一個個非非常常系系數數的的線線性性齊齊次次遞遞推推關關系系，設設為為序序列列的的普普通通母母函函數數。將將微微分分有有將將上上式式兩兩端端同同乘乘以以 有有因因此此（注注意意初初值值條條件件）有有解解：nnnnnnnnnnnnnnnnnna xnaxx f xa xaxx xfxxxf xnanaax11222220222122(1)(2) 2( )22()( ) (12) ( )(1)(2)20 而而將

30、將以以上上三三個個式式子子兩兩端端分分別別相相加加，并并由由遞遞推推關關系系得得346.5 母函數的應用例4-26.5 母函數在遞推關系中的應用母函數在遞推關系中的應用例例 題題例例4、求遞歸關系求遞歸關系 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)()!根根據據初初值值條條件件，可可得得，故故有有356.5 母函數的應用例5-16.5 母函數在遞推關系中的應用母函數在遞推關系中的應用例例 題題例例5、求求n位十進制正整數中出現(xiàn)偶數位十進制正整數中出現(xiàn)偶數個個5的數的個數。的數的個數。解解i：令令an=n位十進制數中出現(xiàn)偶數個位十進制數中出現(xiàn)偶數個5的數的個數的數的個數 bn=n位十進制數中出現(xiàn)奇數個位十進制數中出現(xiàn)奇數個5的數的個數的數的個數建立遞推關系如下建立遞推關系如下 這是關于序列這是關于序列an和和 bn的聯(lián)立關系。的聯(lián)立關系。設序列設序列an,bn的普

32、通母函數分別為的普通母函數分別為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 ) (進進行行計計算算如如下下xb x x b xxa x)( )8(19 ) ( )( )1同同理理可可得得366.5 母函數的應用例5-26.5 母函數在遞推關系中的應用母函數在遞推關系中的應用例例 題題例例5、求求n位十進制正整數中出現(xiàn)偶數位十進制正整數中出

33、現(xiàn)偶數個個5的數的個數。的數的個數。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故故可可得得關關于于普普通通母母函函數數和和聯(lián)聯(lián)立立方方程程組組nnnnnnnxa01(7 89 10 )21(7 89 10 )2 376.5 母函數的應用例5-36.5 母函數在遞推關系中

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

49、此可見滿足條件的5位數位數ar=215個。個。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 排列應用例97.3 在排列組合中的應用在排列組合中的應用4.3.2 在排列中的應用在排列中的應用 例例 題題例例9、求求1,3,5

50、,7,9五個數字組成的五個數字組成的n位數的個位數的個數，要求其中數，要求其中3,7出現(xiàn)的次數為偶數，其他出現(xiàn)的次數為偶數，其他1,5,9出現(xiàn)的次數不加限制出現(xiàn)的次數不加限制。 解：解：設滿足上述條件的設滿足上述條件的r位數的個數為位數的個數為ar，序列，序列ar的指數母函數為的指數母函數為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 排列應用例107.3 在排列組合中的應用在排列組合中的應用7.3.2 在排列中的應用在排列中的應用 例例 題題例例10、證明從證明從n個不同的物體中允許重復地個不同的物體中允許重復地選取選取r個物體的排列數為個物體的排列數為nr。 證明：證明：這個問題實際上是證明重集這個問題實際上是證明重集b=*b1,*b2,*bn的的r排列數為排列數為nr。設。設ar為所求的排列數。則序列為所求的排列數。則序列ar的指數母函數為的指數母函數為rnerxnnxrrrrxxfxxrx eenr an20( )(1.)2!()!故故有有507.3 排列應用例114.

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

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

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

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

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

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

58、bcc.557.4 整數的拆分例17.4 整數的拆分整數的拆分例例 題題例例1、若有若有1克、克、2克、克、3克、克、4克的砝克的砝碼各一枚，問能稱出哪幾種重量？有碼各一枚，問能稱出哪幾種重量？有幾種可能方案？幾種可能方案？ 證明：證明：我們采用如下辦法來產生拆分數的生成函數：我們采用如下辦法來產生拆分數的生成函數：從右端的生成函數知從右端的生成函數知能能稱出從稱出從1克到克到10克的克的重量重量，系數便是方案，系數便是方案數。數。例如右端有例如右端有2x5 項，即稱出項，即稱出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 整數的拆分例27.4 整數的拆分整數的拆分例例2、求用求用1分、分、2分、分、3分的郵票貼分的郵票貼出不同數值的方案數。出不同數值的方案數。 解：解：因郵票允許重復，故生成函數為因郵票允許重復，故生成函數為以其中以其中x4為例，其系數為為例，其系數為4，即，即4拆分成拆分成1、2、3之和的拆分數為之和的拆分數為4，即即f xxxxxxxxxxxxxxxxxxxxx12224362324

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