组合数学答案.docx

《组合数学答案.docx》由会员分享，可在线阅读，更多相关《组合数学答案.docx（46页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、2.1 求序列0，1，8，27，的母函数。 解： 左右同乘再连加： 母函数：2.2 序列，求母函数。解：的第k项为： ，对于此题，n=4，母函数为：2.3 母函数GX= ,求序列 解：GX=从而有： GX=GX=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*+4*+ =1+2+3+4+

2、 G(x)= +2+3+ 1-*Gx=1+1-*Gx=Gx= 设求。 题解： 1-2得： 2.8 求以下序列的母函数： 11，0，1，0，1，0. 20，-1，0，-1，0，-1. 31，-1，1，-1，1，-1题解：1带入母函数公式得： 2带入母函数公式得： 3有1和2相加得到：2. 9 设G=1+3x+6+10+ +Cn+2，2+证明：11-xG=1+2x+3+4+ +n+1+21-G=1+x+ +3G=1证：G=1+3x+6+10+ +Cn+2，2+ xG= x+3+ 6+ G= + 3+1-xG=1+2x+3+4+ +n+1+1-G=1+x+ +G=(1-x)(1-x)(1-x)G逐步

3、相乘，依据以上两式可得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.12解：2.13 求序列 的母函数。解： -Gx= 2.14 的母函数为， 求： 解： 。 求序列的递推关系。 解： 因此：递推关系为： 2.15 an的母

4、函数为，求序列an的递推关系，并求a0,a1.解：c1= -1，c2=1那么其特征多项式为：Cx=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 +n+1xn+证明(1) G2 =1-X-4= Xn， (2) G2= Xn,其中an=，(3) an=C(n+3,3),n.3.解：设T=x+x2+x3+x4. =x/(1-x)T=1+2X+3X2 +n

5、+1xn+=1/(1-X)2=G所以G2 =1-X-4，又因为G2 =1+2X+3X2 +n+1xn+1+2X+3X2 +n+1xn+=G1G2所以在G2 中xn的系数由(n+1)部分组成：假如G1中取的因子为xk 那么G2中只能去Xn-k,只有这样G1G2后才能得出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，用数学归纳法：1a0 = C(0+3,3)=12假设an=C(n+3,3)成立，即an= C(n+3,3)3证明an+1=C(n+

6、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*(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.3，又依据2。所以1得证。2.18

7、 用母函数法求以下递推关系的一般解 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(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+1

8、4a+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 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)+)

9、+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)+)+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

10、-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-25x=(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 特征方

11、程： ，根，那么 通解：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和-1为特征根 特征方程为 2.23 ，和是常数，求满意的递推关系2.24 设-2+=5, =1, =2,求解这个递推关系。 解： 首先解得=8-2+=5 1 -2+=5 21-2 -3+3-=0建立特征方程为： 解这个方程得： 1 -1 1/3 设 =A(1)+B(-1)+C(1/3)

12、 =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的母函数为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

13、序列的母函数为 (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 求以下递推关系的一般解：1an - 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 +B5n2an + 6a n-1=53n解：an + 6a n-1=53na n-1 + 6a

14、 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 +B3n3an - 4a n-1=4n解：an - 4a n-1=4nan-1 - 4a n-2=4n-14an-1 - 16a n-2=4n-得 an -8 an-1+16a n-2=0特征方程 q2-8q+16=0q1=q2=4an =(A +Bn)4n4an + 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)

15、n-得 an+12an-1+36a n-2=0特征方程 q2+12q+36=0q1=q2=-6an =(A +Bn)(-6)n5an - 4a n-1=25n - 34n解：an - 4a n-1=25n - 34nan-1 - 4a n-2=25n -1- 34n-15an-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+56

16、q-80=0q1=q2=4, q3=5an =(A +Bn)(4)n+C5n6an - 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-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=5

17、an =(A +Bn)(4)n+C5n7an + 6a n-1=(-6) n (2n+3n2)解：对应齐次的特征方程为：q+6=0齐次通解为：an=A(-6) n通所求解为：an= A(-6) n +(-6) nk0+k1 n+k2 n28an - 4a n-1=(n-n2)4n解：对应齐次的特征方程为：q-4=0齐次通解为：an=A(4) n通所求解为：an= A(-6) n +(4) nk0+k1 n+k2 n29an - a n-1=4n3-6n2+4n-1解：对应齐次的特征方程为：q-1=0齐次通解为：an=A(1) n通所求解为：an=A(1) n +k0+k1 n1+k2 n2+k

18、3 n310an - 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=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-1

19、02a n-3+72a n-4=0特征方程 q4-12q3+53q2-102q+72=0q1=q2=3, q3=4, q4=2an =(A +Bn)(3)n+C4n+D2 n11an + 2a n-1 - 8a n-2=3(- 4)n - 14(3)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-

20、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=-4, q3=3, q4=2an =(A +Bn)(-4)n+C3n+D2 n12an - 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特征方程

21、 q3-9q2+27q-27=0q1=q2=q3=3an =(A +Bn+Cn2) 3n13an - 7a n-1+ 16a n-2 - 12a n-3=2n+3n解：an - 7a n-1+ 16a n-2 - 12a n-3=2n+3n 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-4

22、4a 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+57q3-134q2+156q-72=0q1=q2=q3=2, q4= q5=3an =(A +Bn+Cn2)2n+(D+En)3 n14an - 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+

23、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-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=

24、2, q3=3,q4= 4an =(A +Bn+)2n+C3 n+D4 n2.28 解：2.29 ，求这个递推关系的解解： ：所以有：设：即：等式的特征方程为：那么：那么的通解为：假设给定初始条件：那么：解得： 所以：又因为：所以：的解：2.30 ， 解这个递推关系。解：所以有：设：即：等式的特征方程为：那么：那么的通解为：因为：所以有：那么：解得： 所以：又因为：所以：的解：解：2.32 解以下递推关系：aan = 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(

25、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) 32a 1an = n!a1an = n!ban - 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 - () ncan - a n-1= 解：an - a

26、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是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), 由

