组合数学答案.doc

{0,1,8,27,……}的母函数。解:左右同乘再连加:母函数:…………,求母函数。解:的第k项为:,对于本题,n=4,母函数为:(X)=,求序列{} 解:G(X)==从而有:G(X)=G(X)=7-4=7*,求对应的序列。解:母函数为解得:A=2B=1所以设,i数。证明:,n=2,3,4…。求的母函数。解:设,则……①……②……③①-②+③,得:又已知,则,所以,设,则可列出方程组:,解得那么,{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)=。题解:(1)-(2)得::(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)相加得到:=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=:(a)(b)求H的表达式。证明:(a)……①……②①-②,得由组合的性质,所以那么,,得证。(b)设,B对应的序列为。根据(a),得,设G对应的序列为,则,根据母函数性质有,,那么,根据(a),。,并求母函数G。解:由题知:(1)(2)(1)-(2)得:(3)(4)(3)-(4)(5)(5)式即为的递推关系。所以序列{}的特征多项式为:又母函数可表示为因此,,即证。其中解方程组:解得:所以已知解:{}的母函数。解:…………----------------------------------------------G(x)=,求:解:。求序列的递推关系。解:因而:递推关系为:{an}的母函数为,求序列{an}的递推关系,并求a0,:c1=-1,c2=1则其特征多项式为:C(x)=x2-x+1与其对应的递推关系为:an-an-1+an-2= 解:当m=1时,的母函数就等于假设当m=k时成立,即(1) 当m=k+1时(2)因为,所以(2)里的,为(2)对应的序列,为(1)对应的序列。所以由性质3得 :已知G=1+2X+3X2+……+(n+1)xn+……证明(1)G2=(1-X)-4=n=0∞C(n+3,n)Xn, (2)G2=n=0∞anXn,其中an=k=0nk+1(n+1-k),(3)an=C(n+3,3),n∈{…….}解:设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+……)=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=n=0∞anXn,an=k=0nk+1(n+1-k)所以(2)得证。现在证(3),用数学归纳法:1)a0=k=00k+1(0+1-k)=C(0+3,3)=12)假设an=C(n+3,3)成立,即an=k=0nk+1(n+1-k)=C(n+3,3)3)证明an+1=C(n+1+3,3)成立,an+1=k=0n+1k+1(n+1+1-k)=[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)]=k