组合数学卢开澄版答案第二章.doc

《组合数学卢开澄版答案第二章.doc》由会员分享，可在线阅读，更多相关《组合数学卢开澄版答案第二章.doc（50页珍藏版）》请在三一文库上搜索。

1、2.1 求序列0，1，8，27，的母函数。 解： 左右同乘再连加： 母函数：2.2 已知序列，求母函数。解：的第k项为： ，对于本题，n=4，母函数为：2.3 已知母函数G（X）= ,求序列 解：G（X）=从而有： G（X）=G（X）=7-4 =7*2.4已知母函数，求对应的序列。解：母函数为 解得：A=2 B=1 所以 2.5 设，其中Fn是第n个Fibonacci数。证明：， n=2，3，4。求的母函数。 解：设，则 -+，得： 又已知 ，则 ， 所以， 设，则可列出方程组： ，解得 那么，2. 6 求序列1，0，2，0，3，4，0，解：G(x)=1+0*x+2*+0*+3*+0*+0*+

2、4*+ =1+2+3+4+ G(x)= +2+3+ （1-）*G（x）=1+（1-）*G（x）=G（x）=2.7 设求。 题解： （1）-（2）得： 2.8 求下列序列的母函数： （1）1，0，1，0，1，0. （2）0，-1，0，-1，0，-1. （3）1，-1，1，-1，1，-1题解：（1）带入母函数公式得： （2）带入母函数公式得： （3）有（1）和（2）相加得到：2. 9 设G=1+3x+6+10+ +C（n+2，2）+证明：（1）（1-x）G=1+2x+3+4+ +（n+1）+（2）（1-）G=1+x+ +（3）G=1证：G=1+3x+6+10+ +C（n+2，2）+ xG= x+3

3、 6+ G= + 3+（1-x）G=1+2x+3+4+ +（n+1）+（1-）G=1+x+ +G=(1-x)(1-x)(1-x)G逐步相乘，根据以上两式可得G=12.10 证明：（a）(b)求H的表达式。 证明：（a） -，得 由组合的性质 ，所以 那么，得证。（b）设，B对应的序列为。根据（a），得，设G对应的序列为 ，则，根据母函数性质有，那么，根据（a），。2.11是一个多项式，并求母函数G。解：由题知： (1) (2)(1)-(2)得： (3) (4)(3)-(4) (5)(5)式即为的递推关系。所以序列的特征多项式为： 又母函数可表示为 因此，即证。其中解方程组： 解得：所以2.1

4、2 已知解：2.13 已知求序列 的母函数。解： -G（x）= 2.14 已知的母函数为， 求： 解： 。 求序列的递推关系。 解： 因而：递推关系为： 2.15 已知an的母函数为，求序列an的递推关系，并求a0,a1.解：c1= -1，c2=1则其特征多项式为：C（x）=x2-x+1与其对应的递推关系为：an-an-1+an-2=02.16 用数学归纳法证明序列 的母函数为 解： 当m=1时，的母函数就等于 假设当m=k时成立，即 （1） 当m=k+1时 （2）因为，所以（2）里的，为（2）对应的序列，为（1）对应的序列。所以由性质3得 所以命题得证2.17：已知G=1+2X+3X2 +（

5、n+1）xn+证明(1) G2 =（1-X）-4= Xn， (2) G2= Xn,其中an=，(3) an=C(n+3,3),n.解：设T=x+x2+x3+x4. =x/(1-x)T=1+2X+3X2 +（n+1）xn+=1/(1-X)2=G所以G2 =（1-X）-4，又因为G2 =（1+2X+3X2 +（n+1）xn+）（1+2X+3X2 +（n+1）xn+）=G1G2所以在G2 中xn的系数由(n+1)部分组成：如果G1中取的因子为xk 那么G2中只能去Xn-k,只有这样G1G2后才能得出xn ， 所以K从0取到n，一共有(n+1)部分组成，当K取0时G1因子的系数为（K+1），G2因子的

6、系数为(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)成立， an+1=1*(n+1+1-0)+2*(n+1+1-1)+ 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

