组合数学 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) 归纳 多重归纳 归纳基础 为真, 为真 归纳步骤 假设 ,为真,证 为真
上下界逼近 确定某个值(或阶) 步骤 证明这个值的上界 证明这个值的下界 如果上界与下界相等,则结束 否则改进上界或者下界,使得它们逐渐逼近
上下界逼近 确定某个值(或阶) 步骤 证明这个值的上界 证明这个值的下界 如果上界与下界相等,则结束 否则改进上界或者下界,使得它们逐渐逼近