组合数学PDF电子书下载

第一章 基本计数原理 1

1.1乘法原理与加法原理 1

1.2排列和组合 1

1.3重复排列和重复组合 4

1.4组合恒等式与二项式系数 6

习题 7

第二章 母函数 9

2.1引例 9

2.2母函数与形式幂级数 10

2.3指数型母函数 16

2.4应用举例 18

习题 27

第三章 递归关系 29

3.1递归模型 29

3.2递归关系的基本解法 35

3.3Stirling数 50

3.4杂例 52

习题 54

第四章 容斥原理及其应用 57

4.1引例 57

4.2容斥原理 58

4.3Jordan（约当）公式 60

4.4容斥原理的应用 65

习题 77

第五章 Pólya计数定理 79

5.1引例 79

5.2置换群与等价类 80

5.3Burnside引理 91

5.4Pólya计数定理 96

5.5Pólya定理推广形式 101

习题 104

第六章 鸽舍原理和Ramsey理论 106

6.1鸽舍原理 106

6.2Ramsey数 111

6.3Ramsey定理 117

6.4Ramsey理论的应用 122

习题 124

第七章 组合算法 126

7.1算法、问题、复杂性 126

7.2图，树 127

7.3深度优先搜索和广度优先搜索 130

7.4回溯法 137

7.5分枝界限法 140

7.6α-β剪枝 144

7.7分治算法 147

7.8动态规划 148

7.9探试算法 152

7.10NP完全问题与近似算法 160

习题 170

8.1图的计算机表示 173

第八章 图的算法 173

8.2强连通分支 174

8.3最短路算法 175

8.4所有点对之间的最短路 177

8.5最小生成树算法 178

8.6可平面性的判定算法 180

8.7传递闭包算法 190

8.8四个俄国人算法 193

习题 195

第九章 图的网络算法 198

9.1最大流最小割定理 198

9.2寻求最大流的标号方法 200

9.3最小费用最大流 203

9.4Menger定理 205

9.5求二分图的最大对集算法和HALL定理 207

9.6附录：Dinic算法 211

习题 214

参考文献 218