《组合数学教程》

第一章导论1

1-1 组合数学的历史发展和中心问题1

1-2 棋盘的完备覆盖1

1-3 幻方3

习题一7

第二章排列和组合8

2-1 加法法则和乘法法则8

2-2 集合的排列与组合11

2-3 多重集合的排列和组合16

2-4 排列数和组合数的一些重要性质21

2-5 组合恒等式的组合解释26

2-6 P（n,r）和（nr）的取值范围的扩充29

习题二36

第三章二项式系数与组合恒等式39

3-1 二项式系数的几何解释39

3-2 二项式定理及其应用40

3-3 格点平面和组合恒等式44

3-4 多项式定理49

习题三51

第四章母函数54

4-1 母函数的引入54

4-2 形式幂级数的代数56

4-3 母函数的性质及其应用60

4-4 母函数在组合问题中的应用66

4-5 正整数的分拆70

4-6 母函数对组合恒等式的应用75

4-7 指数型母函数78

习题四83

第五章递归关系86

5-1 递归关系的基本概念和实例86

5-2 用迭代和归纳法解一阶递归关系92

5-3 用特征根法解常系数线性递归关系98

5-4 用母函数法求解递归关系109

5-5 排序算法的分析119

习题五125

第六章Fibonacci数、Catalan数和Stirling数129

6-1 Fibonacci数129

6-2 Catalan数133

6-3 第一类Stirling数139

6-4 第二类Stirling数141

习题六147

第七章容斥原理和反演公式150

7-1 容斥原理150

7-2 容斥原理在排列组合问题中的应用155

7-3 容斥原理在初等整数论中的应用159

7-4 容斥原理在图论等问题中的应用161

7-5 第一反演公式及其应用163

7-6 麦比乌斯反演公式及其应用168

习题七174

第八章鸽笼原理和Ramsey定理176

8-1 鸽笼原理的最简形式176

8-2 鸽笼原理的加强形式179

8-3 Ramsey定理182

8-4 Ramsey数r（p,q）的性质184

习题八187

第九章Pólya定理188

9-1 置换群189

9-2 轮换与置换的奇偶性193

9-3 置换群的轮换指标199

9-4 Burnside引理201

9-5 Pólya基本定理205

9-6 带权的pólya定理211

习题九217

习题答案与提示219

参考文献223