[工学]组合数学第二章课后习题答案

1、求母函数的题要化简吗？2.1题（陈兴） 求序列 0，1，8，27，的母函数。 解：由序列可得到 因为 设 设 由以上推理可知=所以可通过求得得到序列的母函数：2.2题（陈兴）已知序列，求母函数解： = 因为所以所以就是所求序列的母函数。2.3题（陈兴）已知母函数，求序列。解：=由得所以由两式相加得：对应序列=11，39，2.4题（陈兴）已知母函数，求序列。解：=则=2.5题（陈兴）设，其中是fibonacci数。证明：，n=2.3.4.求的母函数。解：(1).已知则= 则则(2)为什么？ = = = =这他娘的对吗？2.6题（陈兴）求序列1，0，2，0，3，0，的母函数。解：序列=2.7题（顿

2、绍坤）设=1/(1-x2)2求解设为什么等于这个？所以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/(x+1)？2.9题（顿绍坤）设证明：(1)(2)(3)因为，所以有证明（1） （2）展开(1-x2)g= (1+x)/(1-2x+x2) 当时 有 (3) = =1 2.10题（顿绍坤）证明(1) (2) 求h的表达式。证明(1) 设h的第k+1项为h，则h=， 设g的前k+1项的和为g，则g=+ 而+ =1+ + + =1+3*2+4*3+(k+

3、2)(k+1) =1+(1+ 2+ 3+k+3+6+3k+2+2+2) =1+k(k+1)(2k+1)+ +2k =1+k = = h h=注释：均为k项，分别为平方数列，等差数列，常数列(2) 由h=1+4x+10x+20 x+() x+ =1+x+ 对其3次积分得=对此积分式3次求导得h=( )求解完毕2.11题（顿绍坤）a=(n+1),g=1+4x+(n+1)x+,证明(1-3x+3x-x)g是一个多项式,并求母函数g。解: g= g =+ g =xg+g(1x)= g= 即为所求(13x3xx)=(1x)(13x3xx)g =(1x)g =(1x) =x+1求解完毕。说明：可以由=2.

