1、第四章生成函數(shù)1.求以下數(shù)列的生成函數(shù):10,1,16,81,n4,解: Gk4=x(1 11x 11x23X )2解：G(1x5n 3531(1 x)431,0,2,0,3,0,4,0,解：A(x)=1+2x2+3x4+4x6+=2.1 x41,k,k2,k3,解：A(x)=1+kx+k1 kx2.求以下和式：114+24+ n4解：由上面第一題可知，n4生成函數(shù)為x(1 11x 11x2 x3)A(x)= i丿kakX,k 0(1 x5此處 ak=k4.令 bn=14+24+n4,那么 bn=kak ,由性質(zhì)3即得數(shù)列bn的生0成函數(shù)為 B(x)=bnxnn 01比擬等式兩邊xn的系數(shù)，便

2、得n 1 514+24+n4=bn=1n(n 3021 2+2 3+ +n(n+1)31)(6nA = (xx11x2311xx4)i1111解： n(n+1)的生成函數(shù)為A(x)=29n n 1)2x =(1 x)3=knakk 0n_A(x)_ 2x_=2xnkakX0,此處 ak= n(n+1).令bn=1 2+2 3+n(n+1)，那么bn=ak .由性質(zhì)3即得數(shù)列bn的生成函數(shù)為B(x)= bnxn 01 x (1 x)比擬等式兩邊xn的系數(shù)，便得n(n 1)(n 2)3n 21 2+2 3+n(n +1)= bn= 2n 13.利用生成函數(shù)求解以下遞推關(guān)系：f(n) 7f( n 1

3、) 12f( n 2)；f (0)2, f(1) 7；解：令 A(x)= f(n)xnn 0那么有 A(x)-f(0)-f(1)x=nf (n)xn =2(7 f( n 1) 12f (n22)x=7xf(n)xn 112x2f(n )xnn 0=7x(A(x)-f(0)-12x 2A(x).將f(0)=2，f(1)=7代入上式并整理，得1 1A(x) 12 7x7x 12x2 f(n)f (0)3f( n 1)01 3x 1 4x5 3n(3n 4'0).解：令A(yù)(x)=f (n)xn，0那么有A(x)-f(O)=(3f (nn 11) 5 3n)xn =3xf (n)x015xn=

4、3xA(x)+15x1 3x15x3x)22f( n 1)0, f(1) 1f(n 2)A(x)=(1f (n)3 i 丿f (0)解：令A(yù)(x)=f (n)xn，0那么有A(x)-f(0)-f(1)x=(2 f(n 1) f (n 2)xn=2xn 2=2x(A(x)-f(0)+x 2A(x).f(n )xnf(n )xn0將f(0)=0, f(1)=1代入上式并整理，得A(x)1 2x4 3x4.設(shè)序列an的生成函數(shù)為：(1 x)(1 x x3),求序列bn的生成函數(shù)解：由 b°a。，ba a。但boa°,biain> bnanan 1 > 得bkk 0an

5、，所以 A(x)=B(x)1 x4 3x由此得B(x)=(1-x)A(x)=，亦即序列 n的生成函數(shù)。5. 生成函數(shù)3 9x 2，求對應(yīng)的序列an.1 x 56x的 3 9x5211解：2= 52 -1 x 56x 8x 1 7x 11 8x 1 7x所以審=-5 8n-2 (-7)n.6. 有紅黃,藍(lán)白球各兩個，綠，紫,黑球各3個，從中取出10個球,試問有多少種 不同的取法？解：Mr=My=Mb=Mw=0,1,2，Mg=Mp=Mh=0,1,2,3，所以該取法的個數(shù)為 (1+x+x2)4(1+x+x2+x3)3 中 x10 的系數(shù)，為 678.7. 口袋中有白球5個，紅球3個,黑球2個，每次從

6、中取5個，問有多少種取法？解：Mw=0,1,2,3,4,5，Mr=0,1,2,3，Mb=0,1,2，所以從中取 5 個的取法個 數(shù)為(1+x+x2)(1+x+x2+x3) (1+x+x2+x3+x4+x5)中 x5 的系數(shù)，為 12。8. 求1,3,5,7,9這5個數(shù)字組成的n位數(shù)個數(shù),要求其中3和7出現(xiàn)的次數(shù)位 偶數(shù),其它數(shù)字出現(xiàn)的次數(shù)無限制.解：M1=M5 =M9=0,1,2,3,，M3 =M7=0,2,4, 該排列的生成函數(shù)為24211(1 .)2(1 x .)3 =丄(ex+e-x)2e3x=1 (e5x+e3x+ex)2!4!2!441“ ncnQ八X=_(5231)-4 n 0n!

7、1所以?=丄(5n2 3n 1).49.用3個1,2個2,5個3這十個數(shù)字能構(gòu)成多少個偶的四位數(shù)？解：因要組成偶的四位數(shù)，所以個位必為 2,然后確定其它三位的排列即可M1=0,1,2,3，M2 =0,1，M3=0,1,2,3,4,5，故生成函數(shù)為232xxx(1x)(1 x)(1 x2!3!2!5x-).5!3其中x的系數(shù)為20,即可以組成20個偶的四位數(shù)3!10. 求由A,B,C,D組成的允許重復(fù)的排列中 AB至少出現(xiàn)一次的排列數(shù)目 解：可把AB看作一個整體，用E表示，那么Ma=Mb=Mc=Md=0,1,2,，Me=1,2,2 2 ,x4 x故有(1 x) (x) =e(4x)(e(x)-1

8、)=e(5x)-e(4x)=5n-4n.2! 2!11. 從n a, n b,n c中取出n個字母，要求a的個數(shù)為3的倍數(shù),b的個數(shù)是 偶數(shù)，問有多少種取法？解：由題意可知，Ma=0,3,6,，Mb=Mc=0,1,2,，該取法的生成函數(shù)為4(1+X3+X6+.)(1+X+X2+X3)2= ( )21 x 1 X12. 把正整數(shù)8寫成三個非負(fù)整數(shù)之和，要求 nK 3,n2W 3,ns< 6.問有多少種不同的方案?解:由題意可知，Mi=M2=0,1,2,3 , M3=0,1,2,3,6,(1+x+x2+x3)2(1+x+x2+x3+ +X6)/1 X 21 X4 7 , 8, c 11 15

9、、1=()=(1-2x -x +x +2x -x ) 1 X 1 X那么生成函數(shù)為8 8 2符合題意的方案數(shù)為X的系數(shù)'為2(1 x)34 2221 21 =13.213. 在一個程序設(shè)計(jì)課程里，每個學(xué)生的每個任務(wù)最多可以運(yùn)行10次.教員發(fā)現(xiàn)某個任務(wù)共運(yùn)行了 38次.設(shè)有15名學(xué)生，每個學(xué)生對這一任務(wù)至少做一 次.求觀察到的總次數(shù)的組合數(shù).解：M1=M2 = =M15=1,2,3,10，生成函數(shù)為(x+x2+x3+x10)15-15 Jx1015(X+X +x + +X )-X ( 1X3715271517其中x38的系數(shù)為1411421414.用1角、2角、3角的郵票可貼出多少種不同

10、數(shù)值的郵資？ 解：生成函數(shù)為 G(x)=(1+x+x2+)(1+x2+x4+)(1+x3+x6+)11x31 1.1 X 1 X215. 設(shè)多重集合S e1,e2,e3,234n組合數(shù)，分別求數(shù)列 an生成函數(shù).1每個e出現(xiàn)奇數(shù)次i = 1,2,3,4；2每個e出現(xiàn)4的倍數(shù)次i = 1,2,3,4;3q出現(xiàn)3或7次,e3出現(xiàn)2,6或8次；4每個e至少出現(xiàn)6次i = 1,2,3,4；n 3Xn解：1由題意知，M1=M2=M3=M4=1,3,5,，故該組合數(shù)序列的生成函數(shù)為(x+x2+x3+ )4=x4 = X4(1 X)2由題意知，M仁M2=M3=M4=0,4,8，故該組合數(shù)序列的生成函 1數(shù)為

11、(1+x4+x8+)4=匚7 .(1 X)3由題意知,M1=3,7，M2= M4=0,1,2,，M3=2,6,8故該組合數(shù)序列的生成函數(shù)為n 1f 3t 726822 / 59111315n(x +x )(x +x +x )(1+x+x +)=(x +2x +x +x +x ) X .n 01w的系數(shù)為n 5 1n 9 1n 11 1n 13 1n 15 12=6n-56111114由題意知，Mi=M2=M3=M4=6,7,8,，故該組合數(shù)序列的生成函數(shù)為(x6+x7+x8+)4=x24 (1一 X24X)n 3 nn 324 nX =Xn nonn 21Xn的系數(shù)為e2,an表示集合S滿足以

12、下條件316. 設(shè)多重集合S 的n排列1234S的每個元素出現(xiàn)偶數(shù)次；S的每個元素至少出現(xiàn)4次；S的每個元素至多出現(xiàn)i次i=1,2,k；S的每個元素至少出現(xiàn)i次i=1,2,k；解：1由題意知，M1=M2=M3=Mk=0,2,4,，故該組合數(shù)序列的生成4k函數(shù)為12!X k e(x) e( x) .)=4!2由題意知，M 1=M2=M3=M k=4,5,6,，故該組合數(shù)序列的生成4 X(5X)k =2X(e(x)1 3X4!5!2!3!kk=(-1)ii 0.e(kii)x)e(1)e(2)ki kn 0(i 0(1)i .i(k i)n1e(2)函數(shù)為k i k nan( 1) . (k i)

13、 1 e(2)i 0i3由題意知,M1=M2=M3=2i成函數(shù)為(1 X .-)k.2!i !4由題意知，M1=M2=M3hii 1生成函數(shù)為(-X.)k.i! (i 1)!e(3)ine(3) J n!e(3)iMk=0,1,2,i，故該組合數(shù)序列的生Mk=i,i+1,i+2,，故該組合數(shù)序列的17. 用生成函數(shù)法證明以下等式:n 2 n 1 n n1 2rr r r 2證明:(1+x)n+2=(1+x)n (1+x)2=(1+2x+x2) (1+x) n=x2(1+x)n+2(1+x)n+1-(1+x)nn 2nn 1n比照左右兩邊X的系數(shù)，左邊:，右邊=2rr 2rrn2n1nn整理得：

14、2rrrr 2等式得證.2q ( 1/ q n q j j 0 j r 證明：(1+X)n(1+x)-1q=xq(1+X)n, xr的系數(shù)，n q j qx) ( 1)j(1j 0j比照左右兩邊左邊=(118.nr q因此等式得證設(shè)有砝碼重為解:19.解:20.x)qq(1)jq n q j ，右邊j 01g的3個，重為2g的4個,重為4g的2個，問能稱出多少種重量？各有多少種方案？由題意知,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+4x6+4x

15、7+5x8+5x9+5x10+5x11+4x12+4x13+3x14+3x15+2x16+2x17+x18+x19故共能稱出20種重量，指數(shù)即為重量類型，系數(shù)為方案數(shù).求方程x什2x2+4x3=21的正整數(shù)解的個數(shù).由題目可以看出，(x x3x7(1X1為奇數(shù)，故生成函數(shù)為.)(x2X4X6X4.)(1X2?一115x2x1.)(x4x4.)(18x4xx12.)x8.)X7x (1 x2)2 1 x471-2 2x 22(1 x )227(1 x )x 廠(1 x )?(1 x ) (1-44、3(X72)243(1 x )2x9x11)-(1 x )(x7c 911、2x x )k 0展開

16、式中x21的系數(shù)為20,H 1 4x10x220x3k 22亦即該方程正整數(shù)解的個數(shù)。n 3 n-x 34kx1證明：(1x)H2求H的表達(dá)式.解：H的生成函數(shù)為G1(1 x)H k(1n 2221.數(shù)1,2,3,，9的全排列中，求偶數(shù)在原來位置上，其余都不在原來位置上 的錯排數(shù)目.m(1 x)(1-x)-m=1+mx+m(m 1)2!解：實(shí)際上是1, 3, 5, 7, 9這5個數(shù)的錯排問題，總數(shù)為5! -C(5,1)4!+C(5,2)3!-C(5,3)2!+C(5,4)1!-C(5,5)=44.22. 求整數(shù)n拆分成1,2,m的和,并允許重復(fù)的拆分?jǐn)?shù).如假設(shè)其中m至少 出現(xiàn)1次,試求它的方案

17、數(shù)和生成函數(shù).解：因?yàn)閚拆分成1, 2,，m的和允許重復(fù)，故其生成函數(shù)為G(x)=(1+x+x 2+ )(1+x2+x4+)(1+xm+x2m+)_ 1 1 1=1 x 1 x21 xm假設(shè)要m至少出現(xiàn)1次，那么生成函數(shù)為G1 (x)=(1+x+x 2+ )(1+x2+x 4+ )(xm+x2m+)=丄1 xm=1 x 1 x21 xm即：整數(shù)n拆分成1到m的拆分?jǐn)?shù)，減去n拆分成1到m 1的拆分?jǐn)?shù), 即為拆分成1到m,至少出現(xiàn)一個m的拆分?jǐn)?shù)。23. n個完全相同的球放到 m個有標(biāo)志的盒子，不允許有空盒，問共有多少種 不同的方案？其中mWn.由于不允許有空盒,解：令n個球放到m個有標(biāo)志的盒子的方案數(shù)為 此序列an的生成函數(shù)為2 2 2G(x)=(x+x +)(x+x + )(x+x + )=m(m 1).(m n m