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) 求它所满足的递推关系；
?n?rk?r?2) 证明fr(n,k)???,n?r?k(r?1)
k??解：可将本题转换为构造相应的0－1串的问题。将这样的n位0－1串与1
到n的正整数对位，与1相应的整数选取，与0相应的不取。一个0－1串对应一个选取方案。这也对应将相同的球放入不同的盒子的方案数。
k10...010...01......10...01
rrr?k?1?n?k?r(k?1)?1??n?r(k?1)?所以fr(n,k)??。 ????n?k?r(k?1)k????11??Fn?116. 试证：??10???F???nnFn?
?Fn?1?证明：可用数学归纳法证明
11?，右边=?11?，成立。 1) 当n=1时，左边= ??????10??10?
11??Fk?12) 假设n=k时，等式成立，则有?????F10???kkFk??. Fk?1?n=k+1时，有
21
?Fk?1Fk??11??Fk?1?Fk?11??????10???F?F??k?1??10??k?Fk?Fk?1由1)、2）可得等式成立。
nk?1Fk??Fk?2???Fk??Fk?1Fk?1?? Fk?n?1?n?k??n?k?17. 设n?0,an???,bn???,用Fibonacci数来表示an和bn. ??2k?1k?0?k?0?2k??解：
?n?k?1?n?1??n?k??n?k??n?n?k??2n?1?n?n?k?1? an?1????????????????????????2k?k?0??2k??2k?1??k?0?2k??2n?2?k?0?2k?1?k?0?n?1
?an?bn?1
同理可得bn?1?an?bn。
由此可得两个序列的生成函数为A(x)?1?xx?3x?12B(x)?11?xx,B(x)?x1?xA(x)。
联立解可得A(x)?,B(x)?x?3x?12。
由Fibonacci数定义可知，f(n)=f(n-1)+f(n-2)，其生成函数为
F(x)?11?x?x?2。
?n令P(x)??f(2n)x,Q(x)??f(2n?1)x，可得
nn?0n?1P(x)?1?xx2?3x?1,Q(x)?xx2?3x?1
所以an＝f(2n), bn＝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=?SiFi,其中Si=(0,1),i=1,2,…m;SiSi+1=0,i=1,2,…,m-1.
i?2m22
可以用数学归纳法进行证明。 1) n=1=f(0)=f(1),成立。
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，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'的路径数。即
1?2n??2n??2n????n??n?1?n?1?n?。 ??????2n?总的路径数为2?。 ??n?1?n?
23