北京大学：《离散数学》离散数学之二《代数结构与组合数学》组合数学 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次 比赛 ↔ 淘汰，比赛次数=淘汰人数

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

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

数学归纳法 描述一个与自然数相关的命题P(n),P,m)等 证明 归纳基础:例如P()真 归纳步骤:例如P(n)→P(n+1) 第一数学归纳法: n=0为真 假设对n为真,证对n+1为真 第二数学归纳法: n=0为真 假设对一切小于n的k为真,证明对n为真

数学归纳法 描述一个与自然数相关的命题 P(n)，P(n,m)等 证明 归纳基础：例如 P(0) 真 归纳步骤：例如 P(n) ⇒ P(n+1) 第一数学归纳法： n=0为真 假设对n为真，证对n+1为真 第二数学归纳法： n=0为真 假设对一切小于n 的 k 为真, 证明对 n 为真

数学归纳法的推广 证明命题Pmn) 针对m,n两个自然数 任意给定m(或n)对n(或m)归纳 多重归纳 归纳基础为真,为真 归纳步骤 假设,为真,证为真

数学归纳法的推广 证明命题 P (m, n ) 针对 m, n 两个自然数 任意给定 m（或 n）对n ( 或 m) 归纳 多重归纳 归纳基础 为真， 为真 归纳步骤 假设 ,为真，证 为真

上下界逼近 确定某个值(或阶) 步骤 证明这个值的上界 证明这个值的下界 如果上界与下界相等,则结束 否则改进上界或者下界,使得它们逐渐逼近

上下界逼近 确定某个值（或阶） 步骤 证明这个值的上界 证明这个值的下界 如果上界与下界相等，则结束 否则改进上界或者下界，使得它们逐渐逼近

实例 用红、蓝两色任意对Kn的边涂色,n至少是多少才能 出现一个红色的三角形,或者出现一个蓝色的三角形? 证明 (1)上界m≤6.,n=6,某顶点至少3条同色边(比如红色) (2)下界n>5.反例,n=5不可能做到 (3)n=6

用红、蓝两色任意对 Kn的边涂色，n 至少是多少才能 出现一个红色的三角形，或者出现一个蓝色的三角形？ 证明 （1）上界 n≤6. n=6，某顶点至少 3 条同色边（比如红色） （2）下界 n>5. 反例，n=5 不可能做到. （3）n=6. 实例

第二十章组合存在性定理 偏序集的分解定理 如最长链长度为n,则偏序集可分成n条反链 注意:n是反链个数的下界 如最大反链长度为n,则偏序集可以分解为长 度为n的链 Ramsey定理 鸽巢原理的推广 相异代表系存在定理 Ha定理(完备匹配存在条件)的推广

第二十章 组合存在性定理 偏序集的分解定理 如最长链长度为 n, 则偏序集可分成 n 条反链 注意：n 是反链个数的下界 如最大反链长度为 n，则偏序集可以分解为长 度为n 的链 Ramsey定理 鸽巢原理的推广 相异代表系存在定理 Hall定理（完备匹配存在条件）的推广