《组合学导引》求取 ⇩

前言1

第一章 什么是组合学？1

1.1例 棋盘的完全覆盖3

1.2例 切割立方体5

1.3例 幻方6

1.4例 四色问题8

1.5例 36军官问题9

1.6例 最短路问题11

练习13

2.1 鸽笼原理的简单形式16

第二章 鸽笼原理16

2.2 鸽笼原理的加强形式18

2.3 Ramsey定理22

练习25

第三章 基本计数原理：排列与组合28

3.2 集合的排列31

3.3 集合的组合35

3.4 重集的排列38

3.5 重集的组合40

3.6 排列的生成43

3.7 排列的逆序47

3.8 r组合的生成50

练习52

第四章 二项式系数57

4.1 Pascsal公式57

4.2 二项式定理60

4.3 恒等式63

4.4 二项式系数的单峰性质69

4.5 多项式定理71

4.6 Newton二项式定理73

练习76

第五章 容斥原理79

5.1 容斥原理80

5.2 重复组合85

5.3 错位88

5.4 其它禁位问题93

练习96

第六章 递归关系99

6.1 Fibonacci序列100

6.2 常系数线性齐次递归关系：不同根的情形106

6.3 常系数线性齐次递归关系：重根的情形112

6.4 迭代与归纳116

6.5 差分表123

练习135

第七章 生成函数140

7.1 生成函数140

7.2 线性递归关系144

7.3 一个几何学的例子153

7.4 指数型生成函数158

练习163

第八章 相异代表组168

8.1 相异代表组168

8.2 多米诺骨牌、棋盘与偶图176

8.3 一种算法182

8.4 无限多个集合的情形192

练习195

第九章 组合设计200

9.1 有限域200

9.2 有限几何213

9.3 拉丁方222

9.4 Kirkman女学生问题232

练习240

第十章 图论入门245

10.1 图的基本性质245

10.2 Euler链与Euler圈250

10.3 Hamilton链与Hamilton圈255

10.4 树259

10.5 两个实际问题268

10.6 Shannon开关对策272

10.7 有向图280

练习284

第十一章 色数、连通度及图的其它参数291

11.1 色数291

11.2 平面图的Euler公式300

11.3 五色定理304

11.4 连通度309

11.5 图的其它参数317

练习323

第十二章 优化问题329

12.1 稳定分配330

12.2 核心分配335

12.3 Hitchcock运输问题339

12.4 最优分配问题357

12.5 瓶颈问题362

练习371

文献目录379

选题解答380