目录
第0 章绪论........................................................................... 1
第1 章排列组合...................................................................... 8
1.1 基本计数原理.............................................................................. 8
1.1.1 加法原理........................................................................... 8
1.1.2 乘法原理........................................................................... 10
1.1.3 减法原理........................................................................... 11
1.1.4 除法原理........................................................................... 12
1.2 集合的排列与组合........................................................................ 13
1.2.1 排列................................................................................. 13
1.2.2 组合................................................................................. 15
1.3 球盒模型与格路模型..................................................................... 18
1.3.1 球盒模型........................................................................... 18
1.3.2 格路模型........................................................................... 19
1.4 二项式定理与组合恒等式............................................................... 21
1.4.1 二项式定理与二项式系数...................................................... 21
1.4.2 利用二项式定理推导组合恒等式.............................................. 24
1.4.3 多项式定理........................................................................ 26
1.5 多重排列与环形排列..................................................................... 27
1.5.1 多重排列........................................................................... 27
1.5.2 环形排列........................................................................... 30
1.6 可重组合与不相邻组合.................................................................. 31
1.6.1 可重组合........................................................................... 31
1.6.2 不相邻组合........................................................................ 36
1.7 生成全排列....................................................................... 36
1.7.1 Stirling 近似公式................................................................. 36
1.7.2 字典序法........................................................................... 37
1.7.3 递增进位制数法.................................................................. 40
1.7.4 递减进位制数法.................................................................. 42
1.7.5 SJT 算法............................................................................ 42
1.8 生成组合........................................................................ 45
习题.................................................................................. 46
第2 章鸽巢原理.................................................................... 52
2.1 鸽巢原理的基本形式..................................................................... 52
2.2 鸽巢原理的推广形式..................................................................... 55
2.3 整点问题.................................................................... 57
2.4 Ramsey 问题..................................................................... 58
2.4.1 完全图二染色的Ramsey 定理................................................. 59
2.4.2 Ramsey 定理的推广形式.............................................. 62
习题................................................................................ 63
第3 章母函数........................................................................ 66
3.1 引论............................................................................ 66
3.2 母函数的性质........................................................... 69
3.3 整数拆分与Ferrers 图像................................................................. 72
3.3.1 有序拆分........................................................................... 73
3.3.2 无序拆分........................................................................... 73
3.3.3 Ferrers 图像........................................................................ 77
3.4 指数型母函数................................................................... 79
习题.............................................................................. 84
第4 章线性常系数递推关系..................................................................... 87
4.1 引论.............................................................................. 87
4.2 Fibonacci 数列.............................................................. 89
4.3 母函数与递推关系........................................................................ 94
4.4 齐次线性常系数递推关系............................................................... 104
4.4.1 特征多项式........................................................................ 105
4.4.2 通过特征多项式求解齐次线性常系数递推关系............................ 106
4.5 非齐次线性常系数递推关系............................................................ 118
4.5.1 差分法.............................................................................. 118
4.5.2 特解法.............................................................................. 123
4.6 递推关系的渐近分析..................................................................... 129
习题.............................................................................. 137
第5 章特殊计数序列............................................................... 141
5.1 Catalan 数...................................................................... 141
5.2 错位排列...................................................................... 148
5.3 第二类Stirling 数........................................................... 151
5.4 第一类Stirling 数............................................................. 160
5.4.1 无符号的第一类Stirling 数..................................................... 160
5.4.2 有符号的第一类Stirling 数..................................................... 164
5.4.3 第一类与第二类Stirling 数的关系............................................ 165
习题.............................................................................. 167
第6 章容斥原理..................................................................... 169
6.1 容斥原理及其证明........................................................................ 169
6.2 带约束的排列问题........................................................................ 175
6.3 带约束的组合问题........................................................................ 183
6.4 广义容斥原理................................................................... 187
6.5 M?bius 反演.................................................................... 188
习题............................................................................... 195
第7 章Pólya 计数理论................................................................ 199
7.1 群论基础..................................................................... 199
7.2 置换群...................................................................... 202
7.3 Burnside 引理.............................................................. 210
7.4 Pólya 计数定理.............................................................. 214
7.5 空间多面体的染色问题.......................................................... 218
习题................................................................................ 225
第8 章组合设计......................................................................... 229
8.1 区组设计...................................................................... 229
8.1.1 平衡不完全区组设计............................................................ 229
8.1.2 对称的平衡不完全区组设计.................................................... 235
8.1.3 Steiner 三元系..................................................................... 241
8.1.4 区组设计的可解性............................................................... 243
8.2 有限平面几何................................................................... 246
8.2.1 有限射影平面..................................................................... 246
8.2.2 利用有限域构造有限射影平面................................................. 252
8.2.3 有限仿射平面..................................................................... 254
8.2.4 利用有限域构造有限仿射平面................................................. 259
8.3 正交拉丁方.................................................................... 260
8.3.1 拉丁方.............................................................................. 261
8.3.2 互正交拉丁方..................................................................... 265
习题................................................................................ 273
附录A 离散数学基础..................................................................... 277
A.1 集合与偏序关系.......................................................................... 277
A.2 偏序卷积与M?bius 反演................................................................ 281
附录B 组合数学中的代数结构.................................................................. 289
B.1 群............................................................................. 289
B.2 环与形式幂级数环........................................................................ 292
B.3 有限域........................................................................ 299
