组合数学习题解答

特征方程为：

解得a、b为2重根。 设

分析上式结构可得：

把n=2代入可解得： 代入an 可得方程组

解得

14. 在Hanoi塔问题中，在柱A上从上到下套着n个圆盘，其编号依次从1到n。现要将奇数编号与偶数编号的圆盘分别转移到柱B和柱C上。转移规则仍然是每次移动一个，始终保持上面的比下面的小。一共要移动多少次？ 解：...

设n为偶数

1）先把n-1个盘通过C移到B 2）把第n个盘移到C 3）把n-3个盘通过C移到A 4）把第n-2个盘移到B

对n为奇数时上述四步仍然成立，但是B、C对调。

其中k(1)=1,k(2)=2,k(3)=5 h(k)为Hanota数列。

可得特征方程： 解得 代入初值可解得

15. 一书框中有m格，每格各放n册同类的书，不同格放的书类型不同。现取出整理后重新放回，但不打乱相同类。试问无一本放在原来位置的方案数应多少？ 解：...

设m层中有k层不在原来的层上，m-k层在原有层上，但是每册都不在原来的位置。

16. 设一矩形ABCD,其中

作C1B1使得AB1C1D是一正方形。试证矩形B1C1CD和ABCD相似。试证继续这过程可得一和原矩形相似的矩形序列。 解：...

把AD看成1

则AB为

同理可得其他矩形相似

17. 平面上有两两相交，无三线共点的n条直线，试求这n条直线把平面分成多少个域？ 解：...

满足条件的n条直线把平面分成an个域，其中n-1条直线分割成的域数为an-1，第n条直线与这n条直线均相交。 被分成n-1+1=n段。

增加的域数为n。 设

解得

18. 在一圆周上取n个点，过一对顶点可作一弦，不存在三弦共点的现象，求弦把圆分割成几部分？ 解：...

n-1个点把圆分为an-1部分，加上第n个点则对于前n-1个点来说，每选取3个点都有3条弦构成一个三角形，而中间的一点和第n点的连线把中间点与第n点间的弦分为两个部分，增加了一个域。而对第n点与其他n-1点的连线有把第1、n-1、n点构成的三角形分为n个域。

所以地推关系为：

可设