《李凡长版组合数学课后习题答案习题》由会员分享，可在线阅读，更多相关《李凡长版组合数学课后习题答案习题（9页珍藏版）》请在金锄头文库上搜索。
1、第三章 递推关系1. 在平面上画n条无限直线,每对直线都在不同的点相交,它们构成的无限区域数记为f(n),求f(n)满足的递推关系.解： f(n)=f(n-1)+2f(1)=2,f(2)=4解得f(n)=2n.2. n位三进制数中,没有1出现在任何2的右边的序列的数目记为f(n),求f(n)满足的递推关系.解：设an-1an-2a1是满足条件的n-1位三进制数序列，则它的个数可以用f(n-1)表示。an可以有两种情况：1） 不管上述序列中是否有2，因为an的位置在最左边，因此0和1均可选；2） 当上述序列中没有1时，2可选；故满足条件的序列数为f(n)=2f(n-1)+2n-1 n1,f(1)
2、=3解得f(n)=2n-1(2+n).3. n位四进制数中,2和3出现偶数次的序列的数目记为f(n),求f(n)满足的递推关系.解：设h(n)表示2出现偶数次的序列的数目，g(n)表示有偶数个2奇数个3的序列的数目，由对称性它同时还可以表示奇数个2偶数个3的序列的数目。则有h(n)=3h(n-1)+4n-1-h(n-1),h(1)=3 （1）f(n)=h(n)-g(n),f(n)=2f(n-1)+2g(n-1) （2）将（1）得到的h(n)=(2n+4n)/2代入（2），可得f(n+1)= (2n+4n)/2-2f(n),f(1)=2.4. 求满足相邻位不同为0的n位二进制序列中0的个数f(n
3、).解：这种序列有两种情况：1)最后一位为0，这种情况有f(n-3)个；2)最后一位为1，这种情况有2f(n-2)个；所以f(n)=f(n-3)+2f(n-2)f(1)=2,f(2)=3,f(3)=5.5. 求n位0,1序列中“00”只在最后两位才出现的序列数f(n).解：最后两位是“00”的序列共有2n-2个。f(n)包含了在最后两位第一次出现“00”的序列数，同时排除了在n-1位第一次出现“00”的可能；f(n-1)表示在第n-1位第一次出现“00”的序列数，同时同时排除了在n-2位第一次出现“00”的可能；依此类推，有f(n)+f(n-1)+f(n-2)+f(2)=2n-2f(2)=1,
4、f(3)=1,f(4)=2.6. 求n位0,1序列中“010”只出现一次且在第n位出现的序列数f(n).解：最后三位是“010”的序列共有2n-3个。包括以下情况：f(n)包含了在最后三位第一次出现010的个数，同时排除了从n-4到n-2位第一次出现010的可能；f(n-2)包含了从n-4到n-2位第一次出现010的个数；f(n-3)包含了从n-5到n-3位第一次出现010的个数；2f(n-4)包含了从n-6到n-4位第一次出现010的个数（因为在第n-3位可以取0或1）；同理，k3时，第n-k-2到n-k位第一次出现010的个数为2k-3f(n-k)(因为第n-k位n-3位中间的k-3位可以
5、取0、1，所以有2k-3种状态)。所以满足条件的递推关系为f(n)+f(n-2)+f(n-3)+2n-6f(3)=2n-3 n6f(3)=1,f(4)=2,f(5)=3.7. 有多少个长度为n的0,1序列,在这些序列中,既不包含“010”,也不包含“101”？解：设满足条件的序列数为f(n)考虑n-1位时最左边的情况：1) 最左边为1，则左边可选0或1生成满足要求的序列，这种情况有2f(n-2)个；2) 最左边为01，则左边只能选1才能满足要求，这种情况有f(n-3)个；f(n)=2f(n-2)+f(n-3)f(2)=1,f(3)=1,f(4)=2.8. 在信道上传输a,b,c三个字母组成的长
6、为n的字符串,若字符串中有两个a连续出现,则信道就不能传输.令f(n)表示信道可以传输的长为n的字符串的个数,求f(n)满足的递推关系.解：信道上能够传输的长度为n（n2）的字符串可分成如下四类：1) 最左字符为b；2) 最左字符为c；3) 最左两个字符为ab；4) 最左两个字符为ac；前两类字符串分别有f(n-1)个，后两类字符串分别有f(n-2)个。容易求出f(1)=3,f(2)=8。从而得到f(n)=2f(n-1)+2f(n-2) (n3)f(1)=3,f(2)=8.9. 求解下列递推关系：（1）；解：先求这个递推关系的通解，它的特征方程为x2-2x2=0解这个方程，得,.所以，通解为.
7、代入初值来确定c1和c2，得，.因此，.（2）；解：此递推关系的特征方程为x2-4x+4=0解这个方程，得x1=x2=2.所以通解为f(n)=c12n+c2n2n.代入初值来确定c1和c2，得c1=1，c2=1/2.因此，f(n)=2n+2n-1n.（3）；解：该递推关系的特征方程为x4+x3-3x2-5x-2=0,解得特征根为x1=x2=x3=-1,x4=2.所以通解为f(n)=c1(-1)n+c2n(-1)n+c3n2(-1)n+c42n.代入初值，得.因此，.（4）；解：由于2是特征方程的二重根，所以该递推关系的特解为f(n)=n2(b1n+b0)2n.将它代入递推关系化简，得到6b1=
8、1,-6b1+2b0=0解得，.而相应齐次递推关系的通解为(c0+c1n)2n，从而非齐次递推关系的通解为.代入初值可得，.于是.（5）；解：f(1)=f(0)+1! f(2)=2f(1)+2!=2f(0)+2*2!=2!(f(0)+2) f(3)=3f(2)+3!=6f(0)+3*3!=3!(f(0)+3) f(n)=n!(f(0)+n)=n!(n+1).（6）；解：f(n)=(n+2)f(n-1)=(n+2)(n+1)f(n-2)=(n+2)(n+1)3f(0)=(n+2)!/2.10. 在一圆周上取n个点,过每对点作一弦,且任何三条弦不在圆内共点,试求这些弦把圆分成的区域的个数.解：n-
9、1个点把圆分为f(n-1)部分，在加第n个点则对于前n-1个点来说，每选3个点都有3条弦构成了一个三角形。而中间的一点和第n点的连线把中间和第n点间的弦分成了2个部分，增加了1一个域。第n个点和其它n-1个点的连线又把第1，n-1，n点构成的三角形分为n个域。故满足条件的递推关系为f(n)=f(n-1)+C(n-1,3)+n-1，f(0)=1,f(1)=1,f(2)=2,f(3)=4,f(4)=8.解得f(n)=1+C(n,2)+C(n-4).11. 设有n条椭圆曲线，两两相交于两点，任意3条椭圆曲线不相交于一点.问这样的n个椭圆将平面分割成多少部分?解：设f(n)表示n个椭圆将平面分割成的部
10、分的个数，则有：一个椭圆将平面分成内、外两个部分，两个椭圆将平面分成4个部分。第二个椭圆的周界被第一个椭圆分成两部分，这恰恰是新增加的域的边界。依此类推，第三个椭圆曲线被前面两个椭圆分割成4部分，将平面分割成448个部分。若n1个椭圆将平面分割成f(n-1)个部分，第n个椭圆和前n1个椭圆两两相交于两点，共2（n1）个交点，即新增加的域有2（n1）个。故有 f(n)=f(n-1)+2(n-1)f(1)=2解得f(n)=n(n-1)+212. 求n位十进制正数中出现偶数个5的数的个数.解：设f(n)表示n位十进制正数中出现个5的数的个数，d=d1d2dn-1表示n-1位十进制数，则若d含有偶数个
11、5，则dn取5以外的任何一个数；若d含有奇数个5，则dn取5。另n-1位十进制的数共有910n-2个，故递推关系为f(n)=9f(n-1)+ 910n-2-f(n-1)= 910n-2+8f(n-1)f(1)=8.13. 在一个平面上画一个圆,然后一条一条地画n条与圆相交的直线.当r是大于1的奇数时,第r条直线只与前r1条直线之一在圆内相交.当r是偶数时,第r条直线与前r1条直线都在圆内相交.如果无3条直线在圆内共点,这n条直线把圆分割成多少个不重叠的部分？解：当r是奇数时，它只与原来r1条直线之一相交，因此多了两个部分；当r是偶数时，它与原来的r1条都相交，因此多了r个交点；故有f(n)=f
12、(n-1)+2 n为奇数；f(n)=f(n-1)+n n为偶数；14. 从1到n的自然数中选取k个不同且不相邻的数,设此选取的方案数位f(n,k).1) 求f(n,k)满足的递推关系；2) 用归纳法求f(n,k)；3) 若设1与n算是相邻的数,并在此假定下从1到n的自然数中选取k个不同且不相邻的数的方案数位g(n,k),试利用f(n,k)求g(n,k).解：1）有两类：选n为f(n-2,k-1)；不选n为f(n-1,k).所以f(n,k)=f(n-2,k-1)+f(n-1,k). 2)f(n,k)=C(n-k+1,k). 3)f(n,k)=C(n-k+1,k-1)*n/k.15. 从1到n的自
13、然数中选取两两之差均大于r的k个数1) 求它所满足的递推关系；2) 证明解：可将本题转换为构造相应的01串的问题。将这样的n位01串与1到n的正整数对位，与1相应的整数选取，与0相应的不取。一个01串对应一个选取方案。这也对应将相同的球放入不同的盒子的方案数。所以。16. 试证：证明：可用数学归纳法证明1) 当n=1时，左边= ，右边=，成立。2) 假设n=k时，等式成立，则有.n=k+1时，有由1)、2）可得等式成立。17. 设,用Fibonacci数来表示和.解：同理可得。由此可得两个序列的生成函数为。联立解可得。由Fibonacci数定义可知，f(n)=f(n-1)+f(n-2)，其生成
14、函数为。令，可得所以f(2n), f(2n-1).18. 某人有n元钱,他每天买一次物品,每次买物品的品种很单调,或者买一元的甲物品,或者买二元钱的乙物品,或者买二元钱的丙物品.问,他花完这n元钱有多少种不同的方式？解：f(n)表示花完这n元钱的方案数。则f(n)=f(n-1)+2f(n-2)f(1)=1,f(2)=3.19. 证明：任一个正整数n都可以写成不同的Fibonacci数的和.证明：任意正整数n可以表示为Fibonacci序列的有限和，即n=,其中Si=(0,1),i=1,2,m;SiSi+1=0,i=1,2,m-1.可以用数学归纳法进行证明。1) n=1=f(0)=f(1),成立
15、。2) 假设n=k时等式成立，则n=k+1亦成立，因为1也是Fibonacci数。3) 由1)、2）可证等式成立。20. 证明：有n个叶子的完全二叉树的个数为Catalan数.证明：令Pn表示给n个叶子安排位置的方案数,则有Pn=P1Pn-1+P2Pn-2+Pn-1P1,P1=P2=1.显然，Pk=Ck+1,k=1,2,n.21. 证明：从（0,0）点到（n,n）点的除端点外不接触直线y=x的路径数为2h(n),其中,h(n)为Catalan数.证明：此题可划分为两部分：一部分从（0，0）到（n，n）的路径全部在y=x上方，另一部分全部在下方，由于对称性，故只要考虑一部分即可。记O点（0，0），A点（n，n），O点（0，
