《组合数学》

第一章引言1

习题一3

第二章鸽巢原理和Ramsey定理5

1 鸽巢原理的简单形式及其应用5

2 鸽巢原理的加强形式7

3 Ramsey定理9

习题二15

第三章排列和组合17

1 加法法则和乘法法则17

2 集合的排列和组合18

3 多重集的排列和组合23

习题三28

第四章二项式系数33

1 二项式定理33

2 组合恒等式36

3 非降路径问题43

4 牛顿二项式定理48

5 多项式定理51

习题四54

第五章包含排斥原理58

1 包含排斥原理58

2 多重集的γ-组合数63

3 错位排列65

4 有限制条件的排列问题69

5 有禁区的排列问题73

习题五80

第六章递推关系82

1 Fibonacci数列82

2 常系数线性齐次递推关系的求解86

3 常系数线性非齐次递推关系的求解94

4 用迭代和归纳法求解递推关系98

习题六102

1 生成函数的定义及性质105

第七章生成函数105

2 多重集的γ-组合数112

3 用生成函数来求解递推关系115

4 正整数的剖分117

5 指数生成函数与多重集的排列问题125

6 Catalan数和Stirling数131

习题七144

第八章Polya定理147

1 置换群中的共轭类与轨道147

2 Polya定理的特殊形式及其应用152

3 带权的Polya定理157

习题八164

第九章动态规划167

1 动态规划方法的基本思想167

2 背包问题174

3 最小代价的字母树177

习题九181

第十章回溯184

1 回溯算法的基本思想184

2 改进回溯算法的一些途径188

3 估计回溯算法的效率190

4 分支与界方法192

5 游戏树与α-β裁剪技术195

习题十199

第十一章启发式算法202

1 贪心法202

2 装箱问题208

3 工作安排问题215

4 在树形约束下的工作安排问题221

习题十一227

部分习题的解答或提示229

参考书目250