1、第二章 母函數(shù)與遞推關(guān)系組合數(shù)學(xué)組合數(shù)學(xué)2.1 2.1 母函數(shù)母函數(shù) 遞推關(guān)系是計(jì)數(shù)的一個(gè)強(qiáng)有力的工具，特別是在做算法分析時(shí)是必需的。遞推關(guān)系的求解主要是利用母函數(shù)。當(dāng)然母函數(shù)尚有其他用處，但這主要是介紹解遞推關(guān)系上的應(yīng)用。例如1)-1-(2 )()(1)1 ()1)(1 (212131212121nnnnnnxaaaxaaaaaaxaaaxaxaxa 2.1 2.1 母函數(shù)母函數(shù) 項(xiàng)的系數(shù) 中所有的項(xiàng)包括n個(gè)元素a1，a2， an中取兩個(gè)組合的全體；同理項(xiàng)系數(shù)包含了從n個(gè)元素a1，a2， an中取3個(gè)元素組合的全體。以此類推。2xnnaaaaaa13121 2.1 2.1 母函數(shù)母函數(shù) 若令

2、a1=a2= =an=1，在2-1-1式中 項(xiàng)系數(shù)： 中每一個(gè)組合有1個(gè)貢獻(xiàn)，其他各項(xiàng)以此類推。故有：2xnnaaaaaa13121 2)-1-(2 ),()2 ,() 1 ,(1)1 (2nnxnnCxnCxnCx2.1 2.1 母函數(shù)母函數(shù) 另一方面：nmnmxxx)1 ()1 ()1 ( nmmmnxnmnmCxnmCnmCxxmmCxmCmCxnnCxnCnC),( ) 1 ,()0 ,(),() 1 ,()0 ,( ),() 1 ,()0 ,( 12.1 2.1 母函數(shù)母函數(shù)比較等號(hào)兩端項(xiàng)對(duì)應(yīng)系數(shù)，可得一等式)0 ,(),( ) 1,() 1 ,( ),()0 ,(),(nCrmCr

3、nCmCrnCmCrnmC2.1 2.1 母函數(shù)母函數(shù) 同樣對(duì)于 ，（設(shè) ），用類似的方法可得等式： mnxx)/11 ()1 (mn 3)-1-(2 )0 ,()0 ,( )0 ,()0 ,()0 ,()0 ,(),(mCnCmCnCmCnCmnmCnmmmnxxxx)1 ()/11 ()1 ( 正法如下：2.1 2.1 母函數(shù)母函數(shù)z比較等式兩端的常數(shù)項(xiàng)，即得公式(2-1-3)nmmmnxnmnmCxnmCxnmCnmCxxmmCxmCmCxnnCxnCnC),( )2 ,() 1 ,()0 ,(),() 1 ,()0 ,( ),() 1 ,()0 ,( 212.1 2.1 母函數(shù)母函數(shù)又

4、如等式：nxnnCxnCxnCnCx),( )2 ,() 1 ,()0 ,()1 (2令x=1 可得4)-1-(2 2),()2 ,() 1 ,()0 ,(nnnCnCnCnC2.1 2.1 母函數(shù)母函數(shù)(2-1-2)式等號(hào)的兩端對(duì)x求導(dǎo)可得：5)-1-(2 2 ),()3 ,(3)2 ,(2) 1 ,(1nnnnnCnCnCnC等式(2-1-5)兩端令x=1，得：5)-1-(2 2 ),() 3 ,(3)2 ,(2) 1 ,(1nnnnnCnCnCnC2.1 2.1 母函數(shù)母函數(shù) 用類似的方法還可以得到：132)1 (),( )3 ,(3)2 ,(2) 1 ,( nnxnxxnnnCxnCx

5、nCxnC7)-1-(2 2) 1( ),()3 ,(3)2 ,(2) 1 ,( 2222nnnnnCnnCnCnC 定義：對(duì)于序列定義：對(duì)于序列 構(gòu)造一構(gòu)造一函數(shù)：函數(shù)：2.1 2.1 母函數(shù)母函數(shù) 還可以類似地推出一些等式，但通過上面一些例子已可見函數(shù) 在研究序列 的關(guān)系時(shí)所起的作用。對(duì)其他序列也有同樣的結(jié)果?，F(xiàn)引進(jìn)母函數(shù)概念如下： nx)1 ( ),(,),1 ,(),0 ,(nnCnCnC,210aaa,)(2210 xaxaaxG,210aaa稱函數(shù)G(x)是序列 的母函數(shù)序列 可記為 。 如若已知序列 則對(duì)應(yīng)的母函數(shù)G(x)便可根據(jù)定義給出。反之，如若以求得序列的母函數(shù)G(x)，則

6、該序列也隨之確定。 2.1 2.1 母函數(shù)母函數(shù) 例如 是序列 的母函數(shù)。 nx)1 ( ),(,),1 ,(),0 ,(nnCnCnC,210aaa,210aaana2.2 2.2 遞推關(guān)系遞推關(guān)系 利用遞推關(guān)系進(jìn)行計(jì)數(shù)這個(gè)方法在算法分析中經(jīng)常用到，舉例說明如下： 例一.Hanoi問題：這是個(gè)組合數(shù)學(xué)中的著名問題。N個(gè)圓盤依其半徑大小，從下而上套在A柱上，如下圖示。每次只允許取一個(gè)移到柱B或C上，而且不允許大盤放在小盤上方。若要求把柱A上的n個(gè)盤移到C柱上請(qǐng)?jiān)O(shè)計(jì)一種方法來，并估計(jì)要移動(dòng)幾個(gè)盤次?，F(xiàn)在只有A、B、C三根柱子可用。2.2 2.2 遞推關(guān)系遞推關(guān)系 Hanoi問題是個(gè)典型的問題，第

7、一步要設(shè)計(jì)算法，進(jìn)而估計(jì)它的復(fù)雜性，集估計(jì)工作量。算法：算法：N=2時(shí)第一步先把最上面的一個(gè)圓盤套在B上z z第二步把下面的一個(gè)圓盤移到C上 最后把B上的圓盤移到C上 到此轉(zhuǎn)移完畢A B C2.2 2.2 遞推關(guān)系遞推關(guān)系z 對(duì)于一般n個(gè)圓盤的問題，z 假定n-1個(gè)盤子的轉(zhuǎn)移算法已經(jīng)確定。z 先把上面的n-1個(gè)圓盤經(jīng)過C轉(zhuǎn)移到B。z 第二步把A下面一個(gè)圓盤移到C上 z 最后再把B上的n-1個(gè)圓盤經(jīng)過A轉(zhuǎn)移到C上 A B C 2.2 2.2 遞推關(guān)系遞推關(guān)系 上述算法是遞歸的運(yùn)用。n=2時(shí)已給出算法；n=3時(shí)，第一步便利用算法把上面兩個(gè)盤移到B上，第二步再把第三個(gè)圓盤轉(zhuǎn)移到柱C上；最后把柱B上兩

8、個(gè)圓盤轉(zhuǎn)移到柱C上。N=4，5，以此類推。2.2 2.2 遞推關(guān)系遞推關(guān)系 算法分析：令算法分析：令h(n)表示表示n個(gè)圓盤所需要個(gè)圓盤所需要的轉(zhuǎn)移盤次。根據(jù)算法先把前面的轉(zhuǎn)移盤次。根據(jù)算法先把前面n-1個(gè)盤子個(gè)盤子轉(zhuǎn)移到轉(zhuǎn)移到B上；然后把第上；然后把第n個(gè)盤子轉(zhuǎn)到個(gè)盤子轉(zhuǎn)到C上；上；最后再一次將最后再一次將B上的上的n-1個(gè)盤子轉(zhuǎn)移到個(gè)盤子轉(zhuǎn)移到C上。上。 n=2時(shí)，算法是對(duì)的，因此，時(shí)，算法是對(duì)的，因此，n=3是算是算法是對(duì)的。以此類推。于是有法是對(duì)的。以此類推。于是有2.2 2.2 遞推關(guān)系遞推關(guān)系算法復(fù)雜度為：1)-2-(2 1) 1 ( , 1) 1(2)(hnhnh,)3()2()

