【组合数学】组合数学简介 ( 组合数学脉络 | 组合数学技巧 | 组合思想 1 : 一一对应 )

文章目录

• ​​一、组合数学脉络​​
• ​​二、组合数学思想 1 : 一一对应技巧​​
• ​​三、组合计数模型 与 一一对应​​

一、组合数学脉络

组合存在性问题 : 鸽巢原理 , Remsey 定理 ;

组合计数问题 :

计数定理 : 容斥原理 , Polya 定理 ;

计数方法 : 递推方程 , 生成函数 , 指数生成函数 ;

计数模型 : 选取方案 , 不定方程解 , 非降路径问题 , 拆分方案 , 放球方案 ;

组合枚举问题 : 生成算法 , 组合设计 ;

组合优化问题 : 最短路径问题 , 最小生成树 , 网络优化 ;

三个重要的组合思想 :

• 一一对应
• 数学归纳法
• 上下界逼近处理方法

二、组合数学思想 1 : 一一对应技巧

一一对应技巧 : 将某种计数 转为 另外一种计数 , 另外一种计数有一个非常显然的结果 , 两种计数的个数是一样多的 ;

示例

1

1

1 :

3

×

3

×

3

3 \times 3 \times 3

3×3×3 的立方体 , 需要切割多少次 , 才能切成

27

27

27 个小的立方体 ;

最中心的小立方体 ,

6

6

6 个面都是切出来的 , 必须切

6

6

6 刀 , 才能得到

6

6

6 个面 ;

最中心的小立方体的面数 , 与 切割的刀数 是 一一对应 的 ;

示例

2

2

2 :

n

n

n 个运动员比赛 , 淘汰赛制 , 需要多少次比赛 ;

n

−

1

n-1

n−1 次 , 比赛次数 与 淘汰人数 一一对应 ;

三、组合计数模型 与 一一对应

计数方法 : 计数模型 与 实际问题 进行对应 ;

计数模型 :

• 选取问题
• 不定方程非负整数解问题
• 非降路径问题
• 整数拆分问题
• 放球问题

上述模型都是非常典型的组合计数模型 , 很多实际问题都可以与上述某个模型建立一一对应关系 , 这样就可以使用上述模型的公式和方法 , 来解实际的问题 ;

参考之前学习的 Stirling 子集数 , 【集合论】Stirling 子集数 ( 斯特林子集数概念 | 放球模型 | Stirling 子集数递推公式 | 划分的二元关系 加细关系 ) 二、放球模型 ,

集合的 划分问题 , Stirling 子集数问题 ,

与 放球模型 中的 球有编号 , 盒子没有编号 ( 不同的球放在相同盒子里 ) 模型的方案个数