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

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*+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+ 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.12 已知解：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 +……+（n+1）xn+……证明(1) G2 =（1-X）-4= Xn， (2) G2= Xn,其中an=，(3) an=C(n+3,3),n{0.1.2.3…….}解：设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因子的系数为(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*(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{0.1.2.3……}，又根据（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(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 ③ 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)+…)+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-25x=(A/1-5x)+(B/(1+5x)) G(x)=A(1+5x+(5x)+(5x)+…)+B(1+(-5x)+(-5x)+…) 则一般通解为: a=A*5+B*(-5)2．20 已知， （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和-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) 。