17
第三章 递推关系
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)满足的递推关系. 解:设a n-1a n-2…a 1是满足条件的n-1位三进制数序列,则它的个数可以用f(n-1)表示。
a n 可以有两种情况:
1) 不管上述序列中是否有2,因为a n 的位置在最左边,因此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),可得 n +4n )/2-2f(n), 4. 求满足相邻位不同为0的n 位二进制序列中0的个数f(n). 解:这种序列有两种情况:
1)最后一位为0,这种情况有f(n-3)个; 2)最后一位为1,这种情况有2f(n-2)个;
所以
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”的可能;
依此类推,有
18
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的个数为 2k-3
f(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. 求解下列递推关系:
(1)()2(1)2(2)(1)3,(2)8
f n f n f n f f =-+-??==?;
解:先求这个递推关系的通解,它的特征方程为x 2-2x -2=0
解这个方程,得11x =,21x =
19
所以,通解为12()(1(1n n f n c c =+.
代入初值来确定c 1和c 2
,得1c =
2c =.
因此,()n n f n =
+. (2)()4(1)4(2)
(0)1,(1)3
f n f n f n f f =---??
==?;
解:此递推关系的特征方程为x 2-4x+4=0 解这个方程,得x 1=x 2=2. 所以通解为f(n)=c 12n +c 2n2n .
代入初值来确定c 1和c 2,得c 1=1,c 2=1/2.
因此,f(n)=2n +2n-1n.
(3)()(1)3(2)5(3)2(4)(0)1,(1)0,(2)1,(3)2
f n f n f n f n f n f f f f =--+-+-+-??====?;
解:该递推关系的特征方程为x 4+x 3-3x 2-5x-2=0, 解得特征根为x 1=x 2=x 3=-1,x 4=2.
所以通解为f(n)=c 1(-1)n +c 2n(-1)n +c 3n 2(-1)n +c 42n .
代入初值,得12347
1
2
,,0,9
3
9
c c c c ==-==.
因此,712()(1)(1)
29
3
9
n
n
n
f n n =---+
?.
(4)()4(1)4(2)2(0)0,(1)1
n
f n f n f n n f f ?--+-=??==?;
解:由于2是特征方程的二重根,所以该递推关系的特解为
f '(n)=n 2(b 1n+b 0)·2n .
将它代入递推关系化简,得到 6b 1=1, -6b 1+2b 0=0
解得012
b =
,116
b =
.
而相应齐次递推关系的通解为(c 0+c 1n)·2n ,从而非齐次递推关系的通解为
2
011()()262n n f n c c n n =+++??
??? ??
????
?
.
代入初值可得00c =,116
c =-
.
20 于是321
()(3)26
n f n n n n =+-?.
(5)()(1)! (1)(0)2
f n nf n n n f =-+≥??=?;
解: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)()(2)(1) (1)(0)1f n n f n n f =+-≥??=?
;
解:f(n)=(n+2)f(n-1)=(n+2)(n+1)f(n-2)=… =(n+2)(n+1)…3·f(0)=(n+2)!/2.
10. 在一圆周上取n 个点,过每对点作一弦,且任何三条弦不在圆内共点,试
求这些弦把圆分成的区域的个数.
解:n-1个点把圆分为f(n-1)部分,在加第n 个点则对于前n-1个点来说,每选3个点都有3条弦构成了一个三角形。而中间的一点和第n 点的连线把中间和第n 点间的弦分成了2个部分,增加了1一个域。第n 个点和其它n-1个点的连线又把第1,n-1,n 点构成的三角形分为n 个域。 故满足条件的递推关系为
,
解得 f(n)=1+C(n,2)+C(n-4). 11. 设有n 条椭圆曲线,两两相交于两点,任意3条椭圆曲线不相交于一点.
问这样的n 个椭圆将平面分割成多少部分?
解:设f(n)表示n 个椭圆将平面分割成的部分的个数,则有:一个椭圆将平面分成内、外两个部分,两个椭圆将平面分成4个部分。第二个椭圆的周界被第一个椭圆分成两部分,这恰恰是新增加的域的边界。依此类推,第三个椭圆曲线被前面两个椭圆分割成4部分,将平面分割成4+4=8个部分。若n -1个椭圆将平面分割成f(n-1)个部分,第n 个椭圆和前n -1个椭圆两两相交于两点,共2(n -1)个交点,即新增加的域有2(n -1)个。故有 f(n)=f(n-1)+2(n-1) f(1)=2
解得f(n)=n(n-1)+2
12. 求n 位十进制正数中出现偶数个5的数的个数.
解:设f(n)表示n 位十进制正数中出现个5的数的个数,d=d 1d 2…d n-1表示n-1位十进制数,则若d 含有偶数个5,则d n 取5以外的任何一个数;若d 含有奇数个5,则d n 取5。另n-1位十进制的数共有9×10n-2个,故递推关系为
f(n)=9f(n-1)+ 9×10n-2-f(n-1)= 9×10n-2+8f(n-1) f(1)=8.
21
13. 在一个平面上画一个圆,然后一条一条地画n 条与圆相交的直线.当r 是
大于1的奇数时,第r 条直线只与前r -1条直线之一在圆内相交.当r 是偶数时,第r 条直线与前r -1条直线都在圆内相交.如果无3条直线在圆内共点,这n 条直线把圆分割成多少个不重叠的部分?
解:当r 是奇数时,它只与原来r -1条直线之一相交,因此多了两个部分; 当r 是偶数时,它与原来的r -1条都相交,因此多了r 个交点; 故有
f(n)=f(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 的自然数中选取两两之差均大于r 的k 个数
1) 求它所满足的递推关系;
2) 证明(,),(1)r n rk r f n k n r k r k -+??
=+≥+ ???
解:可将本题转换为构造相应的0-1串的问题。将这样的n 位0-1串与1
到n 的正整数对位,与1相应的整数选取,与0相应的不取。一个0-1串对应一个选取方案。这也对应将相同的球放入不同的盒子的方案数。
{{{10...010...01......10...01k r
r
r
64444744448
所以1(1)1(1)(,)(1)r k n k r k n r k f n k n k r k k ++------????
== ? ?---????
。 16. 试证:111110n
n n n
n F F F F +-???
?= ? ?????
证明:可用数学归纳法证明
1) 当n=1时,左边= 1110?? ???,右边=1110?? ???
,成立。 2) 假设n=k 时,等式成立,则有1
11110k
k k k
k F F F
F +-??
??= ? ?????
. n=k+1时,有
22 1
112
111
111101110k k k k k k k k k k k k k k k F F F F F F F F F F F F F F +++++--++==+??????
????= ? ? ? ? ?
??????????
由1)、2)可得等式成立。
17. 设0n ≥,02n
n k n k a k =+=??
???∑,1
021n n k n k b k -=+=+?? ???
∑,用Fibonacci 数来表示n a 和n b . 解:
1
1100001211222122221n n n n n k k k k n k n k n k n k n n k a k k k k n k +++====++++++++==+=++-++??????????????
? ? ? ? ? ? ??
?????????????∑∑∑∑
1n n a b +=+
同理可得1n n n b a b +=+。
由此可得两个序列的生成函数为()()1(),()11B x B x x A x A x x x
=
+=
--。
联立解可得2
2
()1(),31
31
B x x x
A x x x x x =
-=-+-+。
由Fibonacci 数定义可知,f(n)=f(n-1)+f(n-2),其生成函数为
2
1()1F x x x =
--。
令0
1
()(2)()(21),n
n
n n P x f n x Q x f n x ∞
∞
====-∑∑,可得
22()1(),31
31
Q x x x P x x x x x =
-=
-+-+
所以n a =f(2n), n b =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=2m
i i i S F =∑,其中S i =(0,1),i=1,2,…m;S i S i+1=0,i=1,2,…,m-1.
23
可以用数学归纳法进行证明。 1) n=1=f(0)=f(1),成立。
2) 假设n=k 时等式成立,则n=k+1亦成立,因为1也是Fibonacci 数。 3) 由1)、2)可证等式成立。
20. 证明:有n 个叶子的完全二叉树的个数为Catalan 数. 证明:令P n 表示给n 个叶子安排位置的方案数,则有 P n =P 1P n-1+P 2P n-2+…+P n-1P 1,P 1=P 2=1. 显然,P k =C k+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,1),A'点(n ,n +1)。
从O 点出发经过OA 及OA 上方的点到达A 点的路径对应一条从O'点出发经过O'A'点及O'A'上方的点到达A'点的路径。这是很显然的。
从O'点出发途经OA 上的点到达A'点的路径,即为从O'点出发穿越O'A'到达A'点的路径。故对应一条从O 点出发穿越OA 到达A 点的路径。
所以,从O 点出发经过OA 及OA 上方的点最后到达A 点的路径数,等于从O'出发到达A'点的所有路径数,减去从O'点出发途经OA 上的点到达A'的路径数。即
222111n n n n n n n -=++????
?? ? ? ???????
。 总的路径数为221n n n +?? ???
。