《组合数学导论》

第一章 排列和组合1

1-1 引1

1-2 和则、积则1

1-3 排列2

1-4 组合5

1-5 不同诸物的分配7

1-6 相同诸物的分配9

1-7 Stirling公式10

1-8 小结和参考文献13

习题13

第二章 母函数18

2-1 引18

2-2 组合的母函数19

2-3 排列的计数母函数23

2-4 不同的诸物分配人不可辨的诸盒26

2-5 整数的分拆28

2-6 Ferrers图31

2-7 初等关系32

2-8 小结和参考文献35

习题36

第三章 递归关系41

3-1 引41

3-2 常系数线性递归关系42

3-3 用母函数方法求解47

3-4 一类特殊的非线性差分方程51

3-5 带双指标的递归关系56

3-6 小结和参考文献60

附录3-1 差分方程的解的唯一性61

4-2 容斥原理69

第四章 容斥原理69

4-1 引69

4-3 一般公式73

4-4 更列75

4-5 在相对位置上有限制的排列78

4-6 棋阵多项式79

4-7 禁位排列81

4-8 小结和参考文献84

习题85

第五章 Polya计数定理91

5-1 引91

5-2 集、关系和群92

5-3 在一个置换群下的等价类95

5-4 函数的等价类101

5-5 函数的权和存储103

5-6 Polya基本定理105

5-7 Polya定理的推广110

5-8 小结和参考文献115

习题116

第六章 图论的基本概念121

6-1 引121

6-2 图的连通性124

6-3 Euler路125

6-4 Hamilton路128

6-5 小结和参考文献130

习题131

第七章 树、回路和割集133

7-1 树和支撑树133

7-2 割集134

7-3 线性向量空间136

7-4 同图相结合的线性空间138

7-5 子空间向基底140

7-6 矩阵表示141

附录7-1 向量空间的基底中向量的个数144

习题145

第八章 可平面图和对偶图148

8-1 引148

8-2 Euler公式149

8-3 Kuratowski定理151

8-4 对偶图159

8-5 小结和参考文献163

习题165

第九章 控制关系、独立关系和色数167

9-1 控制集167

9-2 独立集169

9-3 色数172

9-4 色多项式176

9-5 四色问题177

9-6 小结和参考文献182

习题183

第十章 运输网络184

10-1 引184

10-2 割185

10-3 最大流量小割定理186

10-4 推广189

10-5 小结和参考文献195

习题195

第十一章 匹配理论199

11-1 引199

11-2 完全匹配200

11-3 最大匹配203

11-4 另一方法207

11-5 小结和参考文献209

习题210

第十二章 线性规划212

12-1 引212

12-2 最优可行解214

12-3 松驰变量218

12-4 单纯形法223

12-5 表格法226

12-6 错综复杂的情形及其解决办法229

12-7 对偶性234

12-8 小结和参考文献239

习题240

13-1 引244

第十三章 动态规划244

13-2 最优性原理246

13-3 函数方程249

13-4 小结和参考文献252

习题253

第十四章 区组设计255

14-1 引255

14-2 完全区组设计257

14-3 正交拉丁方258

14-4 平衡不完全区组设计262

14-5 区组设计的构造265

14-6 小结和参考文献271

习题272

索引(英汉对照)273