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

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题（顿绍坤）设=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)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+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.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= 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解得：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-)，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 (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 所以 =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,为其特征方程的两个特征根，则可知其特征方程为：（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是二重特征根，令特解为， =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=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=Gx227 题（孙明柱） 求下列递推关系的一般解：（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） 递推关系的特征方程为：，其两个特征根为0和-6右端可以看成，m=1，p=0，令特解代入递推关系：即：解的k=4故非其次方程特解是：一般解：,系数A由初始条件确定。（5） 则 相减得：特征方程是：两个特征根是：因为 则（*）的解：（*）的解可表示为：其中是（*）的特解，比较后得： 代入（*）得即： 故 因为 则（*）的解： 其中是（*）的特解，比较后得： 代入（*）得即： 故 递推关系的一般解为： （6） （*） 则 相减得：特征方程是：两个特征根是：因为 则（*）的解： （*）的解可表示为：其中是（*）的特解，比较后得： 代入（*）得即： 故 因为 则（*）的解： 其中是（*）的特解，比较后得： 代入（*）得即： 故 递推关系的一般解为： (7) 对应的特征方程： 有两个特征根：，其中令非齐次递推关系的特解为 代入递推关系得： 非递推关系的一般解为： ,系数A由初始条件确定。 (8) 对应的特征方程: 有两个特征根：, 令非齐次递推关系的特解为： 代入递推关系得： 非递推关系的一般解为： ,系数A由初始条件确定。 (9) 对应的特征方程: 有两个特征根：,其中 令非齐次递推关系的特解为： 代入递推关系得： 求的 特解为非递推关系的一般解为：，系数A由初始条件确定。（10） （*）齐次关系特征方程为：x27x+12=(x-3)(x-4)=0 则 假定特解为 得： =10* =12 特解为：12n一般解为 .+.+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-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=(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+ 其中是（*）的特解，比较后得=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 题 （王居柱） 利用置换,解: ,解： ，即：，由原式的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=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+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-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-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-2b12b2+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-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+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)设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-b2cn-2)=b12cn-1-2b2cn-1-b22cn-2=(b12-2b2)cn-1-b22cn-22.45题（王振华）已知F0,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=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+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 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图像的符号串的数目。解 设不出现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(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台，第二个单位的分配量不超过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都满足j。否则，Fi-1=n+1Fi Fi+1Fi=0)定义的（一阶）差分序列。 那么0，1，2 ，阶差分序列列成一行而得 举个例子 令序