北京大学：《离散数学》离散数学之二《代数结构与组合数学》组合数学 Combinatorial Mathmatics

组合数学 Combinatorial Mathmatics 组合存在定理基本计数公式 递推方程生成函数 容斥原理Bo小ya定理

组合数学 Combinatorial Mathmatics 组合存在定理 基本计数公式 递推方程 生成函数 容斥原理 Bolya定理

组合数学的主要内容 研究离散个体满足约束条件下的配置问题 ■组合存在性 偏序集分解定理 Ramsey定理 相异代表系存在定理 组合计数 基本计数公式 计数方法 计数定理 ■组合枚举:生成算法、组合设计 组合优化:最短路经、最小生成树、网络流

组合数学的主要内容 研究离散个体满足约束条件下的配置问题 „ 组合存在性 „ 偏序集分解定理 „ Ramsey定理 „ 相异代表系存在定理 „ 组合计数 „ 基本计数公式 „ 计数方法 „ 计数定理 „ 组合枚举：生成算法、组合设计 „ 组合优化：最短路经、最小生成树、网络流

组合数学的主要技巧 重要的组合思想 对应 数学归纳法 上下界逼近的处理方法

组合数学的主要技巧 重要的组合思想 „ 一一对应 „ 数学归纳法 „ 上下界逼近的处理方法

对应 例13×3×3的立方体至少需要多少次才能切成 27个小立方体? 解:6次 切割中心立方体的面 次数=面数 例2n个选手比赛决出冠军,需要多少次比赛? 解:n-1次 比赛分淘汰,比赛次数=淘汰人数

一一对应 例1 3×3 × 3 的立方体至少需要多少次才能切成 27个小立方体？ 解： 6次 切割 ↔ 中心立方体的面 次数=面数 例2 n个选手比赛决出冠军，需要多少次比赛？ 解： n -1次 比赛 ↔ 淘汰，比赛次数=淘汰人数

组合计数模型与一一对应 计数方法:计数模型与实际问题的对应 ■计数模型: 选取问题 不定方程非负整数解问题 非降路径问题 整数拆分问题 放球问题等等

组合计数模型与一一对应 „ 计数方法：计数模型与实际问题的对应 „ 计数模型： „ 选取问题 „ 不定方程非负整数解问题 „ 非降路径问题 „ 整数拆分问题 „ 放球问题等等