组合数学课件 第二章母函数与递推关系习题解答.ppt

2020 1 27 组合数学 1 题目解 比较n次方系数即可证 2020 1 27 组合数学 2 题目解 分析的结构可知仅当时有项 三个系数相加即为所求 2020 1 27 组合数学 3 题目解 用指数型母函数 可得母函数 系数即为所求 2020 1 27 组合数学 4 题目解 A B C D组成的全排列数为 出现A后 其后续字母必为A B C D中的一个 其概率相等 2020 1 27 组合数学 AB至少出现一次的排列为 排列数为 2020 1 27 组合数学 5 题目解 对符合题设要求的排列如果0可以出现在最高位 则可得母函数 2020 1 27 组合数学 但是对n位四进制数来说最高位不能为0 2020 1 27 组合数学 6 题目解 参见第四题解答前半部分 2020 1 27 组合数学 7 题目解 题设中序列的母函数为 由 4性质3得 上式 2020 1 27 组合数学 8 题目解 等式的右端相当于从n m 1个球中取n 1个球的组合 把这n m 1个球编号 如果取出的n 1个球中最小编号是一 则得到如果最小编号是二则得到如果最小编号是m则得到 可证 2020 1 27 组合数学 9 题目解 由推导过程知 2020 1 27 组合数学 令 2020 1 27 组合数学 求导得 令 即 解得 2020 1 27 组合数学 将代入得 2020 1 27 组合数学 10 题目解 把单位看成元素 共12个元素其中第1单位有3个第2单位有4个第3单位有5个则命题可看成从12个元素中取8个的组合 母函数为 2020 1 27 组合数学 其中项系数为所求 2020 1 27 组合数学 11 题目解 用归纳法可证明 1 当k 1时命题成立2 设当k N时命题成立即N可唯一表示成不同且不相邻的F数之和 则当k N 1时 明显可以分成N的序列再加上1 但这可能会不能满足 不同且不相邻 的条件 下面予以讨论 2020 1 27 组合数学 先讨论相邻的 明显若有 则可用代替 以此类推可解决相邻问题 再讨论相同 可把超过1个的分解为再用结决相邻问题的方法即可解决命题得证 2020 1 27 组合数学 12 题目解 设n个满足条件的平面把空间分成个域n 1个满足条件的平面把空间分成个域则第n个平面与这n 1个平面有n 1条交线 且这些两两相交 任三线不共点 第n个平面被这n 1条线分成个域增加了个域 可得 2020 1 27 组合数学 设 解得 2020 1 27 组合数学 13 题目解 当n位二进制数最高位为1时 最高位为0时 次高位必为1 即是F数列 2020 1 27 组合数学 14 题目解 设n为偶数1 先把n 1个盘通过C移到B2 把第n个盘移到C3 把n 3个盘通过C移到A4 把第n 2个盘移到B对n为奇数时上述四步仍然成立 但是B C对调 其中 为Hanota数列 2020 1 27 组合数学 15 题目解 这是一个错排问题把某种排列状态看成暂时状态则 2020 1 27 组合数学 16 题目解 把AD看成1则AB为 2020 1 27 组合数学 同理可得其他矩形相似 2020 1 27 组合数学 满足条件的n条直线把平面分成个域 其中n 1条直线分割成的域数为 第n条直线与这n条直线均相交 被分成n 1 1 n段 增加的域数为n 17 题目解 2020 1 27 组合数学 设 解得 2020 1 27 组合数学 18 题目解 n 1个点把圆分为部分 加上第n个点则增加了n 1条弦增加第1条弦 被其他弦分成0段增加第2条弦 被其他弦分成1x n 2 1 段 增加第n 2条弦 被其他弦分成 n 3 n 2 n 3 段增加第n 1条弦 被其他弦分成0段 2020 1 27 组合数学 19 题目解 设n 1位不出现11的个数为n 2位不出现11的个数为n位不出现11的个数为则 即特征方程为 2020 1 27 组合数学 设代入得 2020 1 27 组合数学 20 题目解 设所求为则 2020 1 27 组合数学 21 题目解 是n的4次方 满足第推关系 设 2020 1 27 组合数学 代入可解得 2020 1 27 组合数学 22 题目解 由矩阵的结构知 只要求出K即可 2020 1 27 组合数学 24 题目解 当r是奇数 1 时 当r是偶数时 2020 1 27 组合数学 25 题目解 I当n是偶数时对所有符合条件的来说 每边增加1各单位 则可构成符合条件的 设短边为a b 长边为c 则 a b c 2即a b 2 c 1 对所有符合条件的来说 每边减少1各单位 则可构成符合条件的 20