组合数学答案

1、精品文档2.1求序列 0 ，1， 8， 27， n3 的母函数。解：G x a0 a1 x a2 x 2a3 x3an x nG x 0 x 8x227 x3n3 xnann 3an 1n31an4an 16an 2 4an 3an 40左右同乘再连加：x 4 : a44a36a24a1a00x 5 : a54a46a34a2a10x n1 : an 14an 26an 34an 4an 50x n:an4an 16an 24an 3an 4036 20x 6 x2母函数： G x4x 12.2已知序列 33 , 43 , n3 3, ，求母函数。解： Q1的第 k 项为： ( nk1n 1

2、)，对于本题， n=4，(1x)n母函数为：1(1 x)42.3 已知母函数 G（X） =378 x2,求序列an 3 x54 x1解：G（X）=3 78x=AB9x)(16x)9x)(16x)(1(1从而有：AB 3A76 A9B78B4G（X）=749x)(16x)(1G（X）=7(1 9x 92 x 293 x 3) -4 (1(-6)x(-6) 2 x 2(6) 3 x3)。1欢迎下载精品文档an =7* 9n4 * ( 6) n2.4 已知母函数39x，求对应的序列an。1x56x2解：母函数为 G (x)39x39x1x56 x2(17x)(18x)令 G(x)AB17x18xA(

3、18x)B(17x)39xAB38A+7B=9解得： A=2B=1所以 G(x)1212*(7x) i(8x) i7x18xi0i0an2*( 7)n8n2.5 设 GnF2nn 是第 n 个Fibonacci3Gn 20，其中 F数。证明： G n G n 1n=2， 3， 4 。求 G0 ,G1 , G 2 , 的母函数。解：设 H ( x)G0G1 xG2 x 2G3 x 3，则H ( x) G0G1xG 2 x 2G3 x3G 4 x 4 3xH (x)3G 0 x3G1 x23G2 x33G3 x 4 x 2 H (x)G0 x 2G1 x3G 2 x4 - +，得：1 3xx2Hx

4、)G0G xGx(130又已知GnF2 n ，则G0F00， G1F21所以， H ( x)xx13xx2( 35x)( 35x)22设 H ( x)AB，则可列出方程组：3535x22x。2欢迎下载精品文档AB1535A103535A0352B52B10H ( x)AB35353535)(1x)(2(2)(1x)2ii2( 3(3525 x)55 x)5i 05i 025(325 ) i(35 )ixi5 i022. 61020340Q G(x)=1+0*x+2* x2 +0* x3 +3* x4 +0* x3 +0* x5 +4* x6 +=1+2x2 +3 x4 +4 x6 +x2 G(

5、x)=x2 +2 x4 +3x6 +1- x2 *G x =1+ x2 + x4 + x6 +1- x2 *G x = (2e2a )1jij1 x2v jvsj svjvvjv s js1G x =(1 x2 )22.7G 1 2 x23x44x6. (n 1)x2n. (1x2 )G ,(1x2 ) 2 GG 12x23x44x6.(n1)x2n.(1)2Gx22x43x64x8.2 n(n1)x2 n 2.(2)x(n) x1-2Gx2G 1x2x4x6.(n)x2n.(1x2 )G1x2n1x2(1x2 )2 G1x2 n2.81101010.20-10-10-1.。3欢迎下载精品文档

6、31-11-11-11G (x)1 x2x4x6.x2 n.1x2 n1x22G (x)( x1x3x5.x2n 1.)x(1 x2 n )1 x23121x2 n1x2. 9G=1+3x+6x2 +10 x3 +Cn+22xn +11-xG=1+2x+3x2 +4 x3 +n+1xn +2 1- x2 G=1+x+x2 + x3 + xn +3(1x)3 G=1QG=1+3x+623n+10 x +x+Cn+2 2x +xG= x+323x+ 6 x+x2 G=x2 + 3 x3 +1-x G=1+2x+3x2 +4 x3 + + n+1 xn + 1- x2 G=1+x+x2 + x3 +

7、 + xn +(1x)3 G=(1-x)(1-x)(1-x)G(1x)3 G=12.10H 1 4x 10x220x3n3x n3a (1 x) HGn2xnn 02(b)Ha H14x 10x 220x3n 3x n3xHx4x 210x3n23xn。4欢迎下载精品文档- ，得(1x) H13x6x 210x3n3n 2x n33由组合的性质nn 1n1，所以rrr1n 3n 2n2332那么， (1x) HGn2xn，得证。n 02（ b）设 B(x)1212x3x 24x3( n1) xn， 对应的序(1x)B列为 b0 , b1 ,b2,bn , 。根据（ a），得 G 1 3x6x

8、210x3n3n2x n，33k设 G 对应的序列为 g0 , g1, g2, g n ,，则 gkbi，根据母函数i0性质有，G ( x)B( x)13 ，那么，根据（a），HG14 。1x(1x)(1x)(1x)2.11 2an xn1 4 xL2nL,证明(1 3x 3x23)G是an(n 1) , G(n 1) xxn0一个多项式，并求母函数G。解：由题知： anan-1(n+1) 2n22n1(1)an-1an-22(n1)1=2n1(2)(1)-(2) 得：an2an-1an22(3)an-12an-2an 32(4)(3)-(4)an3an-13a n 2an30(5)(5) 式

9、即为 an 的递推关系。所以序列 an 的特征多项式为：。5欢迎下载精品文档C(x)=x 33x 23x 1又母函数可表示为G(x)P(x), 其中 R(x)=x 3C( 1),C(x)为序列 an的特征多项式R(x)xR(x)=x3C(13(13313x3x2x3)= xx3x21)xx因此 (13x3x 2x3 )G(x)P(x) ， P(x) 是最高项次数不超过2的多项式 ，即证。G( x)P(x)P(x)P(x)ABCR(x)31(1 x) 31x(1x) 2(1x) 3x)C(x其中 a01,a14,a 29ABC1解方程组：A2B3C4解得： A0,B1,C2A3B6C9所以 G(

10、x)21x1(1x) 3(1x) 2(1x) 3n1k 2 ,1x( n1) 2 xn , 求序列 a n的母函数。2.12已知 ank1(1x) 3n 0解：设： bn( n1) 2 , B(x)( n 1) 2 xnn0k1a kbll1由母函数的性质3得：B(x)/(1 - x)A(x)又B(x)1x(n1) 2 x n(1x) 3n 0A(x)1x(1x) 4n 1,122.13已知 ank34xx(n1)3 xn , 求序列 an 的母函数。k 1(1x)4n 0解：。6欢迎下载精品文档1: a013x : a11323 xn : an1323L(n1)3-Gx=(1xx2L)23

11、x(1xx2L )33 x(1 xx2L )(1)(123 x33 x2L)1x14xx2(n3nQx) 41) x ,(1n0G(X)14xx2,(1x)52.14pnx22xx11p0 , p1x2x 25x312xx2xx2x2x32x 2x32x 24 x32x 45x32x 45x310 x45x5p00, p112pn。7欢迎下载精品文档G xxx212x(1 2xx 2 )G xxG x2xG xx 2G x x(G xx)2xG xx2 G x0解： (G xa1 xa0 )2xG xx2 G x 0x n :an2an 1an 20x n 1 :an 12an 2an 30x

12、 2 :a2 2a1a00因而：递推关系为：an 2an 1 an 202.15 已知 a 的母函数为12，求序列 a 的递推关系，并求 a ,a.n1x xn01解：111 x x2x2x 1c1= -1 ，c2=1则其特征多项式为： C（x）=x2-x+1与其对应的递推关系为：an-a n-1 +an-2=01AB1xx21 13i x 113i x22A(1 13i x)B(113i x)12211113i3iAB22令13i ，13i2211x2A(1x2 x2L )B(1x2 x2L )xa0AB1a1AB12.16用数学归纳法证明序列mm 1m2mn,m,.,.mmm。8欢迎下载精

13、品文档的母函数为(1x)m 1解： 当 m=1时， 1,2,3,.,1n,. 的母函数就等于1111G ( x)12x3x2.1nxn ,.11111 2x 3x2. ( n 1)xn.(1x) 2假设当 m=k时成立，即Gk ( x)kk1xk2x2.k nxn ,. (1 x) k 1（1）kkkk当 m=k+1时Gk 1kk 1k2knx) k 1 （2）(x)kxx2 .xn ,. (1kkkrr 1nn1kal ，bk 为因为.rr，所以（ 2）里的 bkrr1l 0（2）对应的序列， al 为（ 1）对应的序列。所以由性质 3 得Gk 1 ( x)Gk ( x) / (1 x)Gk

14、 1 ( x)(1 x) k 1 / (1 x)(1 x) k 2所以命题得证2n+2.17 ：已知 G=1+2X+3X+（n+1）x2-4n，证明 (1) G=（1-X） =X(2) G 2=Xn, 其中 an=，(3) a n=C(n+3,3),n0.1.2.3.解：设 T=x+x2+x3+x4. =x/(1-x)2n+=1/(1-X)2T=1+2X+3X+（n+1）x=G2-4，所以 G =（1-X）22n2n+ ）又因为 G =（ 1+2X+3X+（ n+1）x+ ）（1+2X+3X+（n+1）x=G1× G2所以在 G2中 xn 的系数由 (n+1)部分组成：。9欢迎下载精

15、品文档如果 G1中取的因子为 xk 那么 G2中只能去 Xn-k , 只有这样 G1× G2后才能得出xn ，所以 K从 0 取到 n，一共有 (n+1) 部分组成，当 K 取 0 时 G1因子的系数为（K+1），G2因子的系数为 (n-k+1) ，乘后的系数为（ K+1）× (n-k+1) 。所以 G2=Xn ，an=所以（ 2）得证。现在证（ 3），用数学归纳法：1） a0 = C(0+3,3)=12）假设 an=C(n+3,3) 成立，即 an= C(n+3,3)3）证明 an+1=C(n+1+3,3) 成立，a n+1=1*(n+1+1-0)+2*(n+1+1-1)

16、+ 3*(n+1+1-2)+ 4*(n+1+1-3)(n+1+1)*(1)=1*(n+2)+2*(n+1)+3*(n)+(n+2)*1=1*(n+1)+1+2*(n)+2+3*(n-1)+3(n+1)(1)+(n+1)+ (n+2)*1=1*(n+1)+ 2*(n) +3*(n-1). (n+1)(1)+1+2+3+(n+1)+(n+2)=+1+2+3+(n+1)+(n+2)=an += C(n+3,3)+C(n+3,2)= C(n+4,3)所以（ 3）得证。因为 an=C(n+3,3),n0.1.2.3 ，又根据（ 2）。所以（ 1）得证。2.18用母函数法求下列递推关系的一般解 a n -

17、6a n 1+8an 2 =0解 : 设 G(x)=a 0 +a1 x+a2 x 2 +a3 x 3 +。10欢迎下载精品文档-6xG(x)= -6a0 x-6a 1 x 2 -6a 2 x 3 -8x 2 G(x)=8a0 x 2 +8a1 x 3 +相加得G(x)=a0 +(a 1 -6a 0 )x/1-6x+8x2设 p(x)=a0 +(a 1 -6a 0 )x, 由于 p(x)/r(x) 是有理分式 , 多项式 p(x) 的次方低于 r(x) 的次方 , 则 p(x)/r(x) 可化为部分式来表示 , 且表示式是唯一的 .则 G(x)=p(x)/1-6x+8x2 =(A/1-2x) +

18、(B/1-4x)=A(1+2x+(2x)2 +(2x) 3 + )+B(1+4x+(4x) 2 +(4x) 3 + )则一般通解为nna n =A*2 +B*4 . a n +14an 1 +49an 2 =0解 : 设 G(x)=a 0 +a1 x+a 2 x 2 +a3 x 3 +14xG(x)= 14a0 x+a1 x 2 +a2 x 3 +49x 2 G(x)=49a0 x 2 +49a2 x 3 +相加得 ( 同上题 ) G(x)=p(x)/1+14x+49x2 =(A/1-7x) +(B/(1-7x)2 )G(x)=A(1+7x+(7x)2 +)+B(1+2(7x)+3(7x)2

19、+)则一般通解为 : a n =A*7n +B*n*7 nan -9a n 2 =0解: 设 G(x)=a 0 +a1 x+a 2 x 2 +a3 x 3 +-9x 2 G(x)=-9a0 x 2 -9a 1 x 3 -同上题,相加得:。11欢迎下载精品文档G(x)=(a 0 +a1 x)/(1-9x2 )=p(x)/1-9x2 =(A/1-3x)+(B/(1+3x)G(x)=A(1+3x+(3x) 2 +(3x) 3 + )+B(1+(-3x)+(-3x)2 + ): a n =A*3 n +B*(-3) na n -6a n 1 -7a n 2 =0:G(x)=a 0 +a1 x+a 2

20、x 2 +a3 x 3 +-6xG(x)= -6a0 x-6a 1 x 2 -6a 2 x 3 +-7x2 G(x)= -7a 0 x 2 -7a 1 x 3 +,G(x)=(a0 +a1 x-6a 0 x)/(1-6x-7x2 )=A/(1-7x)+B/(1+x)=A(1+7x+(7x) 2 +)+B(1+x+x 2 +): a n =A*7 n +B*1n an -12a n 1 +36an 2 =0:G(x)=a 0 +a1 x+a 2 x 2 +a3 x 3 +-12xG(x)=-12a0 x-12a 1 x 2 -12a 2 x 3 +36x 2 G(x)= 36a 0 x 2 +3

21、6a1 x 3 +,G(x)=(a 0 +a1 x-12a 0 x)/(1-12x+36x2 )=A/(1-6x)+B/(1-6x)2。12欢迎下载精品文档G(x)=A(1+6x+(6x)2 +)+B(1+2(6x)+3(6x)2 +)则一般通解为 : a n =A*6 n +B*n*6 nan -25a n 2 =0解: 设 G(x)=a 0 +a1 x+a 2 x 2 +a3 x 3 +-25x 2 G(x)=-25a 0 x 2 -25a 1 x 3 -同上题 , 相加得G(x)=(a 0 +a1 x)/(1-25x2 )=p(x)/1-25x2 =(A/1-5x)+(B/(1+5x)G

22、(x)=A(1+5x+(5x) 2 +(5x) 3 + )+B(1+(-5x)+(-5x)2 + )则一般通解为 : a n =A*5 n +B*(-5) n220 已知 an2an 1an 20 ，（ 1）求一般解：（ 2）求满足 a0 0 ， a1 1的特解。（ 3）求满足 a0a12 的特解。解：（ 1） 特征方程：x22x 10 ，根 q2 4 42 2 21 2，则22通解： A（ 12 ）+B（ 12 ）0110（2） A1 122 ， B120211411412121212。13欢迎下载精品文档特解：22(1 2)(12)1442112（3） A2121 ， B122111111

23、2121212特解：(12)(12)222.21 已知anc 5nd( 4)n ，c和d为常数，n，求012时c和dNa5,a及序列的递推关系。答案：将 a05,a12 代入 an 中得c+d=5 和 5c-4d=-2c=2， d=3an25n3 ( 4) nan 12 5n 13 ( 4) n 1因为an5an 1 = 27 ( 4) n 1an 15an 2 = 27 ( 4) n 2所以 an5an 1 +4( an 15an2 )=0an 1an 220an 202.22 已知 an=c·3n +d·(-1)n,nN,c,d 是常数 , 求a n 满足的递推关系。解

24、 :等式为 anAx 1nBx 2n 形式3 和-1 为特征根特征方程为x 22x3 0 an 2an 1 3an 2 02.23an ( k1 k2 n)(3) n ， k1和 k2是常数， n N ，求 an 满足的递推关系2.24设 an -2 an 1 + an2 =5, a0=1,a1 =2, 求解这个递推关系。解： 首先解得 a2=8an -2 an 1 + an 2 =5 （1）an 1 -2 an 2 + an 3 =5 （2）（ 1）- （2）。14欢迎下载精品文档an -3 an 1 +3 an 2 - an 3 =0建立特征方程为：x 3 - 3x 23x - 10解这个

25、方程得： x11x 2 -1x 3 1/3设 an =A(1) n +B(-1) n +C(1/3) na0=A+B+Ca1 =A-B+(1/3)Ca2 =A+B+(1/9)C解得 A=2 B=7C= -9an =2(1) n +7(-1)n -9(1/3) n2.25设a n 序列的母函数为：(4-3x)/(1-x)(1+x-x3),但 b0=a0,b 1=a1-a 0.b n=an-a n-1 , 求序列 b n 的母函数 .解：设 b n 的母函数为 B(x),所以 B(x)= b 0 + b 1 x + b n x n又因为已知 b0 =a0,b 1=a1-a 0.b n=an-a n

26、-1 , ，代入 B(x) ，可得：B(x)= a0 + (a 1-a 0) x+. (a n-a n-1 ) x nB(x)= a 0+ a 1 x+an x n -x(a 0+ a 1 x+)又因为 a 序列的母函数为 (4-3x)/(1-x)(1+x-xnB(x)=(4-3x)/(1+x-x2)2.26设 G=a0 a1 x1a3 x2. 且 a 0a 2 xana0 an 1a1 an 2 .an 1 a0, 试证 1+xG2 =G2解：要证 1+x G =G2即证 G1= x Ga 01G1=a1 x a 2 x12a3 x.an a0 an 1a1 an2.an 1 a0,X :a

27、1a0 a02X :a2a0 a1a1 a0X 3 :a3a0 a2a1 a1a2 a03 ), 代入 B(x) ，得，1，。15欢迎下载精品文档.+_2G 1=a 0 x G+a1 xG2提出 G即得： G1= x G1+xG2 =G2.27求下列递推关系的一般解：（1）an - 4a n-1 =5n解：an - 4a n-1 =5na n-1 - 4a n-2 =5n-1 - 得 a n -9 a n-1 + 20a n-2 =0 特征方程 q 2-9q+20=0q1=4 ,q 2=5an =A4n +B5n（2）an + 6a n-1 =5· 3n 解：an + 6a n-1

28、=5·3na n-1 + 6a n-2 =5·3n-13a n-1 +18an-2 =5·3n - 得 a n +3 a n-1 -18a n-2 =0 特征方程 q 2+3q-18=0q1=-6 ,q 2 =3an =A(-6) n +B3n3+a2 x G .n（3）an - 4an-1 =4an- 4an-1 =4nn-1a- 4an-2=4n-14an-1 - 16a n-2=4n - 得 a n -8 a n-1 +16a n-2 =0 特征方程 q 2-8q+16=0q1=q2=4an =(A +Bn)4 nn（4）an + 6a n-1 =4(-6)an + 6an-1 =4(-6) na+ 6an-2=4(-6)n-1n-1。16欢迎下载精品文档-6a n-1 -36a n-2 =4(-6) n - 得 a n+12an-1 +36an-2 =0 特征方程 q 2+12q+36=0q1=q2=-6nan =(A +Bn)(-6)nn（5）an