4、12题（顿绍坤）已知a=, =,求序列 a的母函数。解:设序列 a的母函数为g(x),则g(x)= a+ax+ax+ ax+ ax+ a=1+2+3+n+(n+1)g(x)=1+(1+2)x+(1+2+3)x+(1+2+3+n+(n+1) x+=1+x+ x+x+ +2x(1+x+ x+x+) +3x(1+x+ x+x+)+(n+1)x(1+x+ x+x+)+= (1+x+ x+x+)(1+2x+3x+nx+ (n+1)x+)=g= g= 即为序列 a的母函数。求解完毕。2.13题（高亮）解：b(x)=1+2x+3x+1: a=1b=1x: a=1+2 b=2x: a=1+2+3 b=3a=

5、ba= b+ ba= b+ b+ ba(x)= b(1+x+ x+)+ bx(1+x+ x+)+ bx(1+x+ x+) +=(1+x+ x+)( b+ bx+ bx+)= =2.14题（高亮）解:特征多项式 k(x)= x-2x-1x-2x-1=0 解得：r=1+ r=1-p(x)= +a+b=0-a(1-)-b(1+)=1得：a=, b=-p(x)= ( -)=p=(1+)-(1-)p=0, p=12.15 题（高亮）解：特征多项式 k(x)= x-x+1x-x+1=0解得：r=+i=cos+isin=e, r=-i= cos-isin= ea(x)= +a+a=1, ar+ ar=0解得

6、：a=1，a=a=acos+asin= cos+sina=1, a=1216 题（高亮） 证明序列，的母函数为（1-x）证明：当m=0时，命题成立。 假设对于m-1，命题成立，即=（1-x）， 则g(x)= =+=x g(x)+ （1-x） (1-x) g(x)= （1-x），g(x)= =（1-x）归纳法！2.17题（高亮）g=1/（1-x）22.18题（高亮）(a)an-6an-1+8an-2=0(a) -6+8=0解：令a（x）=+，d（x）=1-6x+8x则a（x）d（x）=(1-6x+8x)(+) =+(-6)+(-6+8)+(-6+8)+ =+(-6) a（x）=+ =a=(4-)

7、，a=(2-) a（x）=(4-)+(2-) =(b) -6+8=0解：令a（x）=+，d（x）=1+14x+49x则a（x）d（x）=(1+14x+49x)(+) =+(+14)+(+14+49)+(+14+49)+ =+(+14) a（x）=+ =a=(14+)，a=-(7+) a（x）=(14+)-(7+) =(c) -9=0解：令a（x）=+，d（x）=1-9x则a（x）d（x）=(1-9x)(+) =+(-9)+ =+ a（x）=+ =a=+，a=- a（x）= (+)+(-) =2.19 题（李拂晓）用特征值法求习题2.18的解。（1） -6+8=0解：特征方程：-6x+8=0 (

8、x-2)(x-4)=0 (2) 特征方程：+14x+49=0 (x+7)(x+7)=0 所以 （3）-9=0 特征方程：- 9=0 （x-3）（x+3）=0 所以 =a+b(4) -6-7=0 特征方程：-6x-7=0 (x-7)(x+1)=0 所以 =a+b(5) -12+36=0 特征方程：-12x+36=0 (x-6)(x-6)=0 所以 =(an+b)(6) -25=0 特征方程：-25=0 (x+5)(x-5)=0 所以 =a+b以上题中a,b均是待定常数。2.20 题（李拂晓）已知-2-=01求一般解；什么是一般解？解：特征方程：-2x-1=0 x-(1+)x-(1-)=0 所以

9、=a+b a,b均是待定常数。2.求满足=0，=1的特解。特解？ 解：根据1题求出的一般解，把=0，=1代入=a+b中，有=a+b=0，=a(1+)+b(1-)=1,解得a=/4,b=-/4,所以=/4-/4。3求满足=2的特解。 解：原理同2题，把=2代入=a+b中，有=a+b=2，=a(1+)+b(1-)=2,解得a=1,b=1,所以，=+。2.21 题（李拂晓）以知=c+d，c和d为常数，nn,求=5，=-2时的c和d及序列的递推关系。 解：由题意可知，=c+d=5，=5c-4d=-2,解得，c=2, d=3, 则=2+3，由此可知，x1=5, x2=-4,为其特征方程的两个特征根，则可

10、知其特征方程为：（x-5）(x+4)=0,即-x-20=0, 所以序列的递推关系为，-20=02.22 题（李拂晓）以知=c+d，c和d为常数，nn,求满足的递推关系。解：由题意可知，的特征方程为，（x-3）（x+1）=0,即-2x-3=0,所以递推关系为-2-3=02.23 题（李拂晓）=（+n）,和是常数，nn,求满足的递推关系。 解：由题意可知，的特征方程为，（x+3）（x+3）=0,即+6x+9=0, 所以递推关系为+6+9=0。2.24 题（李拂晓）设-2+=5，=1，=2，求解这个递推关系。解：由题意可知，特征方程为：-2x+1=（x-1）（x-1）=0, 所以1是二重特征根，令特

11、解为， =k, 代入递推关系得， k-2k+k=5 解得，2k=5, k=5/2 故非齐次方程特解是: =5/2, 一般解： =5/2+an+b 又由 =b=1, =5/2+a+b=2, 可知，a=-3/2, b=1.所以 =5/2-3/2n+1 2.25题（孙明柱）设an序列的母函数为：,但b0=a,b1=a1-a0, ,bn=an-an-1, ,求序列bn的母函数解2.26题（孙明柱）设g=a0+a1x+a2x2+,且a0=1,an=a0an-1+a1an-2+an-1a0,试证1+xg2=g.证明：因为g=a+ax+ax+. x:a=aa+ a1a x:a=aa+ aa+ aa x:a=

12、aa+ aa+ aa+ aa+) g-1-x= a+ax-1-x+(aa+ aa) x+ (aa+ aa+ aa) x+ 因为a=1，得a=1所以g-1-x= (aa+ aa) x+ (aa+ aa+ aa) x+ =a0a1x+aax+ aax+ aax+ aax+ = a(ax+ ax+)+ ax(ax+ax)+ ax( ax +)+ = aax+aax+ ax(ax+ax+)+ axax +=aax+aax+aax+ax(ax+ax)+ axax +-x=-x+(ax+ax+)(a+ax +)=-x+x(a+ax +) (a+ax +)所以：g-1-x=-x+(a+ax +)xg-1=g

