《组合数学》求取 ⇩

第一章基本计数原理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