前言 1
第一章 鸽巢原理与Ramsey定理 1
1.1 鸽巢原理 1
1.2 鸽巢原理的加强形式 4
1.3 Ramsey问题与Ramsey数 6
1.4 Ramsey定理 13
1.5 Ramsey定理的应用 17
第二章 基本计数问题 20
2.1 加法原则与乘法原则 20
2.2 排列与组合问题 21
2.3 重集的排列与组合 29
2.4 应用 43
2.5 排列与组合的生成算法 48
2.6 二项式系数及其应用 52
第三章 母函数及其应用 65
3.1 形式幂级数与普母函数 65
3.2 普母函数与组合计数 69
3.3 指母函数与排列计数 74
3.4 应用 78
第四章 递推关系及应用 84
4.1 差分及其应用 84
4.2 常系数线性差分方程 93
4.3 递推关系的建立与求解 103
4.4 应用母函数求解递推关系问题 112
第五章 容斥原理及其应用 120
5.1 容斥原理 121
5.2 容斥原理的一般形式 124
5.3 容斥原理的应用 129
5.4 更列问题 136
5.5 相邻禁位排列问题 140
5.6 棋子多项式及其应用 143
第六章 分配分拆与特殊计数 151
6.1 映射计数问题 152
6.2 Fibonacci数列及其应用 155
6.3 Catalan数及其应用 161
6.4 两类Stirling数及其应用 166
6.5 分配问题 178
6.6 分拆问题 185
第七章 Pólya计数理论及其应用 202
7.1 置换群的共轭类 203
7.2 Burnside引理 208
7.3 置换群的循环指标 211
7.4 Burnside引理的应用 217
7.5 Pólya定理及其应用 226
8.1 第一反演定理及应用 236
第八章 反演理论及其应用 236
8.2 M?bius反演理论 244
8.3 应用 252
第九章 相异代表系及其应用 257
9.1 SDR与Hall定理 258
9.2 二部图的匹配问题 265
9.3 一个算法 269
9.4 关于SDR的计数问题 275
9.5 SDR与(0,1)—矩阵的积和式 279
第十章 组合设计 284
10.1 拉丁方与正交拉丁方 284
10.2 区组设计与关联矩阵 294
10.3 区组设计构造方法 304
10.4 Hadamard矩阵及其性质 308
10.5 t—(b,v,r,k,λ)—设计 316
10.6 设计的同构 320
第十一章 幻方及其构造 326
11.1 幻方及其性质 326
11.2 奇数阶幻方的构造 332
11.3 偶数阶幻方的构造 341
11.4 一般幻方的构造 343
11.5 一些特殊幻方的构造 351
11.6 Abelian群上的幻方 356
第十二章 图的标号问题 359
12.1 图的优美标号问题 360
12.2 图的其他标号问题 362
12.3 一类弱边优美图 366
12.4 一类超幻图 372
第十三章 组合算法 379
13.1 BFS与DFS算法 380
13.2 回溯法(Bach Track) 382
13.3 分枝定界法 389
13.4 对弈树与α—β剪裁算法 395
13.5 Greedy算法 401
13.6 工作安排问题 405
13.7 稳定指派算法 407
13.8 “入学问题”算法 411
第十四章 组合优化与算法复杂性分析 413
14.1 组合优化问题 413
14.2 算法复杂性分析 416
14.3 P类与NP类 428
14.4 NP—完全问题 429
14.5 强NP—完全问题与NP—难问题 432
参考文献 435
后记 438