组合数学PDF电子书下载

第1章 排列与组合 1

1.1 基本计数法则 1

1.1.1 加法法则、乘法法则及排列与组合 1

1.1.2 应用举例 2

1.2 一一对应 5

1.3 排列 11

1.4 圆周排列 15

1.5 组合 16

1.6 排列的生成算法 23

1.6.1 序数法 23

1.6.2 字典序法 26

1.6.3 换位法 28

1.7 组合的生成 30

1.8 允许重复的组合与不相邻的组合 31

1.8.1 允许重复的组合 31

1.8.2 不相邻的组合 33

1.9 组合意义的解释 34

1.10 应用举例 46

1.11 司特林（Stir1ing）公式 58

1.11.1 瓦利斯（Wa11is）公式 58

1.11.2 司特林公式的证明 60

习题 63

2.1 母函数的引入 68

第2章 母函数与递推关系 68

2.2 母函数的性质 73

2.2.1 若干基本的母函数 74

2.2.2 基本公式 75

2.3 整数的拆分 80

2.4 费勒斯（Ferrers）图像 85

2.5 关于拆分数p（n）的讨论 88

2.5.1 欧拉公式 88

2.5.2 拆分数估计式 94

2.6.1 问题的提出 97

2.6 指数型母函数 97

2.6.2 指数型母函数的引入 99

2.7 递推关系举例 104

2.8 Fibonacci（费卜拉契）数列 115

2.8.1 问题的提出 115

2.8.2 问题的解 116

2.8.3 若干等式 119

2.8.4 优选法 121

2.9 解线性常系数递推关系特征根法 126

2.9.1 二阶线性常系数齐次递推关系 126

2.9.2 一阶、二阶线性常系数非齐次递推关系 133

2.9.3 叠加原理 136

2.10 任意阶齐次递推关系 137

2.11 一般线性常系数非齐次递推关系 145

2.12 应用举例 151

2.13 非线性递推关系举例 176

2.13.1 司特林（stirling）数 176

2.13.2 卡特朗（Catalan）数 184

2.13.3 举例 189

2.14 递推关系解法的补充 195

习题 198

3.1.1 引论 207

第3章 容斥原理与鸽巢原理 207

3.1 容斥原理 207

3.1.2 容斥原理的两个基本公式 208

3.1.3 例子 212

3.2 棋盘多项式和有限制条件的排列 219

3.2.1 有限制的排列 219

3.2.2 棋盘多项式 219

3.2.3 有禁区的排列问题 223

3.3 广义的容斥原理 228

3.3.1 问题的引入 228

3.3.2 特殊情况 229

3.3.3 一般公式 231

3.3.4 广义容斥原理的证明 235

3.4 广义容斥原理的若干应用 238

3.5 第二类司特林数展开式 242

3.6 错排问题的推广 244

3.7 容斥原理在数论上的应用 246

3.7.1 埃拉托逊斯（Eratosthenes）筛法 246

3.7.2 欧拉函数φ(n) 248

3.8 n对夫妻问题 249

3.9.1 反演定理 252

3.9 反演公式 252

3.9.2 若干应用 256

3.10 鸽巢原理 259

3.10.1 问题的引入 259

3.10.2 一般的鸽巢原理 260

3.11 鸽巢原理的推广 265

3.11.1 推广形式之一 265

3.11.2 例 265

3.11.3 推广形式之二 274

3.12 拉蒙赛（Ramsey）数 275

3.12.1 拉蒙赛问题 275

3.12.2 拉蒙赛数 281

习题 285

第4章 贝恩塞特（Burnside）引理与波利亚（Pólya）定理 294

4.1 群的概念 294

4.1.1 定义 294

4.1.2 群的基本性质 297

4.2 置换群 299

4.3 循环、奇循环与偶循环 305

4.4 贝恩塞特（Burnside）引理 312

4.4.1 若干概念 312

4.4.2 重要定理 315

4.4.3 例 320

4.5 波利亚（Pólya）定理 324

4.6 举例 327

4.7 母函数形式的波利亚定理 336

4.8 图的计数 342

4.9 波利亚定理的若干推广 348

习题 354

第5章 区组设计与编码 357

5.1 问题的提出 357

5.2 拉丁方与正交的拉丁方 359

5.2.1 问题的引入 359

5.2.2 正交拉丁方及其性质 361

5.3 域的概念 363

5.4 Galois域GF(pn) 365

5.5 正交拉丁方的构造 368

5.6 正交拉丁方应用举例 372

5.7 均衡不完全的区组设计（BIBD） 374

5.7.1 基本概念 374

5.7.2 (b,v,r,k,t)－设计 374

5.8 区组设计的构成方法 380

5.9 斯梯纳三元系 383

5.10 科克曼女生问题 386

5.11.1 二维的射影几何 387

5.11 有限射影空间 387

5.11.2 有限域上的射影空间 391

5.12 阿达玛（Hadamard）矩阵 392

5.13 编码理论的基本概念 398

5.14 对称二元信道 402

5.15 纠错码 404

5.15.1 最近邻法则 404

5.15.2 汉明不等式 405

5.16 若干简单的编码 406

5.16.1 重复码 406

5.16.2 奇偶校验码 407

5.17 线性码 408

5.17.1 生成矩阵与校验矩阵 408

5.17.2 关于生成矩阵和校验矩阵的定理 412

5.17.3 译码步骤 413

5.18 汉明码 413

5.19 陪集译码法 416

5.20 BCH码 420

5.21 其他编码技术简介 423

5.21.1 利用区组设计纠错码 423

5.21.2 利用阿达玛矩阵进行编码 424

习题 426

第6章 组合算法与复杂性分析 432

6.1 归并排序算法 432

6.1.1 归并排序 432

6.1.2 举例 433

6.1.3 复杂性分析 434

6.2 快速排序 435

6.2.1 算法的描述 435

6.2.2 复杂性分析 438

6.3 F0rd-Johnson排序法 440

6.4 求第k个元素 444

6.5 排序网络 446

6.5.1 0-1原理 447

6.5.2 Bn网络 448

6.5.3 复杂性估计 449

6.5.4 Batcher奇偶归并网络 451

6.6 快速傅里叶变换（FFT） 453

6.6.1 问题的提出 453

6.6.2 预备定理 454

6.6.3 快速算法 455

6.6.4 复杂性分析 459

6.7.1 算法的引入 460

6.7 DFs算法 460

6.8 判决树 465

6.8.1 银币问题 465

6.8.2 举例 468

6.9 渡河问题 472

6.10 TSM问题与分支定界法 473

6.11 多段判决 478

6.11.1 问题的提出 478

6.11.2 最佳原理 481

6.11.3 矩阵链积问题 481

6.12 NPC问题 483