组合数学习题3(共5章)

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元钱,他每天买一次物品,每次买物品的品种很单调,或者买一

元的甲物品,或者买二元钱的乙物品,或者买二元

>>灞曞紑鍏ㄦ枃<<
12@gma联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4