组合数学（第5版）

卢开澄，清华大学计算机系资深教授，长期从事组合数学、图论、计算机算法、密码学等课程的教学科研工作，2000-2004年曾到澳门科技大学资讯学院讲授组合数学、图论、计算机算法、密码学、编码理论等课程，并培养研究生。以“混合密码”成果获国家科技进步奖；与航空部合作的“远程通信”加密获国家及部级科技进步奖。著有《计算机密码学——计算机网络中的数据保密与安全（第３版）》、《计算机算法导引——设计与分析（第２版）》、《图论及其应用（第2版）》、《线性规划》等多部普通高等教育“十一五”*规划教材。获北京市教学成果奖两次，清华大学先进工作者多次。

目录

第1章排列与组合1

1.1加法法则与乘法法则1

1.2一一对应5

1.3排列与组合8

1.3.1排列与组合的模型8

1.3.2排列与组合问题的举例9

1.4圆周排列14

1.5排列的生成算法15

1.5.1序数法15

1.5.2字典序法17

1.5.3换位法18

1.6允许重复的组合与不相邻的组合20

1.6.1允许重复的组合20

1.6.2不相邻的组合21

1.6.3线性方程的整数解的个数问题21

1.6.4组合的生成21

1.7组合意义的解释22

1.8应用举例28

1.9Stirling公式36

*1.9.1Wallis公式36

*1.9.2Stirling公式的证明38

习题39

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

2.1递推关系43

2.2母函数44

2.3Fibonacci序列47

2.3.1Fibonacci序列的递推关系47

2.3.2若干等式48

2.4优选法与Fibonacci序列的应用49

2.4.1优选法49

2.4.2优选法的步骤51

2.4.3Fibonacci的应用51

2.5母函数的性质52

2.6线性常系数齐次递推关系55

2.7关于线性常系数非齐次递推关系62

2.8整数的拆分68

2.9Ferrers图像71

2.10拆分数估计74

2.11指数型母函数76

2.11.1问题的提出76

2.11.2指数型母函数的定义77

2.12广义二项式定理78

2.13应用举例81

2.14非线性递推关系举例100

2.14.1Stirling数100

2.14.2Catalan数105

2.14.3举例109

2.15递推关系解法的补充112

习题114

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

31De Morgan定理120

32容斥定理121

33容斥原理举例124

3.4棋盘多项式与有限制条件的排列129

3.5有禁区的排列132

3.6广义的容斥原理134

3.6.1容斥原理的推广134

3.6.2一般公式135

3.7广义容斥原理的应用138

3.8第2类司特林数的展开式141

3.9欧拉函数(n)142

3.10n对夫妻问题143

3.11Mbius反演定理143

3.12鸽巢原理146

313鸽巢原理举例147

314鸽巢原理的推广150

3141推广形式之一150

3142应用举例150

3.14.3推广形式之二155

3.15Ramsey数156

3.15.1Ramsey问题156

3.15.2Ramsey数159

习题162

第4章Burnside引理与Pólya定理168

41群的概念168

411定义168

412群的基本性质169

42置换群171

43循环、奇循环与偶循环175

44Burnside引理179

441若干概念179

442重要定理181

443举例说明184

45Pólya定理186

46举例188

47母函数形式的Pólya定理194

48图的计数197

习题201

第5章区组设计203

5.1问题的提出203

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

5.2.1问题的引入204

5.2.2正交拉丁方及其性质205

5.3域的概念206

5.4Galois域GF(pn)208

5.5正交拉丁方的构造211

5.6正交拉丁方的应用举例213

5.7均衡不完全的区组设计214

5.7.1基本概念214

5.7.2(b,v,r,k,λ)设计215

5.8区组设计的构成方法218

5.9Steiner三元系220

习题222

第6章编码简介225

6.1基本概念225

6.2对称二元信道226

6.3纠错码227

6.3.1近邻法则227

6.3.2Hamming不等式228

6.4若干简单的编码229

6.4.1重复码229

6.4.2奇偶校验码229

6.5线性码230

6.5.1生成矩阵与校验矩阵230

6.5.2关于生成矩阵和校验矩阵的定理233

6.5.3译码步骤233

6.6Hamming码234

6.7BCH码235

习题238

第7章组合算法简介241

7.1归并排序241

7.1.1算法241

7.1.2举例242

7.1.3复杂性分析242

7.2快速排序243

7.2.1算法的描述244

7.2.2复杂性分析245

7.3FordJohnson排序法246

7.4排序的复杂性下界248

7.5求第k个元素249

7.6排序网络251

7.6.101原理252

7.6.2Bn网络252

7.6.3复杂性分析254

7.6.4Batcher奇偶归并网络254

7.7快速傅里叶变换255

7.7.1问题的提出255

7.7.2预备定理256

7.7.3快速算法257

7.7.4复杂性分析259

7.8DFS算法260

7.9BFS算法261

7.10αβ剪枝术262

7.11状态与图263

7.12分支定界法265

7.12.1TSM问题265

7.12.2任务安排问题268

7.13短树与Kruskal算法270

7.14Huffman树270

7.15多段判决272

7.15.1问题的提出272

7.15.2原理274

7.15.3矩阵链积问题274

7.15.4图的两点间短路径275

习题276

卢开澄，清华大学计算机系资深教授，长期从事组合数学、图论、计算机算法、密码学等课程的教学科研工作，2000-2004年曾到澳门科技大学资讯学院讲授组合数学、图论、计算机算法、密码学、编码理论等课程，并培养研究生。以“混合密码”成果获国家科技进步奖；与航空部合作的“远程通信”加密获国家及部级科技进步奖。著有《计算机密码学——计算机网络中的数据保密与安全（第３版）》、《计算机算法导引——设计与分析（第２版）》、《图论及其应用（第2版）》、《线性规划》等多部普通高等教育“十一五”*规划教材。获北京市教学成果奖两次，清华大学先进工作者多次。