第1章 基本解题方法与计数法则 1
1.1 组合数学简介与基本解题方法 1
1.1.1 组合数学简介 1
1.1.2 基本解题方法 1
1.2 常用符号与基本计数法则 3
1.2.1 常用符号 3
1.2.2 基本计数法则 4
习题1 8
2.1.1 二项式定理 9
2.1 二项式定理与杨辉三角形 9
第2章 二项式与多项式定理 9
2.1.2 杨辉三角形 10
2.2 多项式定理 15
2.2.1 多项式定理简介 15
2.2.2 多项式系数的性质 18
2.2.3 多项式系数的计数意义 20
习题2 21
第3章 排列与组合 24
3.1 初等排列与组合 24
3.1.1 排列 24
3.1.2 组合 32
3.2 排列与组合恒等式 36
3.2.1 基本恒等式 36
3.2.2 组合恒等式 36
3.2.3 排列恒等式 37
3.2.4 可重组合恒等式 38
3.3 网络路径问题 39
3.4 进位制与正整数的阶乘表示法 42
3.4.1 进位制 42
3.4.3 正整数的阶乘表示法 43
3.4.2 最优进制 43
3.5 排列与组合的生成 44
3.5.1 排列的生成算法 44
3.5.2 组合的生成算法 49
3.6 Wallis公式 49
3.7 Stirling公式 50
习题3 52
第4章 母函数与递推关系 54
4.1 母函数 54
4.1.1 母函数的定义 54
4.1.2 母函数的性质 55
4.2.1 Hanoi塔问题 57
4.2 递推关系 57
4.2.2 Fibonacci级数 58
4.2.3 递推关系的定义 61
4.2.4 有理分式的分项表示 62
4.2.5 递推关系的解 63
4.3 普母函数与递推关系 66
4.3.1 示例 66
4.3.2 线性常系数齐次递推关系的母函数解法 67
4.3.3 线性常系数非齐次递推关系的母函数解法 70
4.4.1 普母函数与组合 71
4.4 母函数与排列组合 71
4.4.2 指母函数与排列 73
4.5 指母函数与错排 74
4.6 普母函数与分拆 75
4.6.1 分拆的定义 75
4.6.2 有序分拆 76
4.6.3 Ferrers图 77
4.6.4 无序分拆 79
4.6.5 关于p(n) 82
4.7.1 三角剖分问题 86
4.7.2 乘法结合方式问题 86
4.7 普母函数与Catalan数 86
4.7.3 Catalan数的通项公式 87
4.7.4 Catalan数的组合意义 88
4.7.5 Catalan数的性质 89
4.8 母函数与Stirling数 90
4.8.1 Stirling数的定义 90
4.8.2 Stirling数的递推关系 91
4.8.3 Stirling数的母函数 94
4.8.4 Stirling数的通项公式 96
4.8.5 Stirling数的组合意义 96
4.9 球盒分配问题 99
4.8.6 Stirling数的性质 99
4.10 有限和式 103
4.10.1 递推关系求有限和式 103
4.10.2 母函数求有限和式 103
4.10.3 差分表求有限和式 104
习题4 109
第5章 容斥原理 111
5.1 容斥原理 111
5.1.1 容斥原理的简单形式 111
5.1.2 容斥原理的一般形式 113
5.1.3 对称筛公式 118
5.2 容斥原理与限位排列 119
5.3.1 棋盘多项式 121
5.3 棋盘多项式与限位排列 121
5.3.2 限位排列 122
5.4 M？bius函数与Euler函数 123
5.5 M？bius反演 125
5.6 多重集的圆排列 127
习题5 131
第6章 鸽笼原理 132
6.1 鸽笼原理 132
6.1.1 鸽笼原理的简单形式 132
6.1.3 鸽笼原理的推广 133
6.1.2 鸽笼原理的基本形式 133
6.2 Ramsey理论 140
6.2.1 Ramsey定理 140
6.2.2 Ramsey数 142
习题6 146
第7章 几何图形计数 147
7.1 简单图形计数 147
7.2 子图形计数 148
7.3 图形的切割 154
7.4 折线法 157
7.5 整点与整边三角形 159
习题7 161
8.1 群的基本概念 162
第8章 P'olya定理 162
8.2 置换与置换群 163
8.2.1 置换 163
8.2.2 置换群 164
8.3 轮换与置换的奇偶性 165
8.3.1 轮换 165
8.3.2 置换的奇偶性 166
8.4 Burnside引理 168
8.4.1 共轭类 168
8.4.3 不变置换类 169
8.4.2 置换群的轨道 169
8.4.4 Burnside引理 170
8.5 P'olya定理 173
8.6 母函数型的P'olya定理 174
习题8 178
第9章 组合设计 180
9.1 拉丁方 180
9.1.1 拉丁方的概念 180
9.1.2 正交拉丁方 181
9.2 域 182
9.2.1 域的概念 182
9.2.2 Galois域 183
9.2.3 正交拉丁方的构造 185
9.3 区组设计 186
9.3.1 区组设计 186
9.3.2 完全区组设计 187
9.3.3 均衡不完全区组设计 188
9.3.4 区组设计的构造 191
9.4 Hadamard矩阵 194
9.4.1 Hadamard矩阵 194
9.4.2 Hadamard矩阵的构成 195
9.5.1 编码及其分类 197
9.5 编码理论简介 197
9.5.2 线性码 198
习题9 204
第10章 组合算法及其复杂性 206
10.1 排序 206
10.1.1 选择排序 206
10.1.2 气泡浮起排序 207
10.1.3 分段交换排序 208
10.1.4 树型排序 209
10.1.5 合并排序 211
10.1.6 FORD_JOHNSON排序 212
10.2.2 折半查找 213
10.2 查找 213
10.2.1 顺序查找 213
10.2.3 分块查找 214
10.3 寻求第k个元素 215
10.4 快速Fourier变换 216
10.5 组合算法的复杂性 218
10.5.1 示例 218
10.5.2 贪心算法的时间上界 219
10.5.3 “倒树”算法 220
10.5.4 组合算法的复杂性问题 221
习题10 222
习题1答案 223
附录A 习题答案与提示 223
习题2答案 225
习题3答案 232
习题4答案 232
习题5答案 239
习题6答案 241
习题7答案 243
习题8答案 244
习题9答案 245
参考文献 247