1 7 第三章 递推关系 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 n1, 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”的可能； 依此类推，有 1 8 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）； 同理，k3 时，第 n-k-2...
