文章目录
一、组合数学脉络
二、组合数学思想 1 : 一一对应技巧
三、组合计数模型 与 一一对应
一、组合数学脉络
组合存在性问题 : 鸽巢原理 , Remsey 定理 ;
组合计数问题 :
计数定理 : 容斥原理 , Polya 定理 ;
计数方法 : 递推方程 , 生成函数 , 指数生成函数 ;
计数模型 : 选取方案 , 不定方程解 , 非降路径问题 , 拆分方案 , 放球方案 ;
组合枚举问题 : 生成算法 , 组合设计 ;
组合优化问题 : 最短路径问题 , 最小生成树 , 网络优化 ;
三个重要的组合思想 :
一一对应
数学归纳法
上下界逼近处理方法
二、组合数学思想 1 : 一一对应技巧
一一对应技巧 : 将某种计数 转为 另外一种计数 , 另外一种计数有一个非常显然的结果 , 两种计数的个数是一样多的 ;
示例 1 11 :
3 × 3 × 3 3 \times 3 \times 33×3×3 的立方体 , 需要切割多少次 , 才能切成 27 2727 个小的立方体 ;
最中心的小立方体 , 6 66 个面都是切出来的 , 必须切 6 66 刀 , 才能得到 6 66 个面 ;
最中心的小立方体的面数 , 与 切割的刀数 是 一一对应 的 ;
示例 2 22 :
n nn 个运动员比赛 , 淘汰赛制 , 需要多少次比赛 ;
n − 1 n-1n−1 次 , 比赛次数 与 淘汰人数 一一对应 ;
三、组合计数模型 与 一一对应
计数方法 : 计数模型 与 实际问题 进行对应 ;
计数模型 :
选取问题
不定方程非负整数解问题
非降路径问题
整数拆分问题
放球问题
上述模型都是非常典型的组合计数模型 , 很多实际问题都可以与上述某个模型建立一一对应关系 , 这样就可以使用上述模型的公式和方法 , 来解实际的问题 ;
参考之前学习的 Stirling 子集数 , 【集合论】Stirling 子集数 ( 斯特林子集数概念 | 放球模型 | Stirling 子集数递推公式 | 划分的二元关系 加细关系 ) 二、放球模型 ,
集合的 划分问题 , Stirling 子集数问题 ,
与 放球模型 中的 球有编号 , 盒子没有编号 ( 不同的球放在相同盒子里 ) 模型的方案个数一一对应 ;
