组合数学第二章习题解答

第二章习题,2.3已知序列C(3,3),C(4,3),.,C(n+3,3),.,求母函数。,2.5设Gn=F2n,证明：Gn-3Gn-1+Gn-2=0,n=2,3,4,.求Gn的母函数,2.7G=1+2x2+3x4+4x6+.+(n+1)x2n+.,解：令t=x2代入上式G=1+2t+3t2+4t3+.+(n+1)tn+.=1/(1-x)2=1/(1-x2)2,证明（1-3x+3x2-x3)G是一个多项式，并求母函数G,2.12已知,求序列an的母函数,2.13已知,求序列an的母函数,2.16用数学归纳法证明C(m,m),C(m+1,m),C(m+2,m),.,C(m+n,m),.的母函数为(1-x)-m-1,当m=1时成立，设m=k时成立。也就是：C(k,k),C(k+1,k),C(k+2,k),.,C(k+n,k),.的母函数为(1-x)-k-1,因此，m=k+1时成立,2.17已知：,证明：,2.24设an-2an-1+an-2=5,a0=1,a1=2,求解这个递推关系。,可认为是(1)n5,1是2重根，特解是kn2代入递推关系：kn2-2k(n-1)2+k(n-2)2=5,k=5/2一般解是：k1+k2n+5n2/2,2.23设an=(k1+k2n)(-3)n,k1,k2是常数，求an的递推关系。,特征方程为(x+3)2=x2+6x+9=0,递推关系为an+6an-1+9an-2=0,2.25分母展开求出an的递推关系，再求出bn的递推关系,2.26逐项展开，两边合并。,将分母展开(1-x)(1+x-x2)=1-2x2+x3,因此an满足递推关系：an-2an-2+an-3=0,a0=4,a1=-3,b0=4,b1=-7,母函数为：,an-an-1+an-1-an-2-an-2+an-3=bn+bn-1-bn-2=0,2.27求下列递推关系的一般解,(a)an-4an-1=5n,2.27求下列递推关系的一般解,(e)an-4an-1=25n-34n,2.28,2.30,2.31,2.32(a),2.32(b),2.32(c),2.33F0,F1,F2是费卜拉契序列，求解：an-an-1=Fn+2Fn-1,2.34求解：an=an-1+C(n+2,3),a0=0,2.35求解：an=an-1+C(n+3,4),a0=0,2.36利用迭代法解,2.37利用置换an=bn2,解：,2.38利用置换an=n!bn,解：,2.39利用置换an=bn/n,解：,2.40解下列递推关系,2.41设an满足：an+b1an-1+b2an-2=5rn,2.42设an满足：an-an-1-an-2=0,bn满足：bn-2bn-1-bn-2=0,cn=an+bn,证cn满足一个四阶线性常系数齐次递推关系。,2.42设an满足：an-an-1-an-2=0,bn满足：bn-2bn-1-bn-2=0,cn=anbn,证cn满足一个四阶线性常系数齐次递推关系。,2.43设an,bn满足：xn+b1xn-1+b2xn-2=0,证anbn满足一个四阶线性常系数齐次递推关系。a0,a2,a4满足,2.44设an,bn满足：xn+b1xn-1+b2xn-2=0,证anbn满足一个四阶线性常系数齐次递推关系。a0,a2,a4满足一个二阶线性常系数递推关系。,2.45设F0,F1,F2是费卜拉契数列，试找出常数a,b,c,d使F3n=aFnFn+1Fn+2+bFn+1Fn+2Fn+3+cFn+2Fn+3Fn+4+dFn+3Fn+4Fn+5,2.47证明等式,2.求中项的系数.,2.题目解：,分析的结构可知仅当时有项,三个系数相加即为所求,2.48有红、黄、蓝、白球各两个，绿、紫、黑球各3个，问从中取出10个球，试问有多少种不同的取法？,用指数型母函数，可得母函数,系数即为所求。,2.49.求由A,B,C,D组成的允许重复的排列中AB至少出现一次的排列数目。,解：先求不出现的，设an-1,an-2分别是取n-1和n-2不出现AB的排列数。,50、对符合题设要求的排列如果0可以出现在最高位，则可得母函数：,但是对n位四进制数来说最高位不能为0。最高位等零等于n-1位的4进制数。,2.51.试求由A,B,C,这三个字母组成的n位符号串中不出现aa图像的符号串的数目。,解递推关系即可：,2.52.证明：C(n,n)+C(n+1,n)+.+C(n+m,n)=C(n+m+1,m)。,2.54.8台计算机分给3个单位，第1个单位的分配量不超过3台，第2个单位的分配量不超过4台，第3个单位的分配量不超过5台，问共有几种分配方案？,用归纳法可证明：1）当k=1时命题成立2）设当k=N时命题成立即N可唯一表示成不同的F数之和。则当k=N+1时，明显可以分成N的序列再加上1（F1），但这可能会不能满足“不同”的条件。下面予以讨论1、如果原来不存在F1，则命题成立。2、如果存在F1则写成F2，如果存在F2,F1与F2合并成F3,如果原来不存在F3,成立，否则3、F2则与F3合成F4，.,2.55.证明正整数n都可以唯一地表示成不同的且不相邻的Fibonacci数之和。即,56.,57.相邻位不同为0的n位2进制数中一共出现了多少个0？解：.设符合条件的n位二进制数的个数为hn这些数中一共有an个0当n位二进制数最高位为1时,符合条件的n位二进制数的个数为hn-1最高位为0时，次高位必为1符合条件的n位二进制数的个数为hn-2hn=hn-1+hn-2,h1=2,h2=3,h0=1即hn是F数列,58.在Hanoi塔问题中，在柱A上从上到下套着n个圆盘，其编号依次从1到n。现要将奇数编号与偶数编号的圆盘分别转移到柱B和柱C上。转移规则仍然是每次移动一个，始终保持上面的比下面的小。一共要移动多少次？,设n为偶数1）先把n-1个盘通过C移到B2）把第n个盘移到C3）把n-3个盘通过C移到A4）把第n-2个盘移到B对n为奇数时上述四步仍然成立，但是B、C对调。,其中,为Hanota数列。,59.作图可证。,60.证明。用归纳法。,61.求长度为n的0,1符号串，只在最后两位才出现00的符号串总数。,最后两位是00，倒数第三位必须是1，最后三位是100，因此：,62.在一圆周上取n个点，过一对顶点可作一弦，不存在三弦共点的现象。求弦把圆分割成几部分？,设n-1个点把圆分为an-1个部分加上第n个点则增加了n-1条弦增加的第1条弦，被其他弦分成1段（没被分割）增加的第2条弦，被其他弦分成1x(n-2-1)+1段增加的第n-2条弦，被其他弦分成(n-3)x(n-2-n+3)+1段增加的第n-1条弦，被其他弦分成1段,63.求n位二进制数中相邻两位不出现11的数的个数,64.从n个文字中取k个文字作允许重复的排列，但不允许一个文字连续出现3次，求这样的排列的数目。,首先，假设am-1的最后一位为“5”，最后一位与5不同的取法有(n-1)种，少算了最后一位也取5的情况，就是最后两位都是5的情况，也就是最后两位与倒数第三位不同的情况，有(n-1)am-1种。,是n的4次方,满足第推关系,设,65.求14+24+.+n4之和,66.求矩阵,只要求出K即可,69.用an记具有整数边长、周长为n的三角形的个数。,a.证明,I当n是偶数时对所有符合条件的ar-3来说，每边增加一个单位，则可构成符合条件的ar。,设短边为a、b，长边为c，则(a+b)-c=2即a+b-2c-1，对所有符合条件的ar来说，每边减少1各单位，则可构成符合条件的ar-3,II当n为奇数时由I的讨论知，ar比ar-3多了a+b-c=1的三角形。由a+b+c=n，c=n-a-b,可知：,当(n+1)/2能被2整除时，这种三角形有(n+1)/4个,当(n+1)/2不能被2整除时，这种三角形有(n-1)/4个,70.(a)证明边长为整数、最大边长为l的三角形的个数是：,解：.（a）l=1时，只有一种可能（即3边都是长度为1）。l=2时，有两种可能（即“1，2，2”、“2，2，2”）。设三角形的3边边长为x、y、z，且。xyz=l,x+yzl=2k+1时,x+yl,x+y2lx+y=2k+2时，有k+1种方案，即“1，2k+1”、“2，2k”、.、“k+1，k+1”。x+y=2k+3时，有k种方案，即“2，2k+1”、“3，2k”、.、“k+1，k+2”。x+y=2k+4时，有k种方案，即“3，2k+1”、“4，2k”、.、“k+2，k+2”。x+y=4k+1时，有1种方案，即“2k，2k+1”。x+y=4k+2时，有1种方案，即“2k+1，2k+1”。,l=2k时x+y=2k+1时，有k种方案，即“1，2k”、“2，2k-1”、.、“k，k+1”。x+y=2k+2时，有k种方案，即“2，2k”、“3，2k-1”、.、“k+1，k+1”。x+y=2k+3时，有k-1种方案，即“3，2k”、“4，2k”、.、“k+1，k+2”。x+y=4k-1时，有1种方案，即“2k-1，2k”。x+y=4k时，有1种方案，即“2k，2k”。,(b)设fn记边长不超过2n的三角形的个数，而gn记边长不超过2n+1的三角形的个数，求fn和gn的表达式。,74.,75.设F1=F2=1,Fn=Fn-1+Fn-2(a)证明：Fk=FkFn-k+1+Fk-1Fn-k,nk1(b)证明：FnFm的充要条件是nm(c)证明：FmFn=Fm+n-2+Fm+n-6+Fm+n-10+.,(d)证明(Fm,Fn)=F(m,n),(m,n)为m,n的最大公约数。,1）证明用数学归纳法Ik=2时成立，Fn=F2Fn-1+F1Fn-2,II设k=m时成立Fn=FmFn-m+1+Fm-1Fn-m,III当k=m+1时,Fm+1Fn-m+FmFn-m-1=Fn-m(Fm+Fm-1)+FmFn-m-1=Fm(Fn-m+Fn-m-1)+Fn-mFm-1=Fn,2）证明Fm与Fm-1互素(用归纳法可证),作了k次后若n-kmm,则上式,3）证明当n是偶数时，最后一次会出现F0=0项当n是奇数时，最后一次会出现F1=1项,4）证明用2）的结论下面证明是最大公约数设F(n,m)不是最大公约数，FN是,则m|N,n|N则N=(n,m)矛盾是最大公约数:,76.在从1到n的自然数中选取k个不同且