27、于(n+23) + (n+13) + . + (43) + (33)= (n+2n-1) + (n+1n-2) + . + (41) + (30)= (n+3n-1) 有因为a0=0,代入可得， an= (n+3n-1). ，解： 有1-xG(x)=x当G(x)乘4次1-x 有 1-xG(x)= x 1-xG(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

28、 理由置换，解：，答案：把代入中得： 得： 设=代入得到特征多项式解方程的， 所以 239利用置换，解：，解：利用置换代入上式可得，即，即可得 特征方程： 解得，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

29、)x+(b-rb)x-rb因式分解为(x-r)(x+bx+b) 证毕.2.42：设an满意an-an-1-an-2=0, bn满bn-2bn-1-bn-2=0,cn=an+bn, n=.3。证cn满意一个四阶线性常系数齐次递推关系。解：因为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-

30、2cn+cn-1- cn+1 -(2cn-2+cn-3- cn-1)所以3cn-3cn-2-cn-3- cn+1=0 ，满意一个四阶线性常系数齐次递推关系。2.43 习题2.42中，假设，试探讨之解：满意 满意所以， 1又因为 : 所以 有 2 那么 得 又因为2知道332= 所以最终得到 ；所以推出满意四阶线性常系数齐次递推关系。2.44 设an和bn均满意递推关系xn+d1xn-1+d2xn-2=0，试证1anbn满意一个三阶奇次线性常系数递推关系；2a0，a2，a4，满意一个二阶线性常系数奇次递推关系。解1所以anbn满意一个三阶其次线性常系数递推关系。2.45 设是Fibonacci序

31、列,试找出常数a,b,c,d，使解：但n分别为0,1,2,3时,有代入上面四个式子,得 a=,b=21,c=13,d=.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 有红、黄、

32、蓝、白球各两个，绿、紫、黑球各3个，从中取出10个球，试问有多少种不同的取法？ 解：设ar表示取出r个球的不同取法，那么序列ar的母函数为 ，即求的系数。 那么，即先求的整数。可得如下表格：a00011223b01201010c106273401 再依据公式，有 ，那么有的系数为： 即有678种不同的取法。2.49 求由A，B，C，D组成的允许重复的n位排列中AB至少出现一次的排列数目解：设为所求个数，为不出现AB串的个数取n位串=1，=4，=15，=56特征方程为 解得 q=2=A+BA+B=1A2+B2-=4解得： A= B=+=-=-2.50 求n位四进制数中2和3必需出现偶数次的数目.

33、 题解：假如要求首位不是0,幂次减1，那么答案就是.2.51 试求有a,b,c这3个字符组成的n位符号串中不出现aa图像符号串的数目. 题解：设不出现aa的字符串的排列数为an 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 证明：Cn,n+ Cn+1,n+ +Cn+m,n= Cn+m+1,m 证：左式= Cn,0+ Cn+1,1+ +Cn+m,m依据组合意义对于二维坐标系 横坐标最大值为n+1，纵坐标为最大值mCn，0表示从0，0到n，0点的途径数Cn+1,1表示从0，0到n,1点的途径数Cn+1

34、,m表示从0，0到n,m点的途径数Cn+1+m,1表示从0，0到n+1,m点的途径数得证：左式=右式2.53 利用，改善Pn估计式。 解：令 一个整数n拆分成假设干整数的和，在拆分中每个整数允许重复出现。故 ，所以有 ，又因为 所以， ，由于，那么， 所以，那么 由和，有 ，利用条件， 那么， 又， 所以，即 由于，所以，那么 接下来，求式右端的微小值，令 ，即，解得，舍去且，又，所以是微小值点，代入得 ，即 .2.548台计算机分给3个单位，第1个单位的安排量不超过3台，第2个单位的安排量不超过4台，第3个单位的安排量不超过5台，问共有几种安排方案？ 解：易知安排方案的母函数为：其中的系数即

35、为所求方案数，即共有种安排方案。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位二进制数的个数为hn-1 最高位为0时，次高位必为1符合条件的n位