组合数学习题解答

9.利用

改善 §4(2) 的pn估计式。 解：...

由推导过程知

，

令

求导得

令 即

解得

将x1代入y得

10. 8台计算机分给3个单位，第1单位的分配量不超过3台，第2单位的分配量不超过4台，第3个单位不超过5台，问共有几种分配方案？ 解：...

把单位看成元素，共12个元素 其中 第1单位有3个 第2单位有4个 第3单位有5个

则命题可看成从12个元素中取8个的组合。母函数为：

其中x8项系数为所求

11. 证明正整数n都可以唯一地表示成不同的且不相邻的Fibonacci数之和。即

注意F1=F2=1是相同的Fibonacci数。 证明：...

先证明可表示性

对n用归纳法. 1）当n=1时命题成立

2）设对小于n的正整数命题成立 对于n，存在k，满足设

则

可表示为不相同且不相邻的F数列的和。即

若

则Fk与Fk-1可合并为Fk+1 命题得证。

，

12. 设空间的n个平面两两相交，每3个平面有且仅有一个公共点，任意4个平面都不共点。这样的n个平面把空间分割成多少个不重叠的域？ 解：...

设n个满足条件的平面把空间分成an个域n-1个满足条件的平面把空间分成an-1个域 则第n个平面与这n-1个平面有n-1条交线，且这些两两相交，任三线不共点。

第n个平面被这n-1条线分成个域。可得 设

个域 增加了

解得

13. 相邻位不同为0的n位2进制数中一共出现了多少个0？ 解：...

设符合条件的n位二进制数的个数为hn 这些数中一共有an个0

当n位二进制数最高位为1时,符合条件的n位二进制数的个数为hn-1 最高位为0时，次高位必为1符合条件的n位二进制数的个数为hn-2 即hn是F数列