卢开澄、卢华明编著的《组合数学》是《组合数学》第3版的修订版，内容包括：排列与组合、递推关系与母函数、容斥原理与鸽巢原理、Burnside引理与P6lya定理、区组设计、线性规划、编码简介、组合算法简介。本书内容全面，语言通俗，论述严谨，理论与实践紧密相联系，是计算机系本科生和研究生的教学用书，也可作为数学专业师生的教学参考书。

卢开澄、卢华明编著的《组合数学》是《组合数学》第3版的修订版，全书共分8章，分别是：排列与组合、递推关系与母函数、容斥原理与鸽巢原理、Burnside引理与Polya定理、区组设计、线性规划、编码简介、组合算法简介。丰富的实例及理论和实际相结合是本书一大特点，有利于对问题的深入理解。

《组合数学》是计算机系本科生和研究生的教学用书，也可作为数学专业师生的教学参考书。

第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.9 Stirling公式35

*1.9.1 Wallis公式35

*1.9.2 Stirling公式的证明37

 习题38

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

 2.1 递推关系42

 2.2 母函数43

 2.3 Fibonacci序列46

2.3.1 Fibonacci序列的递推关系46

2.3.2 若干等式47

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

2.4.1 优选法48

2.4.2 优选法的步骤50

2.4.3 Fibonacci的应用50

 2.5 母函数的性质51

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

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

 2.8 整数的拆分67

 2.9 Ferrers图像70

 2.10 拆分数估计73

 2.11 指数型母函数75

2.11.1 问题的提出75

2.11.2 指数型母函数的定义76

 2.12 广义二项式定理77

 2.13 应用举例80

 2.14 非线性递推关系举例99

2.14.1 Stirling数99

2.14.2 Catalan数104

2.14.3 举例108

 2.15 递推关系解法的补充111

 习题113

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

 3.1 De Morgan定理119

 3.2 容斥定理120

 3.3 容斥原理举例123

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

 3.5 有禁区的排列131

 3.6 广义的容斥原理133

3.6.1 容斥原理的推广133

3.6.2 一般公式134

 3.7 广义容斥原理的应用137

 3.8 第二类Stirling数的展开式140

 3.9 欧拉函数φ(n)141

 3.10 n对夫妻问题142

 3.11 Mbius反演定理142

 3.12 鸽巢原理145

 3.13 鸽巢原理举例146

 3.14 鸽巢原理的推广149

3.14.1 推广形式之一149

3.14.2 应用举例149

3.14.3 推广形式之二154

 3.15 Ramsey数155

3.15.1 Ramsey问题155

3.15.2 Ramsey数158

习题161

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

 4.1 群的概念167

4.1.1 定义167

4.1.2 群的基本性质168

 4.2 置换群170

 4.3 循环、奇循环与偶循环174

 4.4 Burnside引理178

4.4.1 若干概念178

4.4.2 重要定理180

4.4.3 举例说明183

 4.5 Pólya定理185

 4.6 举例187

 4.7 母函数形式的Pólya定理193

 4.8 图的计数196

 4.9 Pólya定理的若干推广200

 习题203

第5章 区组设计206

 5.1 问题的提出206

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

5.2.1 问题的引入207

5.2.2 正交拉丁方及其性质208

 5.3 域的概念209

 5.4 Galois域GF(pm)211

 5.5 正交拉丁方的构造214

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

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

5.7.1 基本概念217

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

 5.8 区组设计的构成方法221

 5.9 Steiner三元素223

 5.10 Kirkman女生问题225

 习题226

第6章 线性规划228

 6.1 问题的提出228

 6.2 线性规划的问题230

 6.3 凸集230

 6.4 线性规划的几何意义231

 6.5 单纯形法的理论基础233

6.5.1 松弛变量233

6.5.2 解的充要条件234

 6.6 单纯形法与单纯形表格238

 6.7 改善的单纯形法245

 6.8 对偶概念247

 6.9 对偶单纯形法253

 习题258

第7章 编码简介260

 7.1 基本概念260

 7.2 对称二元信道261

 7.3 纠错码262

7.3.1 最近邻法则262

7.3.2 Hamming不等式263

 7.4 若干简单的编码264

7.4.1 重复码264

7.4.2 奇偶校验码264

 7.5 线性码265

7.5.1 生成矩阵与校验矩阵265

7.5.2 关于生成矩阵和校验矩阵的定理268

7.5.3 译码步骤268

 7.6 Hamming码269

 7.7 BCH码270

 习题273

第8章 组合算法简介276

 8.1 归并排序276

8.1.1 算法276

8.1.2 举例277

8.1.3 复杂性分析277

 8.2 快速排序278

8.2.1 算法的描述279

8.2.2 复杂性分析280

 8.3 FordJohnson排序法281

 8.4 排序的复杂性下界283

 8.5 求第k个元素284

 8.6 排序网络286

8.6.1αβ原理287

8.6.2 Bn网络287

8.6.3 复杂性分析289

8.6.4 Batcher奇偶归并网络289

 8.7 快速傅里叶变换290

8.7.1 问题的提出290

8.7.2 预备定理291

8.7.3 快速算法292

8.7.4 复杂性分析294

 8.8 DFS算法295

 8.9 BFS算法296

 8.10 αβ剪技术297

 8.11 状态与图298

 8.12 分支定界法300

8.12.1 TSM问题300

8.12.2 任务安排问题303

 8.13 最短树与Kruskal算法305

 8.14 Huffman树305

 8.15 多段判决307

8.15.1 问题的提出307

8.15.2 最佳原理309

8.15.3 矩阵链积问题309

8.15.4 图的两点间最短路径310

 习题311