1、第四章 生成函數(shù)1. 求下列數(shù)列的生成函數(shù)：（1）0,1,16,81,n4,解：Gk4=（2）解：=（3）1,0,2,0,3,0,4,0,解：A(x)=1+2x2+3x4+4x6+=（）2.（4）1,k,k2,k3,解：A(x)=1+kx+k2x2+k3x3+=.2. 求下列和式：（1）14+24+n4解：由上面第一題可知，n4生成函數(shù)為A(x)=，此處ak=k4.令bn=14+24+n4，則bn=，由性質(zhì)3即得數(shù)列bn的生成函數(shù)為B(x)= =.比較等式兩邊xn的系數(shù)，便得14+24+n4=bn=（2）1·2+2·3+n(n+1)解： n(n+1)的生成函數(shù)為A(x)=

2、=，此處ak= n(n+1).令bn=1·2+2·3+n(n+1)，則bn=.由性質(zhì)3即得數(shù)列bn的生成函數(shù)為B(x)= =.比較等式兩邊xn的系數(shù)，便得1·2+2·3+n(n+1)= bn=.3. 利用生成函數(shù)求解下列遞推關(guān)系：（1）;解：令A(yù)(x)=則有A(x)-f(0)-f(1)x= =7x(A(x)-f(0)-12x2A(x).將f(0)=2，f(1)=7代入上式并整理，得.（2）;解：令A(yù)(x)=，則有A(x)-f(0)= =3xA(x)+15x·.A(x)= （3）;解：令A(yù)(x)=，則有A(x)-f(0)-f(1)x=2x(A(x

3、)-f(0)+x2A(x).將f(0)=0，f(1)=1代入上式并整理，得. 4. 設(shè)序列的生成函數(shù)為：,但,求序列的生成函數(shù).解：由,得，所以A(x)= .由此得B(x)=(1-x)A(x)= ，亦即序列的生成函數(shù)。5. 已知生成函數(shù),求對(duì)應(yīng)的序列.解：=所以an=-5·8n-2·(-7)n.6. 有紅,黃,藍(lán),白球各兩個(gè),綠,紫,黑球各3個(gè),從中取出10個(gè)球,試問(wèn)有多少種不同的取法？解：Mr=My=Mb=Mw=0,1,2，Mg=Mp=Mh=0,1,2,3，所以該取法的個(gè)數(shù)為(1+x+x2)4(1+x+x2+x3)3中x10的系數(shù)，為678.7. 口袋中有白球5個(gè),紅球3

4、個(gè),黑球2個(gè),每次從中取5個(gè),問(wèn)有多少種取法？解：Mw=0,1,2,3,4,5，Mr=0,1,2,3，Mb=0,1,2，所以從中取5個(gè)的取法個(gè)數(shù)為(1+x+x2)(1+x+x2+x3) (1+x+x2+x3+x4+x5)中x5的系數(shù)，為12。8. 求1,3,5,7,9這5個(gè)數(shù)字組成的n位數(shù)個(gè)數(shù),要求其中3和7出現(xiàn)的次數(shù)位偶數(shù),其它數(shù)字出現(xiàn)的次數(shù)無(wú)限制.解：M1=M5 =M9=0,1,2,3,，M3 =M7=0,2,4,該排列的生成函數(shù)為=(ex+e-x)2e3x=(e5x+e3x+ex)=所以an=.9. 用3個(gè)1,2個(gè)2,5個(gè)3這十個(gè)數(shù)字能構(gòu)成多少個(gè)偶的四位數(shù)？解：因要組成偶的四位數(shù)，所以個(gè)

5、位必為2，然后確定其它三位的排列即可.M1=0,1,2,3，M2 =0,1，M3=0,1,2,3,4,5，故生成函數(shù)為.其中的系數(shù)為20，即可以組成20個(gè)偶的四位數(shù)。10. 求由A,B,C,D組成的允許重復(fù)的排列中AB至少出現(xiàn)一次的排列數(shù)目.解：可把AB看作一個(gè)整體，用E表示，則MA=MB=MC=MD=0,1,2,，ME=1,2,故有=e(4x)(e(x)-1)=e(5x)-e(4x)=5n-4n.11. 從中取出n個(gè)字母,要求a的個(gè)數(shù)為3的倍數(shù),b的個(gè)數(shù)是偶數(shù),問(wèn)有多少種取法?解：由題意可知，Ma=0,3,6,，Mb=Mc=0,1,2,，該取法的生成函數(shù)為(1+x3+x6+)(1+x+x2+

6、x3)2=·12. 把正整數(shù)8寫(xiě)成三個(gè)非負(fù)整數(shù)之和，要求n13,n23,n36.問(wèn)有多少種不同的方案？解：由題意可知，M1=M2 =0,1,2,3，M3=0,1,2,3,6，則生成函數(shù)為(1+x+x2+x3)2(1+x+x2+x3+x6)= ·=(1-2x4-x7+x8+2x11-x15) ·符合題意的方案數(shù)為x8的系數(shù)，為=13.13. 在一個(gè)程序設(shè)計(jì)課程里,每個(gè)學(xué)生的每個(gè)任務(wù)最多可以運(yùn)行10次.教員發(fā)現(xiàn)某個(gè)任務(wù)共運(yùn)行了38次.設(shè)有15名學(xué)生,每個(gè)學(xué)生對(duì)這一任務(wù)至少做一次.求觀(guān)察到的總次數(shù)的組合數(shù).解：M1=M2 =M15=1,2,3,10，生成函數(shù)為(x+x2

7、+x3+x10)15=，其中x38的系數(shù)為。14. 用1角、2角、3角的郵票可貼出多少種不同數(shù)值的郵資？解：生成函數(shù)為G(x)=(1+x+x2+)(1+x2+x4+)(1+x3+x6+)= ·· =1+x+2x2+3x3+4x4+15. 設(shè)多重集合,表示集合滿(mǎn)足下列條件的n組合數(shù),分別求數(shù)列生成函數(shù).（1）每個(gè)出現(xiàn)奇數(shù)次（i1,2,3,4）；（2）每個(gè)出現(xiàn)4的倍數(shù)次i1,2,3,4）；（3）出現(xiàn)3或7次,出現(xiàn)2,6或8次；（4）每個(gè)至少出現(xiàn)6次（i1,2,3,4）；解：（1）由題意知，M1=M2=M3=M4=1,3,5,，故該組合數(shù)序列的生成函數(shù)為(x+x2+x3+)4=x

8、4·= x4·=.Xn的系數(shù)為.（2）由題意知，M1=M2=M3=M4=0,4,8,，故該組合數(shù)序列的生成函數(shù)為(1+x4+x8+)4= .（3）由題意知，M1=3,7，M2= M4=0,1,2,，M3=2,6,8故該組合數(shù)序列的生成函數(shù)為(x3+x7)(x2+x6+x8)(1+x+x2+)2=(x5+2x9+x11+x13+x15) ·.Xn的系數(shù)為6n-56.（4）由題意知，M1=M2=M3=M4=6,7,8,，故該組合數(shù)序列的生成函數(shù)為(x6+x7+x8+)4=x24·= x24·=.Xn的系數(shù)為.16. 設(shè)多重集合,表示集合滿(mǎn)足下列條件

9、的n排列（1）S的每個(gè)元素出現(xiàn)偶數(shù)次；（2）S的每個(gè)元素至少出現(xiàn)4次；（3）S的每個(gè)元素至多出現(xiàn)i次（i=1,2,k）；（4）S的每個(gè)元素至少出現(xiàn)i次（i=1,2,k）；解：（1）由題意知，M1=M2=M3=Mk=0,2,4,，故該組合數(shù)序列的生成函數(shù)為=.（2）由題意知，M1=M2=M3=Mk=4,5,6,，故該組合數(shù)序列的生成函數(shù)為=(-1)i= （3）由題意知，M1=M2=M3=Mk=0,1,2,i，故該組合數(shù)序列的生成函數(shù)為.（4）由題意知，M1=M2=M3=Mk=i,i+1,i+2,，故該組合數(shù)序列的生成函數(shù)為.17. 用生成函數(shù)法證明下列等式：（1）證明：(1+x)n+2=(1+x

10、)n·(1+x)2=(1+2x+x2) (1+x)n=x2(1+x)n+2(1+x)n+1-(1+x)n對(duì)比左右兩邊xr的系數(shù)，左邊=，右邊=，整理得：.等式得證.（2）證明：(1+x)n(1+x)-1q=xq(1+x)n，對(duì)比左右兩邊xr的系數(shù)，左邊=，右邊=，因此等式得證.18. 設(shè)有砝碼重為1g的3個(gè),重為2g的4個(gè),重為4g的2個(gè),問(wèn)能稱(chēng)出多少種重量？各有多少種方案？ 解：由題意知，M1=0,1,2,3，M2=0,1,2,3,4，M4=0,1,2，故生成函數(shù)為(1+x+x2+x3)(1 +x2+x4+x6+x8)(1+x4+x8)=1+x+2x2+2x3+3x4+3x5+4x

11、6+4x7+5x8+5x9+5x10+5x11+4x12+4x13+3x14+3x15+2x16+2x17+x18+x19故共能稱(chēng)出20種重量，指數(shù)即為重量類(lèi)型，系數(shù)為方案數(shù).19. 求方程x1+2x2+4x3=21的正整數(shù)解的個(gè)數(shù).解：由題目可以看出，x1為奇數(shù)，故生成函數(shù)為展開(kāi)式中x21的系數(shù)為20，亦即該方程正整數(shù)解的個(gè)數(shù)。20.（1）證明：（2）求H的表達(dá)式.解：H的生成函數(shù)為=，所以.21. 數(shù)1,2,3, ,9的全排列中,求偶數(shù)在原來(lái)位置上,其余都不在原來(lái)位置上的錯(cuò)排數(shù)目.解：實(shí)際上是1，3，5，7，9這5個(gè)數(shù)的錯(cuò)排問(wèn)題，總數(shù)為5！-C(5,1)4!+C(5,2)3!-C(5,3)

12、2!+C(5,4)1!-C(5,5)=44.22. 求整數(shù)n拆分成1,2,m的和,并允許重復(fù)的拆分?jǐn)?shù).如若其中m至少出現(xiàn)1次,試求它的方案數(shù)和生成函數(shù).解：因?yàn)閚拆分成1，2，m的和允許重復(fù)，故其生成函數(shù)為G(x)=(1+x+x2+)(1+x2+x4+)(1+xm+x2m+)=··· 若要m至少出現(xiàn)1次，則生成函數(shù)為G1(x)=(1+x+x2+)(1+x2+x4+)(xm+x2m+)= ··· 即：整數(shù)n拆分成1到m的拆分?jǐn)?shù)，減去n拆分成1到m1的拆分?jǐn)?shù)，即為拆分成1到m，至少出現(xiàn)一個(gè)m的拆分?jǐn)?shù)。23. n個(gè)完全相同的球放到m個(gè)有標(biāo)志的盒子,不允許有空盒,問(wèn)共有多少種不同的方案？其中mn.解：令n個(gè)球放到m個(gè)有標(biāo)志的盒子的方案數(shù)為an，由于不允許有空盒，因此序列an的生成函數(shù)為G(x)=(x+x2+)(x