引言ⅩⅤ第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司特林(Stirling)公式58

1.11.1瓦利斯(Wallis)公式58

1.11.2司特林公式的证明60

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

2.1母函数的引入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指数型母函数97

2.6.1问题的提出97

2.6.2指数型母函数的引入99

2.7递推关系举例104

2.8Fibonacci(费卜拉契)数列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章容斥原理与鸽巢原理207

3.1容斥原理207

3.1.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.8n对夫妻问题249

3.9反演公式252

3.9.1反演定理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.4Galois域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有限射影空间387

5.11.1二维的射影几何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.20BCH码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.3Ford\|Johnson排序法440

6.4求第k个元素444

6.5排序网络446

6.5.101原理447

6.5.2Bn网络448

6.5.3复杂性估计449

6.5.4Batcher奇偶归并网络451

6.6快速傅里叶变换(FFT)453

6.6.1问题的提出453

6.6.2预备定理454

6.6.3快速算法455

6.6.4复杂性分析459

6.7DFS算法460

6.7.1算法的引入460

6.8判决树465

6.8.1银币问题465

6.8.2举例468

6.9渡河问题472

6.10TSM问题与分支定界法473

6.11多段判决478

6.11.1问题的提出478

6.11.2最佳原理481

6.11.3矩阵链积问题481

6.12NPC问题483