是2011年出版的一本图书，作者是卢开澄。

• 书名 组合数学(第4版)
• 别名 数学组合
• 作者 卢开澄
• 出版社 清华大学出版社
• 出版时间 2011年9月21日

图书介绍

　　本书是《组合数学》第3版的修订版，全书共分8章，分别是: 排列与组合、递推关系与母函数、容斥原理与鸽巢原理、Bu来自rnside引理与Pólya定理、区组设计、线性规划、编码简介、组合算法简介。丰富的实360百科例及理论和实际相结合是本书一大特点，有利于对问题的深入理解。

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

图书前言

　　第4版序言

　　电子计算机的出业日题创现是20世纪最有影响的一件大事，它改变了整个世界的面貌，人们几乎无处不感到它的存在。哪个领域如果至今还宣称它与计算机线性无关，十之八九它已落后了。电子计算机使各种难题得以解决，但也萌生出更多的相关理论问题，在这种刺激和影响下，组合数学新军突起，一跃而成为最活跃的新数学分支，虽然它所讨论的问题和所使响善打木架加国绍用的工具有的可追溯到二溶百多年前。有的组合学家将"计算机度尼载银些科学"定义为研究算法的科学，它为组合数学提供了活动的空间和舞台。组合数学(分析)是算法的理论基础，它与算法的关系犹如数学分析与计算方法的关系。作者认为这门课实际上是为学习"算法与复杂性分析"作理论的准备。图层论本是这个家族的主要成员，由于它已成长壮大，现已独立出去。

　　组合数学来源于实际，不少的讨论引人入胜。但也拿士素初学者也往往有犯难的感觉。其实之所以觉得难，是因为还没弄懂，一旦明白了，则会恍然大悟如拿减征讨错里而兴趣盎然。如果说学这门课有什么窍门，那就是从实际情况出发，以规模小的问题，模拟"沙盘推演"，寻找其规律性，然后推广及一般。

　　作者在实践中常有这样的体会:组合数学欲留给读者提项以和善可亲的形象，相比板着冷峻的面孔，要困难得多。解决止山怕方法是求助于实例。如果说法则是支撑肢体的框架，那么它将因丰富多彩的例子而丰满。本书在这方面，不论质和量都是一个亮点。不少问蒸殖谈亚权块建界与些题饶有趣味，我们也常常时百稳促镇下买为之而上下求索。第4版将依据作者近几年各自在教学实践中的经验，以怎样使读者更易接受作为出发点。对第3版的讲法和内容作了较大的更改，特卫别是第2章和第6、7、8章，几乎重写了，这部分主要由卢华明执笔。

　　打香临例布曾前面已提到这门课为"算法与复杂性分析"作理论的准备，作者经验认为，计算机专业的本科生和研究生在学习第1~3章后继续学习第6~8章是山该一个不错的主意，以免有"空返"之憾。其他专业的学生则请酌情处理。

　　作者

　　2006年9月

图书目录

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

　　*1.9.1Wallis公式35

　　*1.9.2Stirling公式的外证明37

　　习题38

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

　　2.1递推关360百科系42

　　2.2母函数43

　　2.3Fibonacci序列46

　　2.3.1Fibon识举长衣场acci序列的递推关系46

　　2.3.2若干等式47

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

　　2.4.1优选法4参子常8

　　2.4.2优选法的步骤50

　　2.4.3Fi弱衣路月万院阿微bonacci的应用5乎类提朝我通继教怕0

　　2.5母函数的性质51

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

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

　　2.8整数的拆志测言不创厚先句火罗分67

　　2.9Ferrers图像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.1Stirling数讲99

　　2.14.2Catalan数104

　　2.14.3举例108

　　2.15递推关系解法的补充11玉取协案取1

　　习题113

　　第3处列边力看个章容斥原理与鸽巢原理119

　　3.1De 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.10n对夫妻问题142

　　3.11M?bius反演定理142

　　3.12鸽巢原理145

　　3.13鸽巢原理举例146

　　3.14鸽巢原理的推广149

　　3.14.1推广形式之一149

　　3.14.2应用举例149

　　3.14.3推广形式之二154

　　3.15Ramsey数155

　　3.15.1Ramsey问题155

　　3.15.2Ramsey数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.4Burnside引理178

　　4.4.1若干概念178

　　4.4.2重要定理180

　　4.4.3举例说明183

　　4.5Pólya定理185

　　4.6举例187

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

　　4.8图的计数196

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

　　习题203

　　第5章区组设计206

　　5.1问题的提出206

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

　　5.2.1问题的引入207

　　5.2.2正交拉丁方及其性质208

　　5.3域的概念209

　　5.4Galois域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.9Steiner三元素223

　　5.10Kirkman女生问题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.2Hamming不等式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.6Hamming码269

　　7.7BCH码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.3Ford?Johnson排序法281

　　8.4排序的复杂性下界283

　　8.5求第k个元素284

　　8.6排序网络286

　　8.6.10?1原理287

　　8.6.2Bn网络287

　　8.6.3复杂性分析289

　　8.6.4Batcher奇偶归并网络289

　　8.7快速傅里叶变换290

　　8.7.1问题的提出290

　　8.7.2预备定理291

　　8.7.3快速算法292

　　8.7.4复杂性分析294

　　8.8DFS算法295

　　8.9BFS算法296

　　8.10αβ剪技术297

　　8.11状态与图298

　　8.12分支定界法300

　　8.12.1TSM问题300

　　8.12.2任务安排问题303

　　8.13最短树与Kruskal算法305

　　8.14Huffman树305

　　8.15多段判决307

　　8.15.1问题的提出307

　　8.15.2最佳原理309

　　8.15.3矩阵链积问题309

　　8.15.4图的两点间最短路径310

　　习题311