李凡长版-组合数学课后习题答案-习题3 下载本文

于是f(n)?(n3?3n2?n)?2n.

61?f(n)?nf(n?1)?n! (n?1)(5)?;

?f(0)?2解: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).

?f(n)?(n?2)f(n?1) (n?1)(6)?;

f(0)?1?解: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)=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个椭圆将平面分割成的部分的个数,则有:一个椭圆将平面

分成内、外两个部分,两个椭圆将平面分成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=d1d2…dn-1表示n-1

位十进制数,则若d含有偶数个5,则dn取5以外的任何一个数;若d含有奇数个5,则dn取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. 13. 在一个平面上画一个圆,然后一条一条地画n条与圆相交的直线.当r是

20

大于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。

11?x?x2由Fibonacci数定义可知,f(n)=f(n-1)+f(n-2),其生成函数为F(x)???。

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?2m可以用数学归纳法进行证明。

22

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