发布时间 : 星期五 文章李凡长版-组合数学课后习题答案-习题3更新完毕开始阅读2012f124cd22bcd126fff705cc17552706225ef2
李凡长版-组合数学课后习题答案-习题3
第三章 递推关系
1. 在平面上画n条无限直线,每对直线都在不同的点相交,它们构成的无限
区域数记为f(n),求f(n)满足的递推关系.
解： f(n)=f(n-1)+2 f(1)=2,f(2)=4
解得f(n)=2n.
2. n位三进制数中,没有1出现在任何2的右边的序列的数目记为f(n),求
f(n)满足的递推关系.
解：设an-1an-2…a1是满足条件的n-1位三进制数序列，则它的个数可以用f(n-1)
表示。
an可以有两种情况：
1） 不管上述序列中是否有2，因为an的位置在最左边，因此0
和1均可选；
2） 当上述序列中没有1时，2可选； 故满足条件的序列数为
f(n)=2f(n-1)+2n-1 n?1, f(1)=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). 解：这种序列有两种情况：
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”的可能；
依此类推，有
17
f(n)+f(n-1)+f(n-2)+…+f(2)=2n-2
f(2)=1,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）；
同理，k?3时，第n-k-2到n-k位第一次出现010的个数为 k-3
2f(n-k)(因为第n-k位～n-3位中间的k-3位可以取0、1，所以有2k-3种状态)。
所以满足条件的递推关系为
f(n)+f(n-2)+f(n-3)+…+2n-6f(3)=2n-3 n?6 f(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三个字母组成的长为n的字符串,若字符串中有两
个a连续出现,则信道就不能传输.令f(n)表示信道可以传输的长为n的字符串的个数,求f(n)满足的递推关系.
解：信道上能够传输的长度为n（n?2）的字符串可分成如下四类：
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) (n?3) f(1)=3,f(2)=8. 9. 求解下列递推关系：
?f(n)?2f(n?1)?2f(n?2)（1）?；
?f(1)?3,f(2)?8解：先求这个递推关系的通解，它的特征方程为x2-2x－2=0
解这个方程，得x1?1?3,x2?1?3. 18
所以，通解为f(n)?c1(1?3)n?c2(1?3)n. 代入初值来确定c1和c2，得c1?2?3?2?3，c2?. 2323
因此，f(n)?2?3?2?3(1?3)n?(1?3)n. 2323（2）??f(n)?4f(n?1)?4f(n?2)；
?f(0)?1,f(1)?3
解：此递推关系的特征方程为x2-4x+4=0 解这个方程，得x1=x2=2. 所以通解为f(n)=c12n+c2n2n.
代入初值来确定c1和c2，得c1=1，c2=1/2. 因此，f(n)=2n+2n-1n.
?f(n)??f(n?1)?3f(n?2)?5f(n?3)?2f(n?4)（3）?；
?f(0)?1,f(1)?0,f(2)?1,f(3)?2解：该递推关系的特征方程为x4+x3-3x2-5x-2=0, 解得特征根为x1=x2=x3=-1,x4=2.
所以通解为f(n)=c1(-1)n+c2n(-1)n+c3n2(-1)n+c42n. 代入初值，得c1?,c2??,c3?0,c4?.
939n因此，f(n)?(?1)71279?(?1)n13n?29?2.
n?f(n)?4f(n?1)?4f(n?2)?n?2n（4）?；
?f(0)?0,f(1)?1解：由于2是特征方程的二重根，所以该递推关系的特解为 f?(n)=n2(b1n+b0)·2n.
将它代入递推关系化简，得到 6b1=1, -6b1+2b0=0 解得b0?12
，b1?16.
而相应齐次递推关系的通解为(c0+c1n)·2n，从而非齐次递推关系的通解为
f(n)?(c0?c1n)?n????2?n?1???2n.
??62???1
19
代入初值可得c0?0，c1??.
6