9、 1 ()(32xhxhxhxH H(x)是序列 的母函數(shù)。給定了序列，對(duì)應(yīng)的母函數(shù)也確定了。反過來也一樣，求得了母函數(shù)，對(duì)應(yīng)的序列也就可得而知了。當(dāng)然，利用遞推關(guān)系(2-2-1)式也可以依次求得 ，這樣的連鎖反應(yīng)關(guān)系，叫做遞推關(guān)系。),3(),2(),1 (hhh),3(),2(hh2.2 2.2 遞推關(guān)系遞推關(guān)系 下面介紹如何從(2-2-1)式求得母函數(shù)H(x)的一種形式算法。所謂形式算法說的是假定這些冪級(jí)數(shù)在作四則運(yùn)算時(shí)，一如有限項(xiàng)的代數(shù)式一樣。,)3()2() 1 ()(32xhxhxhxH,)2(2) 1 (2- )(2 )xhxhxxH_32)2(2)3( )1 (2)2() 1

10、()()21 (xhhxhhxhxHx2.2 2.2 遞推關(guān)系遞推關(guān)系 根據(jù)(2-2-1)，, 1)2(2)3(, 1) 1 (2)2(, 1) 1 ( hhhhh)1/()()21 ( 32xxxxxxHx 或利用遞推關(guān)系(2-2-1)有1) 1 (2)2(:2 hhx1)2(2)3(:3 hhx )_)1/()(2)( 2xxxxHxxH2.2 2.2 遞推關(guān)系遞推關(guān)系 上式左端為：xxHxhxHxhxh)() 1 ()()3()2(32 右端第一項(xiàng)為：)(2x )2() 1 (2)2(2) 1 (2232xHxhxhxxhxh 右端第二項(xiàng)為：)1/(232xxxx2.2 2.2 遞推關(guān)系

11、遞推關(guān)系 整理得xxxxxxHx11)()21 (2)21)(1 ()(xxxxH 這兩種做法得到的結(jié)果是一樣的。即：2.2 2.2 遞推關(guān)系遞推關(guān)系 令)21)(1 (2 )21 (1 ()1 ()21 (211)(xxB)xAB)-(AxxxBxAxBxAxHxxBABA)2()( 如何從母函數(shù)得到序列 ？下面介紹一種化為部分分?jǐn)?shù)的算法。),2(),1 (hh2.2 2.2 遞推關(guān)系遞推關(guān)系 由上式可得：. 1 , 1BA 即：12BA0 BA123322) 12( ) 12() 12() 12( )1 ()2221 ( 11211)(kkkxxxxxxxxxxxxH2.2 2.2 遞推關(guān)

12、系遞推關(guān)系由于：1)()(kkxkhxH12)( kkh2.2 2.2 遞推關(guān)系遞推關(guān)系 例例2. 求求n位十進(jìn)制數(shù)中出現(xiàn)偶數(shù)個(gè)位十進(jìn)制數(shù)中出現(xiàn)偶數(shù)個(gè)5的數(shù)的數(shù)的個(gè)數(shù)。的個(gè)數(shù)。 先從分析n位十進(jìn)制數(shù)出現(xiàn)偶數(shù)個(gè)5的數(shù)的結(jié)構(gòu)入手 是n-1位十進(jìn)制數(shù)，若含有偶數(shù)個(gè)5，那么 取5以外的0，1，2，3，4，6，7，8，9九個(gè)數(shù)中的一個(gè)，假設(shè) 只有奇數(shù)個(gè)5，則取 ，使 成為出現(xiàn)偶數(shù)個(gè)5的十進(jìn)制數(shù)。121nppp1np121nppp5npnnpppp1212.2 2.2 遞推關(guān)系遞推關(guān)系 解法1： 令 位十進(jìn)制數(shù)中出現(xiàn)5的數(shù)的個(gè)數(shù)， 位十進(jìn)制數(shù)中出現(xiàn)奇數(shù)個(gè)5的數(shù) 的個(gè)數(shù)。 nannbn 故有：119nnnb

13、aa119nnnabb1 , 811ba)222( 也有類似解釋。2.2 2.2 遞推關(guān)系遞推關(guān)系 (2-2-2)式中的 表達(dá)了含有偶數(shù)個(gè)5的n位十進(jìn)制數(shù)的兩個(gè)組成部分。 表達(dá)由含有偶數(shù)個(gè)5的n-1位十進(jìn)制數(shù) ，令 取5以外的0，1，2，3，4，6，7，8，9九個(gè)數(shù)中的一個(gè)數(shù)構(gòu)成的。 項(xiàng)表示當(dāng) 是含有奇數(shù)個(gè)5的n-1位十進(jìn)制數(shù)，令 而得 是含偶數(shù)個(gè)5的n位十進(jìn)制數(shù)。119nnnabb119nnnbaa19na121npppnp1nb121nppp5npnppp21 (2-2-2)是關(guān)于序列 和 的連立關(guān)系。2.2 2.2 遞推關(guān)系遞推關(guān)系 設(shè)序列 的母函數(shù)為 ，序列 的母函數(shù)為 。nanbna

14、)(xAnb)(xB22122123212321)( )99)(9 )( )( xbxbxxBxaxaxxAxbxbbxBxaxaaxA即：_8)()()91 (xxBxAx2.2 2.2 遞推關(guān)系遞推關(guān)系承前頁： )9 : 9 : 9 : 33432232112baaxbaaxbaax_)()(98)(xxBxxAxA8)()()91 ( xxBxAx2.2 2.2 遞推關(guān)系遞推關(guān)系 又：_1)()()91 (xxAxBx故得關(guān)于母函數(shù) 和 得連立方程組：)(xA)(xB1)()91 ()(8)()()91 (xBxxxAxxBxAx2212212321)( )99)(9)(xaxaxxAx

15、bxbxxBxbxbxbxB2.2 2.2 遞推關(guān)系遞推關(guān)系xxxxD91 91 xx )91 (280181xx)101)(81 (xx)101)(81 (87191 18801811)(2xxxxxxxxA)101)(81 (118 91)101)(81 (1)(xxxxxxxxB2.2 2.2 遞推關(guān)系遞推關(guān)系0)10987(21)1019817(21)( kkkkxxxxA111029827 kkka2.2 2.2 遞推關(guān)系遞推關(guān)系 解法二： n-1位的十進(jìn)制數(shù)的全體共 從中去掉含有偶數(shù)個(gè)5的數(shù)，余下的便是n-1位中含有奇數(shù)個(gè)5的數(shù)。故有： 2109n121111099nnnnnnab

16、baa8 ,1098 121aaannn2.2 2.2 遞推關(guān)系遞推關(guān)系令221232188)(8 )(xaxaxxAxaxaaxA_22312)8()8(8)()81 (xaaxaaxAx2.2 2.2 遞推關(guān)系遞推關(guān)系xxxxxxxAx10171810198 10998)()81 ( 20)10987(21 )1019817(21)101)(101 (718)( kkkkxxxxxxxA111029827 kka 1不出現(xiàn)某特定元素設(shè)為 ，其組合數(shù)為 ，相當(dāng)于排除 后從 中取r個(gè)做允許重復(fù)的組合。2.2 2.2 遞推關(guān)系遞推關(guān)系 例三：從n個(gè)元素 中取r個(gè)進(jìn)行允許重復(fù)的組合。假定允許重復(fù)的

17、組合數(shù)用 表示，其結(jié)果可能有以下兩種情況。 naaa,21),(rnC1a), 1(rnC1anaa,22.2 2.2 遞推關(guān)系遞推關(guān)系 2至少出現(xiàn)一個(gè) ，取組合數(shù)為 相當(dāng)于從 中取r-1個(gè)做允許重復(fù)的組合，然后再加上一個(gè) 得從n個(gè)元素中取r個(gè)允許重復(fù)的組合。1a) 1,(rnC1anaaa,21 依據(jù)加法原則可得：), 1() 1,(),(rnCrnCrnC 因 ，故令1) 1 , 1(,) 1 ,(nnCnnC1)0 ,(nC2.2 2.2 遞推關(guān)系遞推關(guān)系 遞推關(guān)系(2-2-3)帶有兩個(gè)參數(shù)n和r。xnCxnCxGxnCxnCxxGxnCxnCnCxGnnn) 1 , 1()0 , 1(

18、)( ) 1 ,()0 ,( )()2 ,() 1 ,()0 ,()(122_)322( 0)()()1 (1xGxGxnn2.2 2.2 遞推關(guān)系遞推關(guān)系 (2-2-3)式是關(guān)于 的遞推關(guān)系，但系數(shù) 不是常數(shù)。但)(xGn)1 (xxxxxCxCCxG111 )2 , 1 () 1 , 1 ()0 , 1 ()( 221n11 -n221x)-(11)(x)-(11 )()1 (1)(11)( xGxGxxGxxGnnn2.2 2.2 遞推關(guān)系遞推關(guān)系 由二項(xiàng)式定理32! 3)2)(1(! 2) 1(1)1 (xnnnxnnnxx 可得), 1( )!1()!1(!) 1() 1(),(rr

19、nCnrnrrnnnrnC2.3 2.3 母函數(shù)的性質(zhì)母函數(shù)的性質(zhì)2.32.3母函數(shù)的性質(zhì)母函數(shù)的性質(zhì) 一個(gè)序列和它的母函數(shù)一一對(duì)應(yīng)。給了序列便得知它的母函數(shù)；反之，求得母函數(shù)序列也隨之而定。這種關(guān)系頗像數(shù)學(xué)中的積分變換，特別酷似離散序列的Z變換。如2的例子所示的那樣，為了求滿足某種第推關(guān)系的序列，可把它轉(zhuǎn)換為求對(duì)應(yīng)的母函數(shù) ， 可能滿足一代數(shù)方程，或代數(shù)方程組，甚至于是微分方程。)(xG)(xG2.32.3母函數(shù)的性質(zhì)母函數(shù)的性質(zhì) 最后求逆變換，即從已求得的母函數(shù) 得到序列 。關(guān)鍵在于要搭起從序列到母函，從母函數(shù)到序列這兩座橋。這一節(jié)便是以此為目的的。不特別說明下面假設(shè) 、 兩個(gè)序列對(duì)應(yīng)的母

20、函數(shù)分別為 、)(xGnakakb)(xA)(xB2.32.3母函數(shù)的性質(zhì)母函數(shù)的性質(zhì) 性質(zhì)1：假設(shè) 那么kblk 0lkalk )()(xAxxBl證：證：)( 000)(11011xAxxaxaxbxbxBlllllll2.32.3母函數(shù)的性質(zhì)母函數(shù)的性質(zhì) 例例. 知知 1! 3! 2! 132xexxxxA那么) 1(! 3! 2! 1)(121xmmmmexxxxxB2.32.3母函數(shù)的性質(zhì)母函數(shù)的性質(zhì) 性質(zhì)2：假設(shè) ，lkkab那么llkkkxxaxAxB/ )()(102.32.3母函數(shù)的性質(zhì)母函數(shù)的性質(zhì)llkkklllllllllllllxxaxAxxaxaxaaxAxaxaxa

21、xxaxaaxB/ )( / )( )(1 )( 101122102211221證：證：2210)( xbxbbxB2.32.3母函數(shù)的性質(zhì)母函數(shù)的性質(zhì) 例例.! 5! 3sin)(53xxxxxA6533/ ! 51! 31sin ! 91! 71)(xxxxxxxxB2.32.3母函數(shù)的性質(zhì)母函數(shù)的性質(zhì) 性質(zhì)2：假設(shè) ，那么kiikab0 xxAxB1)()(證：證： ): : : :1 2102101210100nnaaaabxaaabxaabxab2.32.3母函數(shù)的性質(zhì)母函數(shù)的性質(zhì) ): : : :1 2102101210100nnaaaabxaaabxaabxab_)1/()()1

