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

上传人:奥沙丽水 文档编号:126722 上传时间:2025-07-11 格式:DOC 页数:50 大小:2.41MB
下载 相关 举报
组合数学卢开澄版答案第二章.doc_第1页
第1页 / 共50页
组合数学卢开澄版答案第二章.doc_第2页
第2页 / 共50页
组合数学卢开澄版答案第二章.doc_第3页
第3页 / 共50页
组合数学卢开澄版答案第二章.doc_第4页
第4页 / 共50页
组合数学卢开澄版答案第二章.doc_第5页
第5页 / 共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位二

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 中学教育 > 试题

宁ICP备18001539号-1