13、x227 题（孙明柱） 求下列递推关系的一般解：（1） 解：递推关系的特征方程为：其两个特征根为0和4右端项可以看成，m=0且p=0,令特解代入递推关系：解的k=5故非其次方程特解是：一般解：，系数a由初始条件确定。（2） 递推关系的特征方程为：，其两个特征根为0和-6右端可以看成，其中m=0且p=0, 令特解 代入递推关系：,解的k=故非其次方程特解是：一般解： ，系数a由初始条件确定。（3） 递推关系的特征方程为：,其两个特征根为0和4右端可以看成，m=1，p=0, 令特解代入递推关系：即 解的k=1故非其次方程特解是：一般解：，系数a由初始条件确定。（4） 递推关系的特征方程为：，其两个

14、特征根为0和-6右端可以看成，m=1，p=0，令特解代入递推关系：即：解的k=4故非其次方程特解是：一般解：,系数a由初始条件确定。（5） 则 相减得：特征方程是：两个特征根是：因为 则（*）的解：（*）的解可表示为：其中是（*）的特解，比较后得： 代入（*）得即： 故 因为 则（*）的解： 其中是（*）的特解，比较后得： 代入（*）得即： 故 递推关系的一般解为： （6） （*） 则 相减得：特征方程是：两个特征根是：因为 则（*）的解： （*）的解可表示为：其中是（*）的特解，比较后得： 代入（*）得即： 故 因为 则（*）的解： 其中是（*）的特解，比较后得： 代入（*）得即： 故 递推

15、关系的一般解为： (7) 对应的特征方程： 有两个特征根：，其中令非齐次递推关系的特解为 代入递推关系得： 非递推关系的一般解为： ,系数a由初始条件确定。 (8) 对应的特征方程: 有两个特征根：, 令非齐次递推关系的特解为： 代入递推关系得： 非递推关系的一般解为： ,系数a由初始条件确定。 (9) 对应的特征方程: 有两个特征根：,其中 令非齐次递推关系的特解为： 代入递推关系得： 求的 特解为非递推关系的一般解为：，系数a由初始条件确定。（10） （*）齐次关系特征方程为：x27x+12=(x-3)(x-4)=0 则 假定特解为 得： =10* =12 特解为：12n一般解为 .+.+

16、10. +12.n.(11) (*)齐次特征解为 +2x-8=(x+4)(x-2)=03. 假定 特解 为 =kn 代入递推关系式kn+2 k（n-1）- 8k（n-2）= 3解得 k=2 =2n（-14）假设特解为: =c 代入递推关系式c+2 c-8 c= （-14）解得 c=-18 则=-18一般解为：+2 n-18(l2) 齐次递推关系式为：-6x+9=假设特征解为 =k 代入递推关系式k-6 k+9 k=解得：k= 特解为：一般解为：（+n）+2.28题（孙明柱）利用置换求解。解： 229 题（孙明柱）an=an-1an-2求这个递推关系的解解：设 bn= log2an 由an=an

17、-1an-2 得 bnbn-1bn-2=0 k(x)=x2x1=0 解得：r1=，r2= bn=a(r1)n+b(r2)n 由 得 bn=nn an=22.30 题（孙明柱）解递推式an=an-12an-23 解： 令： bn=log2anbn=log2(an-12an-23) =2log2an-1+3log2an-2=2bn-1+3bn-2 k(x)=x2-2x-3=0r1=3 r2=-1bn=a3n+b(-1)na0=1 b0=0a1=2 b1=1a+b=0 (1) 3a-b=1 (2) 由(1) (2)得：a=1/4 b=-1/4bn=(1/4)3n+(-1/4)(-1)nlog2an=