22、/( )1/()1/()1/()(22102210 xxAxxaxaaxxaxxaxaxB2.32.3母函數(shù)的性質(zhì)母函數(shù)的性質(zhì) 例例. 知知xxxxxAn111)(2232)1 (14321)(xxxxxB20)1 (1) 1(xxkkk2.32.3母函數(shù)的性質(zhì)母函數(shù)的性質(zhì) 類似可得：03323232)1 (1)2)(1(21 10631 )1 ( )4321 ()(kkxxkkxxxxxxxxxxC2.32.3母函數(shù)的性質(zhì)母函數(shù)的性質(zhì) 性質(zhì)性質(zhì)2：假設(shè)：假設(shè) 收斂，那么收斂，那么0kkaxxxAAxB1)() 1 ()( ) 1 ( : ) 1 ( : ) 1 (:1 10212021121

23、00aaAabxaAaabxAaaab_)1 ( )1 (1)1 ()(221202xxxaxxxaxxAxB2.32.3母函數(shù)的性質(zhì)母函數(shù)的性質(zhì)xxxAAxxxaaxAxB1)() 1 ( )1/()(1) 1 ()( 102.32.3母函數(shù)的性質(zhì)母函數(shù)的性質(zhì) 性質(zhì)性質(zhì)5. 5. 假設(shè)假設(shè) ，那么，那么 。kkkab xxAxB 例例. xxxxA111223211132xxxxxxx那么2.32.3母函數(shù)的性質(zhì)母函數(shù)的性質(zhì)kabkk1 xdxxAxxB01性質(zhì)5和性質(zhì)6的結(jié)論是顯而易見的。 性質(zhì)性質(zhì)6. 假設(shè)假設(shè) ，那么，那么 2.32.3母函數(shù)的性質(zhì)母函數(shù)的性質(zhì) 性質(zhì)性質(zhì)7. 7. 假設(shè)

24、假設(shè) 那么那么 022110babababackkkkkkiikiba0 xBxAxcxccxC22102.32.3母函數(shù)的性質(zhì)母函數(shù)的性質(zhì)證證: 。 22100 xbxbbaxC22101xbxbbxa 221022xbxbbxa22102210 xbxbbxaxaa xBxAxC),:1000bac ,:201101babac,:30211202bababac_2.32.3母函數(shù)的性質(zhì)母函數(shù)的性質(zhì) 例. 知 那么 ,21321,132,1112322kkkCxxxxxxBxxxxAk 31xxxC2.4 Fibonacci2.4 Fibonacci數(shù)列數(shù)列2.4.12.4.1遞推關(guān)系遞推關(guān)

25、系 Fibonacci數(shù)列是遞推關(guān)系的又一個(gè)典型問題，數(shù)列的本身有著許多應(yīng)用。 問題：有雌雄兔子一對(duì)，假定過兩月便可繁殖雌雄各一的一對(duì)小兔。問過了n個(gè)月后共有多少對(duì)兔子？ 設(shè)滿n個(gè)月時(shí)兔子對(duì)數(shù)為 其中當(dāng)月新生兔數(shù)目設(shè)為 對(duì)。第n-1個(gè)月留下的兔子數(shù)目設(shè)為 對(duì)。nFnNnOnnnONF 2.4.12.4.1遞推關(guān)系遞推關(guān)系 但211 , nnnnnFONFO即第n-2個(gè)月的所偶兔子到第n個(gè)月都有繁殖能力了。) 132( 1 , 2121FFFFFnnn由遞推關(guān)系(2-3-1)式可依次得到 , 523 , 3 , 2 435324213FFFFFFFFF2.4.22.4.2問題的求解問題的求解22

26、1)(xFxFxG ): : 23441233FFFxFFFx_)()()(22xGxxxGxxxxGxxGxx)()1 ( 2 設(shè)2.4.22.4.2問題的求解問題的求解 承前頁xBxAxxxxxxxG25112511 )2511)(2511 (1)( 22.4.22.4.2問題的求解問題的求解承前頁1)(250BABA520BABA51 , 51BA2.4.22.4.2問題的求解問題的求解承前頁)()(51 251112511151)( 222xxxxxG5)(F nnn2.4.22.4.2問題的求解問題的求解 其中251512 ,2515122)-3-(2 )251(51)(51nnnn

27、F618. 12511nnFF2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系 2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系 定義定義 如果序列如果序列 滿足滿足 na, 02211knknnnaCaCaCa152,111100kkdadada252 及 是常數(shù)， ，那么稱為 的 階常系數(shù)線性遞推關(guān)系， 稱為 的初始條件，kCCC,21110,kddd0kC152nak252nakkkkCxCxCxxC111)(稱為 的特征多項(xiàng)式 na2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系 設(shè) 為 的母函數(shù))(xGnannxaxaaxG10)(根據(jù)(2-5-1)，有0)(0)(0)(

28、221111211102211knknnnnkkkkkkkkkkaCaCaCaxaCaCaCaxaCaCaCax2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系將這些式子兩邊分別相加，得到 010201xGxCxaxGxCxaxGkkkikiiiii即 10102211kjjkiiijjkkxaxCxGxCxCxC其中10C2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系 令 ，多項(xiàng)式 的次數(shù)不大于 。特征多項(xiàng)式 1010kjjkiiijjxaxCxP xP1k kkkCxCxxC112.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系因此，kkkxCxCxCx111是 次多項(xiàng)式，我們

29、知道 在復(fù)數(shù)域中有 個(gè)根。設(shè)kk 0 xC kkkkaxaxaxxCikikki2121212.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系那么 ikikkkkkxaxaxaxCxCxCx1111121211于是 xPxGxCxCkk11 kkxCxCxPxG11 )452( 1112121ikikkxaxaxaxP2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系(2-5-3)式是有理式，且分子的次數(shù)低于分母的次數(shù)，有分項(xiàng)表示，即：ttkttkttttkkkkxAxAxAxAxAxAxAxAxAxG)1 ()1 (1 )1 ()1 (1 )1 ()1 (1)(2212222222211

30、1211211122112.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系承上頁：)452( )1 (11tikjjiijixA)(xG 的系數(shù)是 。 是常數(shù)。nxnitikjijnannjAai 111ijA2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系 定理：設(shè) 是有理分式，多項(xiàng)式的 次數(shù)低于 的次數(shù)。那么 有分項(xiàng)表示，且表示唯一)()(xQxP)(xP)(xQ)()(xQxP2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系 證明：設(shè)證明：設(shè) 的次數(shù)為的次數(shù)為n，對(duì)，對(duì)n用數(shù)學(xué)歸納用數(shù)學(xué)歸納法。法。)(xQ n=1時(shí)， 是常數(shù)，命題成立。)(xP 假設(shè)對(duì)小于n的正整數(shù)，命題成立

31、。 下面證明對(duì)正整數(shù)n命題成立。設(shè) 是 的 重根，)(xQk0)( ),()()(11xQxQxxQk2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系不妨設(shè) 與 互素，設(shè))(xP)(xQ)()()()()()(11xQxxPxAxQxPkk0)(/ )()()()()(111xQPAxPxPxxAQ)/()()()(11xxAQxPxP2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系 的次數(shù)低于 。根據(jù)歸納假設(shè)，)(xP)(xQ)()()(11xQxxPk可分項(xiàng)表示。因此，)()(xQxP可分項(xiàng)表示。由(2-5-6)式及(2-5-7)式可知表示是唯一的。2.5 2.5 線性常系數(shù)遞推關(guān)

32、系線性常系數(shù)遞推關(guān)系以下分別各種情況討論具體計(jì)算的問題。（1特征多項(xiàng)式 無重根 設(shè) 可見化為 xC kaxaxaxxC21452 kiiikkxaAxaAxaAxaAxG12211111118522.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系 的系數(shù)是nxkiniinaAa1952kAAA,21可由線性方程組daAaAaAdaAaAaAdAAAkkkkkkkk1122111122110211052解出。2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系 的系數(shù)矩陣的行列式是Vander mond 行列式10521121121 1 1 1kkkkkaaaaaa1152jiiiaa0不難看

33、出 有唯一解。10522.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系（2特征多項(xiàng)式 有共軛復(fù)根 設(shè) 是 的一對(duì)共軛復(fù)根。21,aa xC xC)sin(cos,sincos121iaaia中 的系數(shù)是xaAxaA221111nx2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系 nBnAnAAinAAninAninAiAiAAAnnnnnnnnnnnnsincossin)(cos)()sin(cos)sin(cos)sin(cos)sin(cos21212121122112.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系其中)( ,2121AAiBAAA在具體計(jì)算時(shí)，可先求出各對(duì)共軛

34、復(fù)根，再求待定系數(shù)A，B，避免中間過程的復(fù)數(shù)運(yùn)算。 （3特征多項(xiàng)式 有重根設(shè) 是 的 重根，那么(2-5-4)可簡化為)(xCk)(xCkiiixA1)1 (2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系 的系數(shù) 。其中nxnkjjnannjAa11111jnjnnj是n的j-1次多項(xiàng)式。因此， 是 與n的k-1次多項(xiàng)式的乘積。nan2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系 為了簡化計(jì)算，下面引入一些記號(hào)，介紹幾個(gè)命題。 設(shè)x是任意變量，n是非負(fù)整數(shù)，令nx,0 , 1是當(dāng) n,1 ,!) 1() 1(時(shí)當(dāng) nnnxxx2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系 不

35、難證明，多項(xiàng)式可用 唯一線性表示。其中 是常數(shù)0111)(axaxaxaxfnnnnnxxx,1,0ka)0(nk2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系 設(shè) 是給定序列，令 稱為 的 階差分。)( ,11nknknnnaaaaanankanak 不難證明，如果對(duì)任意的n有 ，則有0nra0) 1(0irnriiair因而序列 的特征多項(xiàng)式為narxxC) 1()(2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系 不難證明，假設(shè) 是n的r次多項(xiàng)式，那么 是n的r+1次多項(xiàng)式。nana 以上幾個(gè)命題作為習(xí)題，請(qǐng)讀者自己證明。2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系 總

36、之：總之： (1)若特征多項(xiàng)式 有n個(gè)不同零點(diǎn) 則遞推關(guān)系(2-5-1)的解)(xC,11naaaknnkkkalalala2211其中 是待定系數(shù)，有初始條件(2-5-2)來確定。,11nlll2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系 (2)若特征多項(xiàng)式 有不同的復(fù)根，可依照(1)的辦法處理。不過任意復(fù)數(shù) 可寫為 方式，設(shè) 是 的一個(gè)零點(diǎn)，其共軛復(fù)根為)sin(cos1iei)(xCbia ie)(xC)sin(cos2iei2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系kllikllkiklkiklllkkkkkksin)(cos)( )sin(cos )sin(cos2

37、121212211 和 仍然是待定常數(shù)。即 有一對(duì)共軛復(fù)根 和 時(shí)，遞推關(guān)系(2-5-1)的解有對(duì)應(yīng)的項(xiàng)21ll )(21lli0)(xCie1ie2kBkAkksincos其中A，B是待定常數(shù)。2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系 (3)假設(shè) k重根。不妨設(shè) 是k的重根。則遞推關(guān)系(2-5-1)的解對(duì)應(yīng)于的項(xiàng)為 其中 是k個(gè)待定常數(shù)。nkknAnAA11110)()(xC1110,kAAA2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系 例例1 1：求下列：求下列n n階行列式階行列式 的值。的值。nd20012100012100012nd2.5 2.5 線性常系數(shù)遞推關(guān)

38、系線性常系數(shù)遞推關(guān)系根據(jù)行列式性質(zhì)3 , 2 , 022121dddddnnn對(duì)應(yīng)的特征方程為10) 1(122122mmmmm故 是二重根1mBnABnAdnn) 1)( 2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系 時(shí)有1n21BAd 時(shí)有2n322BAd1 322 BABABA即1 ndn2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系 例例2 2：求：求nknkS01321 1321 1nSnnSnnnSSnn1 同理121nSSnn相減得1221nnnSSS2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系同理12321nnnSSS 3 , 1 , 0 033 2103

39、21SSSSSSSnnnn對(duì)應(yīng)的特征方程為0) 1(133323mmmm2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系 是三重根1m22) 1)( CnBnACnBnASnn0 , 00AS0 , 11CBS0 , 342 , 32CBCBS即) 1(2121212nnnnSn) 1(21321nnn這就證明了2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系 例例2 2：求：求nknkS0222212222) 1(321 ) 1(321 nSnnSnn21 nSSnn同理221) 1( nSSnn相減得12221nSSSnnn2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系同理1

40、) 1(22321nSSSnnn 14 , 5 , 1 , 0 0464 32104321SSSSSSSSSnnnnn對(duì)應(yīng)的特征方程為0) 1(1464014644234234rrrrrmmmm相減得233321nnnnSSSS同理2334321nnnnSSSS2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系 是四重根1rnnDnCnBnAS) 1)( 32根據(jù) 得關(guān)于A、B、C、D的連立方程組：14, 5, 1, 03210SSSS142793584210DCBDCBDCBA2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系122793842111612791484511121B2.5

41、 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系 知 是n的3次式，故不妨令nS)2)(1(! 31) 1(! 21nnDnnCnBnASn確定待定系數(shù)時(shí)，比較方便，無需解一聯(lián)立方程組。 例如0 , 00ASn時(shí)1 , 1 , 11BBASn時(shí)3 , 52 , 22CCBSn時(shí)2 ,1433 , 33DDCBSn時(shí)2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系) 12)(1(61 )2)(1(31) 1(23 nnnnnnnnnSn2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系 例例4 4：求：求33321nSn 解解: : 是是n n的的3 3次多項(xiàng)次多項(xiàng)式，因此式，因此 是滿足遞

42、推關(guān)系：是滿足遞推關(guān)系：31) 1( nSSSnnnnS051010554321nnnnnnSSSSSS設(shè)43214321nAnAnAnASn2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系6 ,412674110043612 ,2373136397 ,1219211443433332233211AASAASAASAS2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系46312271 nnnnSn以n=5對(duì)上面的結(jié)果驗(yàn)證一下225510035S255301207054563512257152.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系 例例5 5：求：求 中中 的的 系數(shù)。系數(shù)。)

43、1)(1 ()1 (1)(323xxxxGnxna 解：解： 的特征多項(xiàng)式是的特征多項(xiàng)式是na) 1)(1() 1(23xxxx2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系 是3重根1x 是1重根1x 的根是012 xx32 , 1 ,23132iei2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系因此可設(shè)32sin32cos ) 1(2nFEDnCBnAann2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系 通過做長除法，求得876543265423231087 54321 11 )1)(1 ()1 (1)(xxxxxxxxxxxxxxxxxG2.5 2.5 線性常系數(shù)遞推關(guān)

44、系線性常系數(shù)遞推關(guān)系可知, 1, 1, 1, 1, 1, 1, 1, 1, 1876543210aaaaaaaaa 利用 的值解得。 故543210,aaaaaaFEDCBA,32sin 32cos) 1(2nFEDnCBnAann2.5 2.5 線性常系數(shù)遞推關(guān)系線性常系數(shù)遞推關(guān)系 通過上式，計(jì)算得 與用長除法得到的結(jié)果相同。,10, 8, 7876aaa2.6 2.6 整數(shù)的拆分和整數(shù)的拆分和FerrersFerrers圖像圖像 2.6.1 2.6.1 問題舉例問題舉例 所謂整數(shù)拆分即把整數(shù)分解成若干整數(shù)的和，相當(dāng)于把n個(gè)無區(qū)別的球放到n個(gè)無標(biāo)志的盒子，盒子允許空著，也允許放多于一個(gè)球。整

45、數(shù)拆分成若干整數(shù)的和，辦法不一，不同拆分法的總數(shù)叫做拆分?jǐn)?shù)。2.6.1 2.6.1 問題舉例問題舉例 例1：若有1克、2克、3克、4克的砝碼各一枚，問能稱出那幾種重量？有幾種可能方案？109876543274332432 1)1)(1 ()1)(1)(1)(1 (xxxxxxxxxxxxxxxxxxxx2.6.1 2.6.1 問題舉例問題舉例 從右端的母函數(shù)知可稱出從1克到10克，系數(shù)便是方案數(shù)。例如右端有 項(xiàng)，即稱出5克的方案有252x41325同樣，432110243216故稱出6克的方案有2，稱出10克的方案有12.6.1 2.6.1 問題舉例問題舉例 例例2 2：求用：求用1 1分、分

46、、2 2分、分、3 3分的郵票貼出分的郵票貼出不同數(shù)值的方案數(shù)。不同數(shù)值的方案數(shù)。因郵票允許重復(fù)，故母函數(shù)為)1 ( )1)(1 ()(63422xxxxxxxG 以其中為例，其系數(shù)為4，即4拆分成1、2、3之和的拆分?jǐn)?shù)為4，即2231211111142.6.1 2.6.1 問題舉例問題舉例 例例3 3：若有：若有1 1克砝碼克砝碼3 3枚、枚、2 2克砝碼克砝碼4 4枚、枚、4 4克砝碼克砝碼2 2枚的砝碼各一枚，問能稱出那幾種枚的砝碼各一枚，問能稱出那幾種重量？各有幾種方案？重量？各有幾種方案？2.6.1 2.6.1 問題舉例問題舉例1918171615141312111098765432

