《组合数学》

第一章 排列、组合与二项式定理1

1.1 加法规则和乘法规则1

1.2 排列3

1.3 组合6

1.4 二项式定理11

1.5 组合恒等式14

习题一19

第二章 鸽笼原理与Ramsey定理21

2.1 鸽笼原理的简单形式21

2.2 鸽笼原理的一般形式22

2.3 Ramsey定理24

习题二30

第三章 容斥原理31

3.1 容斥原理31

3.2 重集的r-组合36

3.3 错排问题37

3.4 相对位置上有限制的排列问题39

习题三42

4.1 母函数的基本概念44

第四章 母函数44

4.2 母函数的基本运算47

4.3 母函数在排列、组合中的应用50

4.4 整数的拆分与Ferrers图55

4.5 母函数在组合恒等式中的应用62

习题四65

第五章 递归关系68

5.1 递归关系的建立68

5.2 常系数线性齐次递归关系71

5.3 常系数线性非齐次递归关系77

5.4 迭代法与归纳法81

5.5 母函数法(母函数在递归关系中的应用)84

5.6 Stirling数88

习题五92

第六章 网络流95

6.1 运输网络与最大流95

6.2 割96

6.3 最大流最小割定理97

6.4 标号法99

6.5 最大流最小割定理的推广103

6.6 可行流105

6.7 初始可行流的构造107

6.8 最短通路110

6.9 最小费用流112

习题六115

第七章 线性规划118

7.1 线性规划问题的数学模型118

7.2 线性规划问题的几何意义122

7.3 凸多边形与凸多面体124

7.4 线性规划问题的标准形式126

7.5 线性规划问题的基本定理127

7.6 单纯形方法129

7.7 表格法134

7.8 初始基本可行解的求法139

7.9 单线形法中的特例141

7.10 线性规划问题的对偶问题144

习题七149

8.1 问题的提出及其思想151

第八章 动态规划151

8.2 最优原理与递归函数方程152

8.3 资源分配问题155

8.4 可靠性设计问题157

8.5 背包问题160

8.6 用动态规划解数学问题163

习题八165

第九章 组合设计168

9.1 问题的提出168

9.2 有限射影平面与仿射平面169

9.3 完全区组设计与拉丁方172

9.4 正交拉丁方175

9.5 平衡不完全区组设计179

9.6 三连组系182

9.7 对称区组设计185

9.8 区组设计的一种构造方法187

9.9 Hadamard矩阵189

习题九193