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

《组合数学+卢开澄版++答案第二章.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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=2B=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*

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

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用数学归纳法证明序列的母函数为解

5、：当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+3X

6、2+……+（n+1）xn+……）=G1×G2所以在G2中xn的系数由(n+1)部分组成：如果G1中取的因子为xk那么G2中只能去Xn-k,只有这样G1×G2后才能得出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

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