18、(1/4)3n+(-1/4)(-1)nan=22.31题（王健） = 令= = = 7- 12 =7-12 k(x)=-7x+12=0 =3 =4=a+b = 1 = 2 =0 =1 a+b=0 3a+4b=1 a=-1 b=1 =c- + = -+ =2.32题（王健） = n = 1 = (n-1) = (n-2) = (n-3) = 1 = n(n-1)(n-2)(n-3).1 =- = =7 = + =+=+=+=+.+ =7+(1-)= 8-=-=-=则-=-+=0即-+=0特征方程是 -x+=0特征根是b=1 m= bm解为=+其中 为常数任意为待定系数=1+ 其中是（*）的特解，

19、比较后得=k代入得k- k=即k-k= k=-故 =-=1-2.33题（王健）2.34题（王健）,求（an-1应该写成a0）又有等式的右端相当于从n+m+1个球中取n+1个球的组合。把这n+m+1个球编号，如果取出的n+1个球中最小编号是一，则得到如果最小编号是二则得到如果最小编号是m则得到 所以可得2.35题（王健）解题思路同上题2.36题（王健）（未完成）2.37题 （王居柱）解： 特征方程为：abn=a(3)+b(-1)当n=0时，b0=a+b=1;当n=1时，b1=3a-b=2得 a=3/4 b=1/4所以，2.38题（王居柱）解： 设bn的母函数为x : : ）2.39 题 （王居柱

20、） 利用置换,解: ,什么是置换？解： ，即：，由原式的a1=b1=1，则，所以，=.a ,(n=1)240题（王居柱）（3）解下列递推关系： -3=5*3,=0解：此题是二阶级性非齐次递推关系：-b=hmb=3,m=3,h=5,其中b=m由=0得k=0由公式=（k+hn）b得=（5n）32.41 题（王居柱）证明： +b+a=5r则：+ b a+=5r 同乘 r : r+r b a+r=5r 由-相减得到：+(b-r)+(- br)a-ra=0导致三阶齐次递推关系其特征多项式为：x+(b-r)x+(- br)x-r= (x-r)( x+ bx+)故证明！242题（王居柱）证明：由题知：-a=

21、0 -2-b=0c=+得：c=a+b c=a+b=2b+b b=2 b+b= a+ c= a+ a+2 b+ b= c+ c+ b = c+ c+2b+b= c+ c+5 b+2b c= a+ a+2 b+ b= 2a+5 b+2 b=3+2a+12 b+5 b=3c+2c+9 b+3 b *3-*2得c=3 c+3 c-6 c-4 c-3 b 由c= c+ c+ b所以 c= c+c+ bb= c- c-c 代入：c= 3c+ 3c-6 c+4 c-3 c+3 c+3 c=3c-3 c+7 c得c-3c-3 c+7 c=0满足一个四阶线性常系数递推关系：2.43题（王振华）已知an=an-1

22、+an-2;bn=2bn-1+bn-2;cn=anbn;n=0,1,2,求cn的递推关系。cn=anbn=(an-1+an-2)(2bn-1+bn-2)=2cn-1+cn-2+an-1bn-2+2an-2bn-1(1)=2cn-1+cn-2+(an-2+an-3)bn-2+2an-2(2bn-2+bn-3)=2cn-1+6cn-2+an-3bn-2+2an-2bn-3=2cn-1+6cn+an-3(2bn-3+bn-4)+2(an-3+an-4)bn-3=2cn-1+6cn-2+4cn-3+an-3bn-4+2an-4bn-3 (2)由(1)式得： an-1bn-2+2an-2bn-1=cn-

23、2cn-1+cn-2所以有an-3bn-4+2an-4bn-3=cn-2-2cn-3-cn-4代入(2)式得cn=2cn-1+7cn-2+2cn-3-cn-42-44设an和bn均满足递推关系xn+b1xn-1+b2xn-2=0，试证（1）anbn满足一个三阶齐次线性常系数递推关系（2）a0，a2，a4满足一个二阶线性常系数齐次递推关系解：(1) 设cn=anbn;cn=(-1)(b1an-1+b2an-2)(-1)(b1bn-1+b2bn-2)=b12cn-1+b22cn-2+b1b2(an-1bn-2+an-2) =b12cn-1+b22cn-2-b1b2(b1an-2+b2an-3)bn