7、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),n，又根据（2）。所以（1）得证。2.18 用母函数法求下列递推关系的一般解 a-6a+8a=0 解:设G(x)=a+ax+ax+ax+ -6xG(x)= -6ax-6ax-6ax- 8xG(x)= 8ax+8ax+ 相加得 G(x)=a+(a-6a)x/1-6x+8x 设p(x)=a+(a-6a)x,由于p(x)/r(x)是有理分式,多项式p(x)的次方低于r(x)的次方,则p

8、x)/r(x)可化为部分式来表示,且表示式是唯一的. 则 G(x)=p(x)/1-6x+8x=(A/1-2x) +(B/1-4x) =A(1+2x+(2x)+(2x)+)+B(1+4x+(4x)+(4x)+) 则一般通解为 a=A*2+B*4. a+14a+49a=0解:设G(x)=a+ax+ax+ax+ 14xG(x)= 14ax+ax+ax+ 49xG(x)= 49ax+49ax+相加得(同上题) G(x)=p(x)/1+14x+49x=(A/1-7x) +(B/(1-7x) G(x)=A(1+7x+(7x)+)+B(1+2(7x)+3(7x)+) 则一般通解为: a=A*7+B*n*7

9、 a-9a=0解: 设G(x)=a+ax+ax+ax+ -9xG(x)= -9ax-9ax-同上题,相加得: G(x)=(a+ax)/(1-9x)=p(x)/1-9x=(A/1-3x)+(B/(1+3x) G(x)=A(1+3x+(3x)+(3x)+)+B(1+(-3x)+(-3x)+)则一般通解为: a=A*3+B*(-3) a-6a-7a=0解:设 G(x)=a+ax+ax+ax+ -6xG(x)= -6ax-6ax-6ax+ -7xG(x)= -7ax-7ax+同上题,相加得 G(x)=(a+ax-6ax)/(1-6x-7x)=A/(1-7x)+B/(1+x)=A(1+7x+(7x)+)

10、B(1+x+x+)则一般通解为: a=A*7+B*1 a-12a+36a=0解:设 G(x)=a+ax+ax+ax+ -12xG(x)=-12ax-12ax-12ax+ 36xG(x)= 36ax+36ax+ 同上题,相加得 G(x)=(a+ax-12ax)/(1-12x+36x)=A/(1-6x)+B/(1-6x) G(x)=A(1+6x+(6x)+)+B(1+2(6x)+3(6x)+)则一般通解为: a=A*6+B*n*6 a-25a=0解: 设G(x)=a+ax+ax+ax+ -25xG(x)=-25ax-25ax-同上题,相加得G(x)=(a+ax)/(1-25x)=p(x)/1-2

11、5x=(A/1-5x)+(B/(1+5x) G(x)=A(1+5x+(5x)+(5x)+)+B(1+(-5x)+(-5x)+) 则一般通解为: a=A*5+B*(-5)220 已知， （1）求一般解： （2）求满足，的特解。 （3）求满足的特解。解：（1） 特征方程： ，根，则 通解：A（）+B（） （2） ， 特解：（3）， 特解：2.21 已知，c和d为常数，nN，求时c和d及序列的递推关系。答案：将代入中得c+d=5和5c-4d=-2 c=2，d=3 因为= =所以 +4()=0 2.22 已知an=c3n+d(-1)n,nN,c,d是常数,求an满足的递推关系。 解: 等式为形式 3和

12、1为特征根 特征方程为 2.23 ，和是常数，求满足的递推关系2.24 设-2+=5, =1, =2,求解这个递推关系。 解： 首先解得=8-2+=5 （1） -2+=5 （2）（1）-（2） -3+3-=0建立特征方程为： 解这个方程得： 1 -1 1/3 设 =A(1)+B(-1)+C(1/3) =A+B+C=A-B+(1/3)C=A+B+(1/9)C解得A= 2 B= 7 C= -9 =2(1)+7(-1)-9(1/3)2.25 设an序列的母函数为： (4-3x)/(1-x)(1+x-x3),但b0=a0,b1=a1-a0 .bn=an-an-1,求序列bn的母函数.解：设bn的母函

13、数为B(x), 所以B(x)= b0 + b1 x + bn xn 又因为已知b0=a0,b1=a1-a0 .bn=an-an-1,，代入B(x)，可得： B(x)= a0 + (a1-a0) x+. (an-an-1) xn B(x)= a0+ a1 x+an xn-x(a0+ a1 x+) 又因为an序列的母函数为 (4-3x)/(1-x)(1+x-x3),代入B(x)，得， B(x)=(4-3x)/(1+x-x2)2.26 设G=且1，试证1+x=G解：要证 1+x=G即证G1= x1 G1= : .+_ G1=G+G+G. 提出G即得：G1= x1+x=G2.27 求下列递推关系的一般

14、解：（1）an - 4an-1=5n解：an - 4an-1=5n a n-1- 4an-2=5n-1-得 an -9 an-1+ 20a n-2=0特征方程 q2-9q+20=0q1=4 ,q2=5an =A4n +B5n（2）an + 6a n-1=53n解：an + 6a n-1=53na n-1 + 6a n-2=53n-13a n-1 +18a n-2=53n-得 an +3 an-1-18a n-2=0特征方程 q2+3q-18=0q1=-6 ,q2=3an =A(-6)n +B3n（3）an - 4a n-1=4n解：an - 4a n-1=4nan-1 - 4a n-2=4n-

15、14an-1 - 16a n-2=4n-得 an -8 an-1+16a n-2=0特征方程 q2-8q+16=0q1=q2=4an =(A +Bn)4n（4）an + 6a n-1=4(-6)n解：an + 6a n-1=4(-6)nan-1 + 6a n-2=4(-6)n-1-6an-1 -36a n-2=4(-6)n-得 an+12an-1+36a n-2=0特征方程 q2+12q+36=0q1=q2=-6an =(A +Bn)(-6)n（5）an - 4a n-1=25n - 34n解：an - 4a n-1=25n - 34nan-1 - 4a n-2=25n -1- 34n-15a

16、n-1 -20a n-2=25n - 154n-1-得an-9an-1+20a n-2=34n-1an-9an-1+20a n-2=34n-1an-1-9an-2+20a n-3=34n-24an-1-36n-2+80a n-3=34n1-得an-13an-1+56a n-2-80a n-3=0特征方程 q3-13q2+56q-80=0q1=q2=4, q3=5an =(A +Bn)(4)n+C5n（6）an - 4a n-1=74n - 65n解：an - 4a n-1=74n - 65nan-1 - 4a n-2=74n-1 - 65n-14an-1 -16a n-2=74n - 245n

17、1-得an-8an-1+16a n-2=-65n-1an-8an-1+16a n-2=-65n-1an-1-8an-2+16a n-3=-65n-25an-1-40an-2+80a n-3=-65n-1-得an-13an-1+56a n-2-80a n-3=0特征方程 q3-13q2+56q-80=0q1=q2=4, q3=5an =(A +Bn)(4)n+C5n（7）an + 6a n-1=(-6) n (2n+3n2)解：对应齐次的特征方程为：q+6=0齐次通解为：an=A(-6) n通所求解为：an= A(-6) n +(-6) nk0+k1 n+k2 n2（8）an - 4a n-1

18、n-n2)4n解：对应齐次的特征方程为：q-4=0齐次通解为：an=A(4) n通所求解为：an= A(-6) n +(4) nk0+k1 n+k2 n2（9）an - a n-1=4n3-6n2+4n-1解：对应齐次的特征方程为：q-1=0齐次通解为：an=A(1) n通所求解为：an=A(1) n +k0+k1 n1+k2 n2+k3 n3（10）an - 7a n-1+ 12a n-2=52n - 43n解：an - 7a n-1+ 12a n-2=52n - 43nan-1 - 7a n-2+ 12a n-3=52n-1 - 43n-12an-1 -14a n-2+ 24a n-3

19、52n - 83n-1-得an-9an-1+26a n-2-24a n-3= - 43n-1an-9an-1+26a n-2-24a n-3= - 43n-1an-1-9an-2+26a n-3-24a n-4= - 43n-23an-1-27an-2+78a n-3-72a n-4= - 43n-1-得an-12an-1+53a n-2-102a n-3+72a n-4=0特征方程 q4-12q3+53q2-102q+72=0q1=q2=3, q3=4, q4=2an =(A +Bn)(3)n+C4n+D2 n（11）an + 2a n-1 - 8a n-2=3(- 4)n - 14(3)

20、n解：an + 2a n-1 - 8a n-2=3(- 4)n - 14(3)nan-1 + 2a n-2 - 8a n-3=3(- 4)n-1 - 14(3)n-1-4an-1 -8a n-2 +32a n-3=3(- 4)n +56(3)n-1-得an+6an-1-32a n-3=- 983n-1an+6an-1-32a n-3=- 983n-1an-1+6an-2-32a n-4=- 983n-23an-1+18an-2-96a n-4=- 983n-1-得an+3an-1-18a n-2-32a n-3+96a n-4=0特征方程 q4+3q3-18q2-32q+96=0q1=q2=-

21、4, q3=3, q4=2an =(A +Bn)(-4)n+C3n+D2 n（12）an - 6a n-1+9 a n-2 =3n解：an - 6a n-1+9 a n-2 =3nan-1 - 6a n-2+9 a n-23=3n-13an-1 - 18a n-2+27 a n-3=3n-得an-9an-1-27a n-2-27 a n-3=0特征方程 q3-9q2+27q-27=0q1=q2=q3=3an =(A +Bn+Cn2) 3n（13）an - 7a n-1+ 16a n-2 - 12a n-3=2n+3n解：an - 7a n-1+ 16a n-2 - 12a n-3=2n+3n

22、an-1- 7a n-2+ 16a n-3 - 12a n-4=2n-1+3n-12an-1- 14a n-2+ 32a n-3 - 24a n-4=2n+23n-1-得an-9an-1+30a n-2-44a n-3+24a n-4=3n-1an-9an-1+30a n-2-44a n-3+24a n-4=3n-1an-1-9an-2+30a n-3-44a n-4+24a n-5=3n-23an-1-27an-2+90a n-3-132a n-4+72a n-5=3n-1-得an-12an-1+57a n-2-134a n-3+156a n-4-72a n-5=0特征方程 q5-12q4+

23、57q3-134q2+156q-72=0q1=q2=q3=2, q4= q5=3an =(A +Bn+Cn2)2n+(D+En)3 n（14）an - 2a n-1=2n+3n+4n解：an - 2a n-1=2n+3n+4nan-1 - 2a n-2=2n-1+3n-1+4n-12an-1 - 4a n-2=2n+23n-1+24n-1-得an-4an-1+4a n-2=3n-1+24n-1an-4an-1+4a n-2=3n-1+24n-1an-1-4an-2+4a n-3=3n-2+24n-23an-1-12an-2+12a n-3=3n-1+64n-2-得an-7an-1+16a n-

24、2-12a n-3=24n-2an-7an-1+16a n-2-12a n-3=24n-2an-1-7an-2+16a n-3-12a n-4=24n-34an-1-28an-2+64a n-3-48a n-4=24n-2-得 an-11an-1+44an-2-76a n-3+48a n-4=0特征方程 q4-11q3+44q2-76q+48=0q1=q2= 2, q3=3,q4= 4an =(A +Bn+)2n+C3 n+D4 n2.28 解：2.29 ，求这个递推关系的解解： 已知：所以有：设：即：（）等式（）的特征方程为：（）则：则（）的通解为：若给定初始条件：则：解得： 所以：又因为：

25、所以：的解：2.30 ， 解这个递推关系。解：已知：所以有：设：即：（）等式（）的特征方程为：（）则：则（）的通解为：因为：所以有：则：解得： 所以：又因为：所以：的解：2.31解：2.32 解下列递推关系：（a）an = na n-1, a0 = 1,an = ?解：n： an = na n-1n(n-1)：an-1= (n-1)a n-2n(n-1)(n-2)：an-2= (n-2)a n-3n(n-1)(n-2)(n-3)：an-3= (n-3)a n-4 n(n-1)(n-2)(n-3) 3： a2 = 2a 1把等式左右两端相加化简得：an = n(n-1)(n-2)(n-3) 32

26、a 1an = n!a1an = n!（b）an - a n-1 =, a0 = 7解：an - a n-1 =an-1-a n-2=()n-1 an-1 - a n-2=()n-得 an - an-1+ a n-2=0特征方程 q2- q+ =0q1=1,q2=an =A +B() na0 =7,a1= 7=A+B A=8=A+B=-1an =8 - () n（c）an - a n-1= 解：an - a n-1= an - a n-1=（ ）n-1an-1 - a n-2=（ ）n-得 an - an-1+ a n-2=0特征方程 q2- q+ =0q1=1,q2=an =A +B() n

27、2.33是Fibonacci序列，求解解：.+令则令得则2.34 an= an-1+C(n+2,3), a0=0,求an。 解：由已知递推关系，可得： an-an-1= (n+23) （1） an-1-an-2= (n+13) （2） a2- a1= (43) (n-1) a1-a0= (33) (n) 将1，2，3.。n以上n个式子累加，可得： an-a0= (n+23) + (n+13) + . + (43) + (33), 由于(n+23) + (n+13) + . + (43) + (33)= (n+2n-1) + (n+1n-2) + . + (41) + (30)= (n+3n-1

28、) 有因为a0=0,代入可得， an= (n+3n-1).2.35 ，解： 有（1-x）G(x)=x当G(x)乘4次（1-x） 有 （1-x）G(x)= x （1-x）G(x)=1/(1-x) G(x)=1/（1-x）有六重根，因此设置形式为 带入即可解出a的表达式。2.36 利用迭代法解：(1)(2) 解：（1）若，则 （2） 若，则2.37 利用置换,解： an= ，a0=1,a1= 4 解：把代入等式，即 特征方程为: 特征根为 带入初值： 得 2.38 理由置换，解：，答案：把代入中得： 得： 设=代入得到特征多项式解方程的， 所以 239利用置换，解：，解：利用置换代入上式可得，即，

29、即可得 特征方程： 解得，q=1通解为：根据，可得，即，代入通解可得 由此可得，所以，即2.41. 设a满足: a+ba+ba=5r 其中b,b和r都是常数,试证该序列可满足三阶齐次线性常系数递推关系,且有特征多项式(x-r)(x+bx+b)证明: a+ba+ba=5r a+ba+ba=5r 两边乘以r得 ra+rba+rba=5r 得 a+(b-r)a+(b-rb)a-rba=0 由可知.该序列可满足三阶齐次线性常系数递推关系.它的特征多项式为 x+(b-r)x+(b-rb)x-rb因式分解为(x-r)(x+bx+b) 证毕.2.42：设an满足an-an-1-an-2=0, bn满bn-2

30、bn-1-bn-2=0,cn=an+bnn满足一个四阶线性常系数齐次递推关系。解：因为an= an-1+an-2，bn=2bn-1+bn-2,所以cn= an-1+an-2+2bn-1+bn-2=2cn-1+cn-2-an-1所以an-1=2cn-1+cn-2- cn,又因为an-1=an-an-2=2cn+cn-1- cn+1 -(2cn-2+cn-3- cn-1)所以cn= 2cn-1+cn-2-an-1 cn= 2cn-1+cn-2- 2cn+cn-1- cn+1 -(2cn-2+cn-3- cn-1)所以3cn-3cn-2-cn-3- cn+1=0 ，满足一个四阶线性常系数齐次递推关系

31、2.43 习题2.42中，若，试讨论之解：满足 满足所以， （1）又因为 : 所以 有 （2） 那么 得 又因为（2）知道（3）（3）（2）= 所以最后得到 ；所以推出满足四阶线性常系数齐次递推关系。2.44 设an和bn均满足递推关系xn+d1xn-1+d2xn-2=0，试证（1）anbn满足一个三阶奇次线性常系数递推关系；（2）a0，a2，a4，满足一个二阶线性常系数奇次递推关系。解（1）所以anbn满足一个三阶其次线性常系数递推关系。2.45 设是Fibonacci序列,试找出常数a,b,c,d，使解：但n分别为0,1,2,3时,有代入上面四个式子,得 a=,b=21,c=13,d=.

32、2.45 设是Fibonacci序列，试找出常数，使： 解： 因而有：2a+ 6b + 30c +120d=2 6a+30b+ 120c+520d=8 30a+120b+520c+2184d=34 120a+520b+2184c+9248d=144 解之得： ， ， ， 2.46 对所有的正整数a,b,c,恒有 解：首先 若能证明 （m,n为任意的正整数）成立，则原式可证明成立。所以用第二归纳原理证明得： n固定，当m=1时：2.47 证明：由题知： 所以2.48 有红、黄、蓝、白球各两个，绿、紫、黑球各3个，从中取出10个球，试问有多少种不同的取法？ 解：设ar表示取出r个球的不同取法，则序

33、列ar的母函数为 ，即求的系数。 则，即先求的整数。可得如下表格：a00011223b01201010c106273401 再根据公式），有 ，则有的系数为： 即有678种不同的取法。2.49 求由A，B，C，D组成的允许重复的n位排列中AB至少出现一次的排列数目解：设为所求个数，为不出现AB串的个数（取n位串）=1，=4，=15，=56特征方程为 解得 q=2=A+BA+B=1A（2+）+B（2-）=4解得： A= B=+=-=-2.50 求n位四进制数中2和3必须出现偶数次的数目. 题解：如果要求首位不是0,幂次减1，那么答案就是.2.51 试求有a,b,c这3个字符组成的n位符号串中不出

34、现aa图像符号串的数目. 题解：设不出现aa的字符串的排列数为an 在所有符合要求的n位串中，最后一位是a,则n-1位是b或c，最后一位不是a，则是b或c.故有an=2an-1+2an-2，a1=3，a2=8，a0=1.x2-2x-2=0,解得x=。an=A(1+)n+B(1-)nA=,B= 2.52 证明：C（n,n）+ C（n+1,n）+ +C（n+m,n）= C（n+m+1,m） 证：左式= C（n,0）+ C（n+1,1）+ +C（n+m,m）根据组合意义对于二维坐标系（ 横坐标最大值为n+1，纵坐标为最大值m）C（n，0）表示从（0，0）到（n，0）点的路径数C（n+1,1）表示从（

35、0，0）到（n,1）点的路径数C（n+1,m）表示从（0，0）到（n,m）点的路径数C（n+1+m,1）表示从（0，0）到（n+1,m）点的路径数得证：左式=右式2.53 利用，改善Pn估计式。 解：令 一个整数n拆分成若干整数的和，在拆分中每个整数允许重复出现。故 ，所以有 ，又因为 所以， ，由于，则， 所以，则 由和，有 ，利用条件， 则， 又， 所以，即 由于，所以，则 接下来，求式右端的极小值，令 ，即，解得，（舍去）且，又，所以是极小值点，代入得 ，即 .2.548台计算机分给3个单位，第1个单位的分配量不超过3台，第2个单位的分配量不超过4台，第3个单位的分配量不超过5台，问共有几种分配方案？ 解：易知分配方案的母函数为：其中的系数即为所求方案数，即共有种分配方案。2.55证明任一个正整数n 都可以表示成不同的 Fibonacci数的和。证明：对n作归纳2.56 空间有n个平面，任意三个平面交于一点，无四平面共点，问这样的n个平面将空间分割成多少个不重叠的域？解：设n个平面将空间分割成个域，则第n个平面被其余的n-1个平面分割成n段，这n段正好是新增加的n个域的边界。所以，=1，=2.2.57 相邻为不同为零的n位二进制数，总共有多少个0？ 解：设相邻位不同为0的n位2进制数的个数为hn 个，这些数中一共有an个0，当n位二进制数最高位为1时,符合条件的n位二