组合数学复习总结.ppt

组合数学复习总结 内容 课程知识结构各章知识点 知识结构 什么是组合数学 鸽巢原理 排列与组合 生成排列和组合 二项式系数 容斥原理及应用 递推关系和生成函数 构造算法 排列存在性 二分图的匹配 各章要求和重点 第1章什么是组合数学 组合数学的研究内容组合数学是研究离散结构的存在 计数 分析和优化等问题的学科 一些重要例子棋盘覆盖问题 第2章鸽巢原理及应用 鸽巢原理简单形式及加强形式若将q1 q2 qn n 1个物体被放进n个盒子内 那么 或者第一个盒子至少含有个q1物体 或者第二个盒子至少含有个q2物体 或者第n个盒子至少含有个qn物体Ramsey定理至少掌握Ramsey定理的简单形式及应用 第2章鸽巢原理及应用 续 用于证明某种排列的存在性 不用于构造排列和计数 运用鸽巢原理通常需要将问题转化 第3章排列与组合 主要内容两个基本计数原理 加法原理 乘法原理集合排列和组合多重集的排列 重点掌握 多重集的组合 重点掌握 3 2集合的排列 难点循环排列 把元素排成首尾相连的一个圈 只考虑元素间的相对顺序的排列 n个元素集合的循环r排列个数为 特别地 n元素的循环排列个数 n 1 3 4多重集的排列 无限重元素的排列计数 令S是多重集 它有k个不同的元素 每个元素都有无限重复次数 那么 S的r 排列个数为kr 多重集的 全 排列计数 令S是多重集 它有k个不同的元素 每个元素的重复数分别为n1 n2 nk 那么 S的排列数等于 3 5多重集组合 无限重数多重集组合 令S是多重集 它有k个不同的元素 每个元素都有无限重复次数 那么 S的r 组合个数为S的r 组合个数等于方程x1 x2 xk r的非负整数解的个数 3 5多重集组合 续 多重集S n1 a1 n2 a2 nk ak n n1 n2 nk 求S的r 组合数 其中0 r n 容斥原理方法生成函数方法 第4章 生成排列和组合 主要算法相关问题排列生成算法递归方法邻位替换逆序生成算法 第4章 生成排列和组合 续 生成组合算法 字典序 组合压缩序 反射Gray序生成r 组合算法字典序r 组合生成算法 第5章二项式系数 PASCAL公式 牛顿二项式 第6章容斥原理及应用 主要内容容斥原理 集合交 并的计数容斥原理的应用 1 多重集组合计数 2 特殊问题排列计数 错位排列 禁位排列等 6 1容斥原理 集合S不具有性质P1 P2 Pm的物体的个数 S Ai Ai Aj Ai Aj Ak 1 m A1 A2 Am 容斥原理在多重集组合计数应用 求多重集的r 组合数的一般方法利用容斥原理归为求无限重数元素的多重集计数问题 将计数问题转化为较为简单的集合的交 或者并 应用容斥原理求出这些集合的交 或并 容斥原理应用于排列计数 错位排列计数 Dn n Dn满足如下递推关系 1 Dn n 1 Dn 2 Dn 1 n 3 4 2 Dn nDn 1 1 n n 2 3 容斥原理应用于排列计数 禁位排列应用绝对禁止位置排列相对禁止位置排列 第7章递推关系和生成函数 主要内容 重点递推关系求解 递推关系 特殊问题递推关系线性齐次递推关系求解 特征多项式方法非齐次递推关系求解 生成函数 生成函数利用生成函数求解递推关系特殊序列的生成函数利用生成函数计数 如多重集组合和排列 常系数线性齐次递推关系求解 常系数线性齐次递推关系 hn a1hn 1 a2hn 2 akhn k ak 0 n k 1 方法1 求特征方程xk a1xk 1 a2xk 2 ak 0的特征根 分互异根及重根两种情形 2 方法2 求生成函数形如p x q x 生成函数的展开式 通常化为代数分式和形式 c 1 rx t 利用牛顿二项式展开 非齐次线性递推关系求解 非齐次线性递推关系 hn a1hn 1 a2hn 2 akhn k bn方法 求齐次关系的一般解求非齐次关系的一个特解将一般解和特解结合 通过初始条件确定一般解中出现的常系数值 第九章 知识要点 二分图的问题模型 车 二分图 多米若二分图等二分图 匹配 覆盖及M 交错路径等概念求最大匹配的M 交错路径搜索算法互异代表系统 成婚条件运用延迟认可算法解决稳定的完备婚姻问题 匹配 覆盖及交错路径的关系 1 是最大匹配 不存在M 交错路径 M 交错路径可以构造边数多于M的匹配 2 M S M是匹配 S是覆盖 G c G 两个重要算法 M 交错路径搜索算法 判定并构造最大匹配 延迟认可算法 构造稳定完备婚姻配对 例题选讲及解答要求 1 构造 1 2 8 的排列 使其逆序列是2 5 5 0 2 1 1 0 10分 解答 解法1 根据逆序列2 5 5 0 2 1 1 0 执行逆序构造排列算法I得到 8 87 876 8675 86574 486573 4865732 48657231 48165723 缺构造过程 扣5分 因此 对应该逆序的排列为48165723 解答 解法2 根据逆序列2 5 5 0 2 1 1 0 执行逆序构造排列算法II得到 缺构造过程 扣5分