24、-2+an-2(b1bn-2+b2bn-3)=b12cn-1+b22cn-2-b1b2b1cn-2+b2an-3bn-2+b1cn-2+b2an-2bn-3=b12cn-1+b22cn-2-b12b2(cn-2+cn-2)-b1b22(an-3bn-2+an-2bn-3)由得：b1b2(an-1bn-2+an-2bn-1)=cn-b12cn-1-b22cn-2b1b2(an-2bn-3+an-3bn-2)=cn-1-b12cn-2-b22cn-3cn=b12cn-1+b22cn-2-2b12b2cn-2-b2(cn-1-b12cn-2-b22cn-3) =(b12-b2)cn-1+(b22-2

25、b12b2+b12b2)cn-2+b23cn-3 =(b12-b2)cn-1+(b22-3b12b2)cn-2+b23cn-3(2)设cn=a2n n= 0,1,2cn=a2n=-(b1a2n-1+b2a2n-2)=-(b1a2n-1+b2cn-1) 因为：a2n-1=(-b1a2n-2-b2a2n-3)=-b1cn-1-b2a2n-3所以：cn=-b2cn-1+b1(b1a2n-2+b2a2n-3)=-b2cn-1+b12cn-1+b1b2a2n-3由得：b1a2n-1=-(cn+b2cn-1)b1a2n-3=-(cn-1+b2cn-2)cn=-b2cn-1+b12cn-1+b2(-cn-1

26、-b2cn-2)=b12cn-1-2b2cn-1-b22cn-2=(b12-2b2)cn-1-b22cn-22.44题（王振华）(a)已知an,bn均满足xn+b1xn-1+b2xn-2=0；求anbn的递推关系。设cn=anbn;cn=(-1)(b1an-1+b2an-2)(-1)(b1bn-1+b2bn-2)=b12cn-1+b22cn-2+b1b2(an-1bn-2+an-2) =b12cn-1+b22cn-2-b1b2(b1an-2+b2an-3)bn-2+an-2(b1bn-2+b2bn-3)=b12cn-1+b22cn-2-b1b2b1cn-2+b2an-3bn-2+b1cn-2+

27、b2an-2bn-3=b12cn-1+b22cn-2-b12b2(cn-2+cn-2)-b1b22(an-3bn-2+an-2bn-3)由得：b1b2(an-1bn-2+an-2bn-1)=cn-b12cn-1-b22cn-2b1b2(an-2bn-3+an-3bn-2)=cn-1-b12cn-2-b22cn-3cn=b12cn-1+b22cn-2-2b12b2cn-2-b2(cn-1-b12cn-2-b22cn-3) =(b12-b2)cn-1+(b22-2b12b2+b12b2)cn-2+b23cn-3 =(b12-b2)cn-1+(b22-3b12b2)cn-2+b23cn-3(b)设c

28、n=a2n n= 0,1,2cn=a2n=-(b1a2n-1+b2a2n-2)=-(b1a2n-1+b2cn-1) 因为：a2n-1=(-b1a2n-2-b2a2n-3)=-b1cn-1-b2a2n-3所以：cn=-b2cn-1+b1(b1a2n-2+b2a2n-3)=-b2cn-1+b12cn-1+b1b2a2n-3由得：b1a2n-1=-(cn+b2cn-1)b1a2n-3=-(cn-1+b2cn-2)cn=-b2cn-1+b12cn-1+b2(-cn-1-b2cn-2)=b12cn-1-2b2cn-1-b22cn-2=(b12-2b2)cn-1-b22cn-22.45题（王振华）已知f0

29、,f1,f2是fibonaci序列，试找出常数a,b,c,d使：f3n= afnfn+1fn+2+bfn+1fn+2fn+3+cfn+2fn+3fn+4+dfn+3fn+4fn+5解：当n=0时 f0=af0f1f2+bf1f2f3+cf2f3f4+df3f4f5当n=1时 f3=af1f2f3+bf2f3f4+cf3f4f5+df4f5f6当n=2时 f6=af2f3f4+bf3f4f5+cf4f5f6+df5f6f7当n=3时 f9=af3f4f5+bf4f5f6+cf5f6f7+df6f7f8f0=0,f1=1,f2=1,f3=2f4=3,f5=5,f6=8,f7=13,f8=21,f9

