组合数学PDF电子书下载

第1章 排列与组合 1

1.1 加法法则与乘法法则 1

1.1.1 加法法则 1

1.1.2 乘法法则 2

1.2 排列与组合 3

1.2.1 排列 3

1.2.2 组合 4

1.2.3 组合的性质 5

1.3 多重集的排列与组合 6

1.3.1 多重集的排列 7

1.3.2 多重集的组合 7

1.4 习题 9

第2章 生成排列和组合 12

2.1 生成排列 12

2.1.1 字典序法 12

2.1.2 邻位互换生成算法 13

2.1.3 逆序列生成算法 14

2.2 生成组合 16

2.2.1 生成r-组合的字典序算法 16

2.2.2 生成组合的基2算法 17

2.2.3 以反射Gray码的顺序生成0和1的n元组的算法 17

2.3 习题 18

第3章 二项式系数 19

3.1 二项展开式 19

3.1.1 Pascal公式 19

3.1.2 杨辉三角形 19

3.1.3 二项式定理 20

3.1.4 组合恒等式 21

3.1.5 二项式系数的单调性 22

3.2 牛顿二项式定理和多项式定理 22

3.2.1 组合数的推广 22

3.2.2 牛顿二项式定理 23

3.2.3 多项式定理 23

3.3 习题 24

第4章 容斥原理 25

4.1 容斥原理 25

4.1.1 引论 25

4.1.2 容斥原理的两个基本公式 25

4.2 容斥原理的应用 29

4.2.1 具有重复的组合 29

4.2.2 错位排列 31

4.2.3 带有禁止位置的排列 33

4.3 鸽巢原理 36

4.3.1 鸽巢原理的简单形式 36

4.3.2 鸽巢原理的加强形式 37

4.4 Ramsey定理 38

4.4.1 Ramsey问题 38

4.4.2 Ramsey数的性质 39

4.5 习题 40

第5章 递推关系与母函数 42

5.1 递推关系与Fibonacci数列 42

5.1.1 递推关系的概念 42

5.1.2 Fibonacci数列 42

5.1.3 Fibonacci数的性质 43

5.2 常系数线性齐次递推关系 44

5.2.1 基本概念 44

5.2.2 特征根相异条件下递推关系的通解 44

5.2.3 特征根不相异条件下递推关系的通解 46

5.3 常系数线性非齐次递推关系 48

5.3.1 基本概念 48

5.3.2 递推关系的特解 48

5.4 用母函数法求解递推关系 50

5.5 习题 53

第6章 特殊计数序列 54

6.1 Catalan数 54

6.1.1 Catalan数非线形递推关系 54

6.1.2 Catalan数计算公式 55

6.1.3 利用母函数方法推导计算公式 56

6.2 差分序列和Stirling数 58

6.2.1 差分序列 58

6.2.2 Stirling数 62

6.3 分拆数和Ferrer图象 64

6.3.1 分拆数 64

6.3.2 Ferrer图象 65

6.4 习题 66

第7章 图与网络 67

7.1 基本概念 67

7.1.1 图与简单图 67

7.1.2 度 68

7.1.3 图的连通 68

7.2 欧拉图 70

7.2.1 欧拉图 70

7.2.2 欧拉图的判定 70

7.2.3 欧拉图实例 71

7.3 哈米尔顿图 71

7.4 最短路问题 72

7.4.1 狄克斯特拉（Dijkstra）最短路算法 72

7.4.2 狄克斯特拉最短路算法实例 73

7.5 最小树问题 74

7.5.1 树的概念 74

7.5.2 最小树 75

7.6 最大流问题 76

7.6.1 基本概念 77

7.6.2 最大流算法 77

7.7 匹配 80

7.7.1 二分图 80

7.7.2 匹配 80

7.8 习题 82

第8章 Pólya计数法 85

8.1 置换群与对称群 85

8.1.1 群的概念 85

8.1.2 置换群与对称群 86

8.1.3 循环、奇循环与偶循环 86

8.2 Burnside定理 88

8.2.1 共轭类 88

8.2.2 K不动置换类 89

8.2.3 等价类 89

8.2.4 Burnside定理 89

8.3 Pólya计数公式 90

8.3.1 Pólya计数公式 90

8.3.2 Pólya计数公式应用举例 90

8.4 习题 91

第9章 线性规划 92

9.1 线性规划基本概念 92

9.1.1 线性规划问题的提出及其数学模型 92

9.1.2 线性规划问题的图解法 95

9.2 单纯形法 97

9.2.1 线性规划问题的标准型 97

9.2.2 线性规划问题的解 99

9.2.3 单纯形法的基本思路 100

9.3 初始基本可行解的确定与退化情形的处理 104

9.3.1 初始基本可行解的确定 104

9.3.2 退化情形的处理 108

9.4 修正单纯形法 111

9.5 对偶理论 121

9.5.1 对偶问题的提出 121

9.5.2 对偶问题的基本性质 122

9.6 习题 122

第10章 组合最优化 125

10.1 运输问题 125

10.1.1 运输问题的提出 125

10.1.2 运输问题的求解 126

10.2 分派问题 132

10.2.1 分派问题的提出 132

10.2.2 分派问题的求解 133

10.3 背包问题 135

10.3.1 背包问题的提出 135

10.3.2 背包问题的求解 136

10.4 车辆调度问题 138

10.4.1 车辆调度问题的提出 138

10.4.2 车辆调度问题的求解 138

10.5 习题 140

参考文献 142