47、84111098765432848642322233 445555 4433221 )1)(222 222221 ( )1 ( )1)(1 ()(xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxG2.6.1 2.6.1 問題舉例問題舉例 例例4: 4: 整數(shù)整數(shù)n n拆分成拆分成1 1，2 2，3 3，m m的和，的和，并允許重復(fù)，求其母函數(shù)。如若其中并允許重復(fù)，求其母函數(shù)。如若其中m m至少至少出現(xiàn)一次，其母函數(shù)如何？出現(xiàn)一次，其母函數(shù)如何？ 若整數(shù)n拆分成1，2，3，m的和，并允許重復(fù)，其母函數(shù)為：)1 ( )1)(1 ()(24221mmxxxxxxx

48、G2.6.1 2.6.1 問題舉例問題舉例)1 ()1)(1 (1 111111 )1 ( )1)(1 ()(2224221mmmmxxxxxxxxxxxxxG2.6.1 2.6.1 問題舉例問題舉例 若拆分中m至少出現(xiàn)一次，其母函數(shù)為：)1 ()1)(1 ( )( )1)(1 ()(224222mmmmxxxxxxxxxxxG2.6.1 2.6.1 問題舉例問題舉例顯然有) 162( )1 ()1)(1 (1 )1 ()1)(1 (1 )(1222mmxxxxxxxG等式(2-6-1)的組合意義：即整數(shù)n拆分成1到m的和的拆分?jǐn)?shù)減去拆分成1到m-1的和的拆分?jǐn)?shù)，即為至少出現(xiàn)一個(gè)m的拆分?jǐn)?shù)。2

