《组合数学及其在计算机科学中的应用》求取 ⇩

目 录1

序言1

第一章引言1

第二章排列和组合的一般计算方法3

2.1两个基本计数法则3

2.2简单的排列和组合5

2.3允许重复的排列和组合8

2.4分配问题10

2.5二项系数12

练习18

第三章母函数21

3.1一些母函数型式21

3.2计算母函数的系数23

3.3整数的拆分27

3.4指数型母函数30

3.5一种求和方法33

练习35

第四章递归关系38

4.1一些递归关系型式38

4.2分治法的递归关系43

4.3用母函数求递归关系的解45

4.4线性递归关系的解50

4.5非齐次递归关系的解52

练习54

第五章鸽舍原理和容斥原理57

5.1鸽舍原理的简单形式57

5.2鸽舍原理的强形式58

5.3 Ramsey定理60

5.4容斥原理65

5.5容斥原理的一般公式68

5.6限制位置的问题和城形棋子多项式72

练习78

第六章置换群，Polya定理80

6.1 引言80

6.2轮换81

6.3置换的奇偶性85

6.4 Burnside引理89

6.5 Polya定理（特殊情形）96

6.6 Polya定理（一般情形）100

练习106

第七章图论初步108

7.1图的一些模型108

7.2同构及一个简单的计数公式112

7.3平面图116

练习122

第八章覆盖回路和图着色125

8.1 欧拉回路125

8.2哈密尔顿回路127

8.3图着色131

8.4着色定理134

练习135

第九章树和查找137

9.1树的性质137

9.2用树来枚举141

9.3流动售货员问题144

9.4分类算法的树分析148

练习151

第十章网络算法153

10.1最短路径153

10.2最小生成树154

10.3网络流量156

练习164

参考文献166