组合·算法·理论与应用PDF电子书下载

前言 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