49、.6.1 2.6.1 問題舉例問題舉例 例例1 1：若有：若有1 1、2 2、4 4、8 8、1616、3232克的砝克的砝碼各一枚，問能稱出那幾種重量？有幾種碼各一枚，問能稱出那幾種重量？有幾種可能方案？可能方案？6306326432641632816482423216842)1 (11 111111111111 )1 ( )1)(1)(1)(1)(1 ( )(kkxxxxxxxxxxxxxxxxxxxxxxxxxG2.6.1 2.6.1 問題舉例問題舉例 從母函數(shù)可以得知，用這些砝碼可以稱出從1克到63克的重量，而且辦法都是唯一的。 這問題可以推廣到證明任一十進(jìn)制數(shù)n，可表示為0 , 10

50、 ,20kaankkkk而且是唯一的。2.7 2.7 指數(shù)型母函數(shù)指數(shù)型母函數(shù) 2.7.1 2.7.1 問題提出問題提出 設(shè)有n個(gè)元素，其中元素 重復(fù)了 次，元素 重復(fù)了 次， 重復(fù)了 次， 從中取r個(gè)排列，求不同的排列數(shù)1a1n2a2nkaknknnnn21 假設(shè) ，則是一般的排列問題。121knnn2.7.1 2.7.1 問題提出問題提出 現(xiàn)在由于出現(xiàn)重復(fù)，故不同的排列計(jì)數(shù)便比較復(fù)雜。先考慮 個(gè)元素的全排列，假設(shè) 個(gè)元素沒有完全一樣的元素，則應(yīng)有 種排列。若考慮 個(gè)元素 的全排列數(shù)為 ，則真正不同的排列數(shù)為nn! ninia!in!21knnnn2.7.2 2.7.2 解的分析解的分析 先

51、討論一個(gè)具體問題：若有8個(gè)元素，其中設(shè) 重復(fù)3次， 重復(fù)2次， 重復(fù)3次。從中取r個(gè)組合，其組合數(shù)為 ，則序列 的母函數(shù)為1a3a2arc76543210,cccccccc876543232543232232369109631 )1 ( )23321 ( )1)(1)(1 ()(xxxxxxxxxxxxxxxxxxxxxxxxxG2.7.2 2.7.2 解的分析解的分析 從 的系數(shù)可知，這8個(gè)元素中取4個(gè)組合，其組合數(shù)為10。這10個(gè)組合可從下面展開式中得到4x)1 ( )()( )()(1 )1)(1)(1 ( 3323322312221231221221312221212133233222

52、31211xxxxxxxxxxxxxxxxxxxxxxxxxxxx2.7.2 2.7.2 解的分析解的分析 ) () () ()1 ( 12221331322132213312322232123213323313323223132232132122122131333231222121321xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx承前頁2.7.2 2.7.2 解的分析解的分析其中4次方項(xiàng)有)272( 222133132213221331232223212321332331xxxxxxxxxxxxxxxxxxxxxxx(2-7-2)表

53、達(dá)了從8個(gè)元素( 各3個(gè), 2個(gè))中取4個(gè)的組合。例如 為一個(gè) ，3個(gè) 的組合， 為兩個(gè) ，兩個(gè) 的組合，以此類推。31,aa2a331xx1a3a2321xx3a1a2.7.2 2.7.2 解的分析解的分析 若研究從中取4個(gè)的不同排列總數(shù)，以 對(duì)應(yīng)的兩個(gè)兩個(gè)的不同排列為例，其不同排列數(shù)為2321xx6! 2 ! 2! 4即 六種。同樣，1個(gè) 3個(gè) 的不同排列數(shù)為 ,3311aaaa,1331aaaa,3131aaaa,1313aaaa,1133aaaa,3113aaaa1a3a4! 3! 42.7.2 2.7.2 解的分析解的分析 即 以此類推。故從(2-7-2)式可得問題的解，其不同的排列

54、數(shù)為,3331aaaa,1333aaaa,3133aaaa,3313aaaa70361816! 3 ! 2 ! 2! 3! 23! 33! 2! 24! 4)! 23! 2 ! 23! 34( ! 4)! 2 ! 21! 1 ! 31! 1 ! 2 ! 11! 1 ! 1 ! 21 ! 1 ! 31! 2 ! 21! 2 ! 1 ! 11! 2 ! 21! 3 ! 11! 3 ! 11( ! 42.7.3 2.7.3 指數(shù)型母函數(shù)指數(shù)型母函數(shù) 為了便于計(jì)算，利用上述特點(diǎn)，形式地引進(jìn)函數(shù))! 3! 2! 11 ( )! 2! 11)(! 3! 2! 11 ()(32232xxxxxxxxxGe2

55、.7.3 2.7.3 指數(shù)型母函數(shù)指數(shù)型母函數(shù) )372( 7217287235 121712353142931 )61211 ( )1211256722(1 )(8765432325432xxxxxxxxxxxxxxxxxGe承上頁2.7.3 2.7.3 指數(shù)型母函數(shù)指數(shù)型母函數(shù) 從(2-7-3)式計(jì)算結(jié)果可以得出：取一個(gè)的排列數(shù)為 ，取兩個(gè)的排列數(shù)為 取3個(gè)的排列數(shù)為 ，取4個(gè)的排列數(shù)為 ，如此等等。把(2-7-3)式改寫成下面形式便一目了然了。3, 92/92283/14! 37012/35! 4)472( ! 8560! 7560! 6350 ! 5170! 470! 328! 291

56、!31! )(8765432xxxxxxxxxGe2.7.3 2.7.3 指數(shù)型母函數(shù)指數(shù)型母函數(shù) 定義：對(duì)于序列 ，函數(shù),210aaakkexkaxaxaxaaxG! ! 3! 21! )(332210稱為是序列 得指數(shù)型母函數(shù),210aaa2.7.3 2.7.3 指數(shù)型母函數(shù)指數(shù)型母函數(shù) 綜合上述可得如下兩個(gè)結(jié)論： (a) 若元素 有 個(gè)，元素 有 個(gè)，元素 有 個(gè)，由此；組成的n個(gè)元素的排列，不同的排列總數(shù)為1a1n2a2nknka!21knnnn其中knnnn212.7.3 2.7.3 指數(shù)型母函數(shù)指數(shù)型母函數(shù) (b) 若元素 有 個(gè)，元素 有 個(gè)，元素 有 個(gè)，由此；組成的n個(gè)元素中

57、取r個(gè)排列，設(shè)其不同的排列數(shù)為 。則序列 的指數(shù)型母函數(shù)為1a1n2a2nknkarpnppp,10)! 21!1 ( )! 21!1 ( )! 21!1 ( )(2221221knnnenxxxnxxxnxxxxGk2.7.3 2.7.3 指數(shù)型母函數(shù)指數(shù)型母函數(shù) 與(2)中所用的方法相比，可以看出指數(shù)型母函數(shù)在解決有重復(fù)元素的排列時(shí)的優(yōu)越性。2.7.4 2.7.4 舉例舉例 例1：求由兩個(gè) ，1個(gè) ，2個(gè) 組成的不同排列總數(shù)。abc 根據(jù)結(jié)論一，不同的排列總數(shù)為30! 1 ! 2 ! 2! 5n2.7.4 2.7.4 舉例舉例 例例2 2：由：由1 1，2 2，3 3，4 4四個(gè)數(shù)字組成的

58、五四個(gè)數(shù)字組成的五位數(shù)中，要求數(shù)位數(shù)中，要求數(shù)1 1出現(xiàn)次數(shù)不超過出現(xiàn)次數(shù)不超過2 2次，但次，但不能不出現(xiàn)；不能不出現(xiàn)； 2 2出現(xiàn)次數(shù)不超過出現(xiàn)次數(shù)不超過1 1次；次； 3 3出現(xiàn)次數(shù)可達(dá)出現(xiàn)次數(shù)可達(dá)3 3次，也可以不出現(xiàn)；次，也可以不出現(xiàn)；4 4出現(xiàn)出現(xiàn)次數(shù)為偶數(shù)。求滿足上述條件的數(shù)的個(gè)數(shù)。次數(shù)為偶數(shù)。求滿足上述條件的數(shù)的個(gè)數(shù)。2.7.4 2.7.4 舉例舉例 設(shè)滿足上述條件的r位數(shù)為 ，序列 的指數(shù)型母函數(shù)為ra1021,aaa)1444881247 321)(2123()! 4! 21 ( )! 3! 2! 11)(1)(! 21!( )(7654323242322xxxxxxxxx

59、xxxxxxxxxxGe2.7.4 2.7.4 舉例舉例1098765432288148128814817 4843244338325xxxxxxxxxx!1012600! 97650! 8140! 71785 ! 6645! 5215! 464! 318! 25! 11098765432xxxxxxxxxx由此可見滿足條件的5位數(shù)共215個(gè)。2.7.4 2.7.4 舉例舉例例例3: 求求1，3，5，7，9五個(gè)數(shù)字組成的五個(gè)數(shù)字組成的 位位數(shù)的個(gè)數(shù)，要求其中數(shù)的個(gè)數(shù)，要求其中3，7出現(xiàn)的次數(shù)為偶出現(xiàn)的次數(shù)為偶數(shù)，其他數(shù)，其他1，5，9出現(xiàn)次數(shù)不加限制。出現(xiàn)次數(shù)不加限制。設(shè)滿足條件的設(shè)滿足條件的

60、 位的個(gè)數(shù)為位的個(gè)數(shù)為 ，則序列，則序列 對(duì)應(yīng)的指數(shù)型母函數(shù)為對(duì)應(yīng)的指數(shù)型母函數(shù)為rnra,321aaa)! 3! 21 ()! 4! 21 ()(32242xxxxxxGe2.7.4 2.7.4 舉例舉例由于),! 3! 2132xxxex).(21! 4! 21 42xxeexxxxxxxxeeeeeeexG32232)2(41 )(41)(2.7.4 2.7.4 舉例舉例).1325(41 .!) 1325(41)!32!5(41)2(41000035nnnnnnnnnnnnnnnxxxanxnxnxxneee2.8 2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例母函數(shù)和遞推關(guān)系應(yīng)用舉例 2.8 2.