组合数学第二章习题解答.ppt

第二章习题;2.5设Gn=F2n,证明：Gn-3Gn-1+Gn-2=0,n=2,3,4,...求Gn的母函数;2.7G=1+2x2+3x4+4x6+...+(n+1)x2n+...;2.12;2.13;2.16用数学归纳法证明

C(m,m),C(m+1,m),C(m+2,m),...,C(m+n,m),...的母函数为

(1-x)-m-1;2.17：;2.24设an-2an-1+an-2=5,a0=1,a1=2,求解这个递推关系。;2.25分母展开求出an的递推关系，再求出bn的递推关系;2.27求以下递推关系的一般解;2.27求以下递推关系的一般解;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.48有红、黄、蓝、白球各两个，绿、紫、黑球各3个，问从中取出10个球，试问有多少种不同的取法？;2.49.求由A,B,C,D组成的允许重复的排列中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)。;台计算机分给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，..............;56.;57.相邻位不同为0的n位2进制数中一共出现了多少个0？?

解：...?

???设符合条件的n位二进制数的个数为hn这些数中一共

有an个0?

???当n位二进制数最高位为1时,符合条件的n位二进制数

的个数为hn-1

???最高位为0时，次高位必为1符合条件的n位二进制数的

个数为hn-2

hn=hn-1+hn-2,h1=2,h2=3,h0=1

即hn是F数列?;58.在Hanoi塔问题中，在柱A上从上到下套着n个圆盘，其编号依次从1到n。现要将奇数编号与偶数编号的圆盘分别转移到柱B和柱C上。转移规那么仍然是每次移动一个，始终保持上面的比下面的小。一共要移动多少次？;59.作图可证。;60.证明。用归纳法。;61.求长度为n的0,1符号串，只在最后两位才出现00的符号串总数。;62.在一圆周上取n个点，过一对顶点可作一弦，不存在三弦共点的现象。求弦把圆分割成几局部？;63.求n位二进制数中相邻两位不出现11的数的个数;6