30、=34经验证当n=4时亦成立。2.46题（王振华）对所有的正整数a,b,c，恒有固定n ，利用第二归纳法可证当m=1时 fn+1=f1fn+1+f0fn，f0=f1=1fn+1=fn +fn+1成立假定当m=k时成立fk+n=(fkfn+1)+(fk-1fn)则要证m=k+1时fk+1+n=(fk+1fn+1)+(fkfn)fk+1+n=(fk+n)+(fk+n-1)=(fkfn+1)+(fk-1fn)+(fk-1fn+1)+(fk-2fn) =(fk+fk-1)(fn+1)+(fk-1)+fk-2)fn=(fk+1fn+1)+fkfn即证 所以代入右边即证2.47题（王振华）证明等式求(1+

31、x4+ x8)100中x20项的系数.解法一：利用第一章的第8节的公式7：令m = n, r = n即可。解法二：利用恒等式，比较两边的系数。或是观察母函数的常数项，都可以得到结论。4x+8y=20并且x+2y=5解得x=5,y=0;x=1,y=2；x=3,y=1。共91457520.2.48题（王卓）有红、黄、蓝、白球各两个，绿、紫、 黑的球各3个，问从中取出10个球，试问 有多少种不同的取法？解：(用指数型母函数，可得母函数,x10系数即为所求。)同色球看做是相同的。求(1+x+x2)4(1+x+x2+x3)3中x10的系数。(1-x3)4(1-x4)3/(1-x)7x3 : 0 0 0

32、1 1 2 2 3x4 : 0 1 2 0 1 0 1 0x : 10 6 2 7 3 4 0 1=6782.49题（王卓）求由a,b,c,d组成的允许重复的排列中 ab至少出现一次的排列数目。有没有其他方法？解 设an为所求个数，bn为不出现ab的串的个数an+bn=4n,bn=4bn-1-bn-2,an=4an-1+bn-2,b1=4,b2=15,b0=1,b3=56.x2-4x+1=0 解得x=。bn=s(2+)n+t(2-)ns=,t=2.50.题（王卓）求n位四进制数中2和3必须出现偶次的数目。解： 2.51题（王卓）.试求由a,b,c三个文字组成的n位符号串 中不出现aa图像的符号

33、串的数目。解 设不出现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).证法一 对m做归纳，m=0时，等式成立。 假设对m-1,等式成立。c(n,n)+c(n+1,n)+ + c(n+m-1,n)+c(n+m,n)=c(n+m,n+1)+c(n+m,n)=c(n+m,m-1)+c(n+m,m)=c

34、(n+m+1,n+1) =c(n+m+1,m).证毕。证法二： 等式的右端相当于从n+m+1个球中取n+1个球的组合。 把这n+m+1个球编号:如果取出的n+1个球中最小编号是1，则得到 c(n+m,n);如果最小编号是2则得到c(n+m-1,n)；如果最小编号是m则得到c(n,n)。于是就有c(n,n)+c(n+1,n)+c(n+m,n) = c(n+m+1,n+1) =c(n+m+1,m)2.53 题（翟聪）利用+。=，改善pn估计式。什么是那个估计式？ 解：由于lng(x) ，知道lnpn +nln+,所以。所以。2.54题（翟聪）8台计算机分给3个单位，第一个单位的分配量不超过3台，第

35、二个单位的分配量不超过4台，第三个单位的分配量不超过5台，问共有几种分配方案？ 解：利用母函数(1+ x1+x2+x3)(1+ x1+x2+x3+x4)(1+x1+x2+x3+x4+x5)，x8的系数就是该题的答案。x8的系数为14，所以该题答案：14。2.55 题（翟聪）证明任一个正整数n都可以写成不同的fibonacci数的和。这道题得好好看。 解：该题的意思就是证明n=，aiai+1=0，ai=0，1。其中f1= f2=1是相同的fibonacci数。对n用归纳法1） 当n=1时，命题成立2）设对小于n的正整数命题成立，对于n+1，如果存在i使得n+1=fi，显然成立。否则存在i，满足fi n+1 fi+1 。n+1fi可表示为不同的f数列的和，其其中每个得下表j