《组合数学习题解答.ppt》由会员分享，可在线阅读，更多相关《组合数学习题解答.ppt（58页珍藏版）》请在三一办公上搜索。
1、1.题目解：,比较n次方系数即可证。,2.题目解：,分析 的结构可知仅当时有 项,三个系数相加即为所求,3.题目解：,用指数型母函数，可得母函数,系数即为所求。,4.题目解：,A、B、C、D组成的全排列数为,出现A后，其后续字母必为A、B、C、D中的一个，其概率相等。,AB至少出现一次的排列为,排列数为,5.题目解：,对符合题设要求的排列如果0可以出现在最高位，则可得母函数：,但是对n位四进制数来说最高位不能为0。,6.题目解：,参见第四题解答前半部分。,7.题目解：,题设中序列的母函数为：,由$4性质3得，上式,8.题目解：,等式的右端相当于从n+m+1个球中取n+1个球的组合。把这n+m+
2、1个球编号，如果取出的n+1个球中最小编号是一，则得到 如果最小编号是二则得到 如果最小编号是m则得到。可证,9.题目解：,由推导过程知,令,求导得,令,即,解得,将 代入 得,10.题目解：,把单位看成元素，共12个元素其中 第1单位有3个第2单位有4个第3单位有5个则命题可看成从12个元素中取8个的组合。母函数为：,其中 项系数为所求,11.题目解：,用归纳法可证明：1）当k=1时命题成立2）设当k=N时命题成立 即N可唯一表示成不同且不相邻的F数之和。则当k=N+1时，明显可以分成N的序列再加上1（），但这可能会不能满足“不同且不相邻”的条件。下面予以讨论,先讨论相邻的，明显若有，则可用
3、 代替。以此类推可解决相邻问题。再讨论相同，可把超过1个的分解为 再用结决相邻问题的方法即可解决 命题得证,12.题目解：,设n个满足条件的平面把空间分成 个域n-1个满足条件的平面把空间分成 个域则第n个平面与这n-1个平面有n-1条交线，且这些两两相交，任三线不共点。第n个平面被这n-1条线分成 个域 增加了 个域。可得,设,解得,13.题目解：,设符合条件的n位二进制数的个数为这些数中一共有 个0 当n位二进制数最高位为1时,符合条件的n位二进制数的个数为,最高位为0时，次高位必为1符合条件的n位二进制数的个数为,即 是F数列,特征方程为：,设,解得、为重根。,分析上式结构可得：,把n=
4、2代入可解得：,代入,可得方程组,解得,14.题目解：,设n为偶数1）先把n-1个盘通过C移到B2）把第n个盘移到C3）把n-3个盘通过C移到A4）把第n-2个盘移到B对n为奇数时上述四步仍然成立，但是B、C对调。,其中,为Hanota数列。,可得特征方程：,解得,设,代入初值可解得,15.题目解：,设m层中有k层不在原来的层上，m-k层在原有层上，但是每册都不在原来的位置。,16.题目解：,把AD看成1则AB为,同理可得其他矩形相似,满足条件的n条直线把平面分成 个域，其中n-1条直线分割成的域数为，第n条直线与这n条直线均相交。被分成n-1+1=n段。增加的域数为n。,17.题目解：,设,
5、解得,18.题目解：,n-1个点把圆分为 部分，加上第n个点则增加了n-1条弦增加第1条弦，被其他弦分成0段增加第2条弦，被其他弦分成1x(n-2-1)段增加第n-2条弦，被其他弦分成(n-3)(n-2-n+3)段增加第n-1条弦，被其他弦分成0段,19.题目解：,设n-1位不出现11的个数为n-2位不出现11的个数为n位不出现11的个数为则,即特征方程为,设代入得,20.题目解：,设所求为则,21.题目解：,是n的4次方,满足第推关系,设,代入可解得,22.题目解：,由矩阵的结构知,只要求出K即可,24.题目解：,当r是奇数（1）时,当r是偶数时,25.题目解：,I 当n是偶数时 对所有符合
6、条件的 来说，每边增加1各单位，则可构成符合条件的。,设短边为a、b，长边为c，则(a+b)-c=2即a+b-2c-1，对所有符合条件的 来说，每边减少1各单位，则可构成符合条件的。,II 当n为奇数时 由I的讨论知，比 多了a+b-c=1的三角形。而这种三角形可知,当 能被2整除时，这种三角形有 个,当 不能被2整除时，这种三角形有 个,(2),27.题目,1）证明,同理可证,3）解,28.题目1）证明,用数学归纳法I k=2时 成立，即II 设k=m时成立 则k=m+1时，,用归纳假设,由I、II知题设成立。,2）证明,作了k次后,若,则上式,当n是偶数时，最后一次会出现 项,3）证明,当n是奇数时，最后一次会出现 项,4）证明,用2）的结论,下面证明是最大公约数设 不是最大公约数，是则 则 与 矛盾是最大公约数,30.题目证明,设与第n+1号球同盒的球有n-k个，这样，其他k个球就放入另外m-1个盒子，k=m-1,m,n。即从n个不同的球中取k个放入m-1个相同的盒子的方案有,31.题目解：,特征方程为,解得,代入得,32.题目解：,设所求的串的个数为，相邻不同为0的串的个数为,母函数为,的系数即为所求。,33.题目证明：,用数学归纳法I n=2时 成立II 设n=k时成立即,由I、II知题设成立,当n=k+1时,
