本书侧重于组合数学的概念和思想，包括鸽巢原理、计数技术、排列组合、Polya计数法、二项式系数、容斥原理、生成函数和递推关系以及组合结构（匹配、实验设计、图）等，深入浅出地表达了作者对该领域全面和深刻的理解。

组合数学（原书第5版）
Introductory Combinatorics Fifth Edition　
（美）Richard A. Brualdi 威斯康星大学麦迪逊分校 著　 冯 速　北京师范大学　等译
本书是系统阐述组合数学基础、理论、方法和实例的优秀教材，出版三十多年来多次改版，被MIT、哥伦比亚大学、UIUC、威斯康星大学等众多国外高校采用，对国内外组合数学教学产生了较大影响，也是相关学科的主要参考文献之一。
本书侧重于组合数学的概念和思想，包括鸽巢原理、计数技术、排列与组合、P條ya计数法、二项式系数、容斥原理、生成函数和递推关系以及组合结构（匹配、试验设计、图）等，深入浅出地表达了作者对该领域全面和深刻的理解。
自2004年出版第4版以来，作者又对本书进行了全面的修订和更新，第5版增加了有限概率、相异代表系、匹配数等内容。

作者简介
Richard A. Brualdi　美国威斯康星大学麦迪逊分校数学系教授（现已退休），曾任系主任多年。他的研究方向包括组合数学、图论、线性代数和矩阵理论、编码理论等。Brualdi教授的学术活动非常丰富，担任过多种学术期刊的主编。2000年由于在组合数学研究中所做出的杰出终身成就而获得组合数学及其应用学会颁发的欧拉奖章。

在这一新版本中，我做了一些细微的改变，具体概括如下：
　　在第1章，新增加了一节（1.6节），讨论相互重叠圆的问题，用来具体说明后面章节中所讨论的某些计数问题。之前，这一节的相关内容出现在第7章。
　　第1章中原来关于切割立方体的一节已经删除，但是相关内容放在练习题中。
　　之前版本中的第2章（鸽巢原理）改成了第3章。之前版本中关于排列和组合的第3章改成了第2章。帕斯卡公式在之前的版本中第一次出现在第5章中，现在出现在第2章中。另外，为了清晰起见，在关于集合的论述中我们不再强调“组合”这一术语，而启用了一个本质上等价的术语“子集”。然而，在多重集合的情况下，我们继续使用“组合”，而不使用在我们看来易产生混淆的术语“多重子集”。
　　此版本的第2章包含一节（2.6节）有限概率简介。
　　此版本的第3章包含Ramsey定理的证明。
　　第7章的变化比较大，其中生成函数和指数生成函数移到了本章靠前部分（7.2节和7.3节），成为更核心的内容。
　　分拆数这一节（8.3节）做了扩展。
　　之前版本中关于二分图匹配的第9章做了根本的改变。现在的第9章是新插入的章节，讨论的是相异代表系（SDR）的问题，包括婚姻和稳定婚姻匹配问题，而不再讨论二分图。
　　第9章这样改动的结果是，介绍图论的章节（第11章）不再假设先前已介绍过二分图的知识。
　　再论图论一章（之前版本中的第13章）现在变成了第12章。在本章中，新增加了关于图的匹配数一节（12.5节），在这一节中，第9章中SDR的基础结果被用于二分图。
　　有向图和网络这一章（之前是第12章）现在是第13章。它新增加了一节，回顾了二分图的匹配，其中有些相关内容出现在之前版本的第9章中。
　　对于第5版，除了以上列出的这些变化之外，还更正了我注意到的所有印刷错误；增加了少量的说明；改动了一些顺序，使前后文更加通顺；另外还增加了练习题，第5版中共有700道练习题。
　　根据多年来很多读者的评论，这本书似乎已经通过了时间的检验。因此，我总是犹豫不决而迟迟没有做出更多的改变，也没有增加更多的新话题。我不希望一本书“太长”（这一前言也不会太长），也不愿意让这本书迎合每个人的癖好。不过，我的确做了上述细节上的改变，相信这些改变会使这本书更加完善。
　　与之前各版本一样，这一版可以用于一到两个学期的本科生课程。第一个学期可以侧重计数，而第二个学期可以侧重图论和设计。也可以把相关内容合并在一起作为一个学期的课程，如讲解一些计数和图论知识，或者一些计数与设计理论知识，或者选择其他的组合搭配。下面简要说明各章以及它们之间的相互关系。
　　第1章是介绍，我通常只从中选出一两个话题，最多花两节课时间。第2章讨论的是排列和组合，这一章应该全讲。第3章讨论的是鸽巢原理，这一章至少应该做简单介绍。但是，需要注意的是，后面没有用到一些较难的鸽巢原理应用以及关于Ramsey定理那一节的内容。第4章到第8章主要讨论计数技巧及计数序列的相关性质。这些内容应该按照顺序依次讲解。第4章讨论的是排列和组合的生成方案，包括4.5节的偏序和等价关系的介绍。我认为至少应该讲解等价关系，因为它们在数学中无处不在。除了第5章关于偏序集这一节（5.7节）之外，其余各章本质上都独立于第4章，所以这一章可以跳过或者略讲。你也可以选择根本不讲解偏序集。我把关于偏序集的内容分成两节（4.5节和5.7节），目的是给学生少许时间去消化某些概念。第5章讨论的是二项式系数的性质，而第6章所涉及的是容斥原理。莫比乌斯反演那节（6.6节）可以归结到容斥原理，这一节对后面没有用。第7章比较长，讨论的是生成函数和递推关系求解。第8章主要讨论的是Catalan数、第一和第二类Stirling数、分拆数以及大Schrder数和小Schrder数。对于这一章的各节你可以选择学习，也可以选择跳过。第8章之后的各章与它都没有关系。第9章讨论的是相异代表系（所谓的婚姻问题）。第12章和第13章要用到第9章的一些内容以及第10章中的拉丁方一节（10.4节）。第10章讨论的是组合设计的某些内容，它与本书其后的内容无关。第11章和第12章对图论进行了比较全面的讨论，并稍侧重于某些图论算法。第13章讨论的是有向图和网络流。第14章讨论置换群作用下的计数问题，这一章大量使用了前面的计数思想。除了最后一个例子之外，它与关于图论和设计的各章无关。
　　当我将本书用于一学期课程时，喜欢以第14章的Burnside定理及其几个应用收尾。这种做法使学生们能够解决很多计数问题，而这些用前面几章的计数技巧是不能解决的。通常，我不会讲Pólya定理。
　　继第14章之后，我给出了本书一些练习题的答案和提示。少数练习题旁边标上了“”号，表明它们有相当的挑战性。每一个证明结束及每一个例子结束处都标有“□”号予以明示。
　　很难评说学习这本书所需要的前提条件。与其他教科书一样，高度激发学生的热情、提起学生的兴趣是很有用的，另外还需要指导教师的热情投入。也许这些前提条件应该这样描述为好：有完备的数学知识，即成功地学习了数学分析相关内容以及线性代数的初等课程。本书对数学分析使用极少，而涉及线性代数的内容也不多，因此，对不熟悉这些内容的读者来说，阅读本书应该不会产生任何问题。
　　令我感到最欣慰的就是自从本书第1版出版之后三十多年来，它仍然得到数学界专业人士的认可。
　　我非常感谢曾对之前各版本以及这一版本做出评论的人，其中包括发现印刷错误的人。他们是：Russ Rowlett,James Sellers,Michael Buchner,Leroy F.Meyers,Tom Zaslavsky,Nils Andersen,James Propp,Louis Deaett,Joel Brawley,Walter Morris,John B.Little,Manley Perkel,Cristina Ballantine,Zixia Song,Luke Piefer,Stephen Hartke,Evan VanderZee,Travis McBride,Ben Brookins,Doug Shaw,Graham Denham,Sharad Chandarana,William McGovern,Alexander Zakharin。应出版商要求而对第4版做出评论以备这一版出版的Christopher P.Grant做了非常出色的评论。Chris Jeuell对第5版提出了很多建议，使我避免了更多的印刷错误。　　Mitch Keller是一位出色的精审员。虽然我希望不要出错，但是打印稿中也许还是有些错误，这一切都是我的责任。我也非常感谢那些向我指出这些错误的每一个人。Yvonne Nagel在解决字体难题方面给予我很大的帮助，这已超出了我的专业范畴。
　　还要感谢Prentice Hall的所有出版工作人员——Bill Hoffman、Caroline Celano、Raegan Heerema，他们使第5版得以顺利完成。Pat Daly是一位优秀的文案人员。
　　我希望这本书能够继续反映出我对组合数学这门学科的热爱，以及我对讲授它的热情和方法。
　　最后，我还要感谢我的妻子Mona，她自始至终都给我的生活带来幸福、活力和勇气。

Richard A.Brualdi

数学

本书是系统阐述组合数学基础、理论、方法和实例的优秀教材，出版30多年来多次改版，被MIT、哥伦比亚大学、UIUC、威斯康星大学等众多国外高校采用，对国内外组合数学教学产生了较大影响，也是相关学科的主要参考文献之一。
本书侧重于组合数学的概念和思想，包括鸽巢原理、计数技术、排列组合、Polya计数法、二项式系数、容斥原理、生成函数和递推关系以及组合结构（匹配、实验设计、图）等，深入浅出地表达了作者对该领域全面和深刻的理解。除包含第4版中的内容外，本版又进行了更新，增加了有限概率、匹配数等内容。此外，各章均包含大量练习题，并在书末给出了参考答案与提示。

（美）Richard A. Brualdi 著 威斯康星大学麦迪逊分校：Richard A. Brualdi 美国威斯康星大学麦迪逊分校数学系教授（现已退休），曾任该系主任多年。他的研究方向包括组合数学、图论、线性代数和矩阵理论、编码理论等。Brualdi教授的学术活动非常丰富，担任过多种学术期刊的主编。2000年由于“在组合数学研究中所做出的杰出终身成就”而获得组合数学及其应用学会颁发的欧拉奖章。 加作者照片（影印书上有），并加影印书小封面，书号978-7-111-26525-2，定价：49.00元

冯速 等译：暂无简介

组合数学是计算机出现以后迅速发展起来的一门数学分支。计算机科学即算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是组合数学。
　　本书译自Richard A.Brualdi的《Introductory Combinatorics，Fifth Edition》一书，着重于组合学思想的阐述，包括对鸽巢原理、计数技术、排列与组合、Pólya计数法、二项式系数、容斥原理、生成函数与递推关系以及一些组合结构（如匹配、设计和图等）的讨论。第5版经过较大的修订，添加了有限概率、相异代表系、匹配数等内容，同时删除若干不影响对组合数学理解的内容，或将其移作练习题，以保持本书内容不致过于庞大而使读者却步。为方便读者阅读、理解，作者在这一版中做出了很多努力。比如，使用“子集”来描述“组合”的概念，这两个术语虽然本质上是等价的，但对于初学者来说，显然“子集”要比“组合”容易理解得多。更重要的是，通过布局上的调整，使前后文更加通顺，衔接更加自然。
　　在本书前言中，作者比较详细地介绍了各章的内容和它们之间的关系，谈到了使用本书伸缩性的授课方案以及作者讲授时的经验和偏好，这对于我们深入了解本书的内容和结构以便将它作为教材恰当地使用是很有帮助的。本书原著通俗流畅，深入浅出，生动灵活的写作风格反映了作者对该领域的热情和作为课程讲授的乐趣。
　　本书第5版的翻译工作参考了第4版译稿，感谢第4版译者的辛勤工作。在翻译过程中，译者对原书中出现的明显排印错误进行了修改，并对基本流算法的陈述做了改写，以便更容易理解，希望不是画蛇添足。
　　除封面署名外，参与本书翻译工作的人员还有马晶、易超、龚治、李思源、陈辉、周亦洋、韦添等。
　　由于时间和水平的限制，译文中难免疏漏和错误，期盼广大读者的批评与指正。

译者
2012年2月

出版者的话
译者序
前言
第1章　什么是组合数学1
　1.1　例子：棋盘的完美覆盖2
　1.2　例子：幻方4
　1.3　例子：四色问题6
　1.4　例子：36军官问题7
　1.5　例子：最短路径问题9
　1.6　例子：相互重叠的圆10
　1.7　例子：Nim游戏10
　1.8　练习题12
第2章　排列与组合16
　2.1　四个基本的计数原理16
　2.2　集合的排列21
　2.3　集合的组合(子集)24
　2.4　多重集合的排列28
　2.5　多重集合的组合32
　2.6　有限概率34
　2.7　练习题37
第3章　鸽巢原理42
　3.1　鸽巢原理：简单形式42
　3.2　鸽巢原理：加强版44
　3.3　Ramsey定理47
　3.4　练习题50
第4章　生成排列和组合53
　4.1　生成排列53
　4.2　排列中的逆序57
　4.3　生成组合60
　4.4　生成r子集67
　4.5　偏序和等价关系70
　4.6　练习题73
第5章　二项式系数78
　5.1　帕斯卡三角形78
　5.2　二项式定理80
　5.3　二项式系数的单峰性85
　5.4　多项式定理88
　5.5　牛顿二项式定理90
　5.6　再论偏序集92
　5.7　练习题95
第6章　容斥原理及应用100
　6.1　容斥原理100
　6.2　带重复的组合105
　6.3　错位排列107
　6.4　带有禁止位置的排列110
　6.5　另一个禁止位置问题113
　6.6　莫比乌斯反演114
　6.7　练习题124
第7章　递推关系和生成函数128
　7.1　若干数列128
　7.2　生成函数134
　7.3　指数生成函数138
　7.4　求解线性齐次递推关系142
　7.5　非齐次递推关系152
　7.6　一个几何例子157
　7.7　练习题160
第8章　特殊计数序列164
　8.1　Catalan数164
　8.2　差分序列和Stirling数169
　8.3　分拆数180
　8.4　一个几何问题185
　8.5　格路径和Schrder数187
　8.6　练习题195
第9章　相异代表系198
　9.1　问题表述198
　9.2　SDR的存在性200
　9.3　稳定婚姻204
　9.4　练习题207
第10章　组合设计210
　10.1　模运算210
　10.2　区组设计217
　10.3　Steiner三元系224
　10.4　拉丁方228
　10.5　练习题241
第11章　图论导引245
　11.1　基本性质245
　11.2　欧拉迹251
　11.3　哈密顿路径和哈密顿圈256
　11.4　二分多重图259
　11.5　树263
　11.6　Shannon开关游戏268
　11.7　再论树271
　11.8　练习题278
第12章　再论图论284
　12.1　色数284
　12.2　平面和平面图290
　12.3　五色定理293
　12.4　独立数和团数295
　12.5　匹配数300
　12.6　连通性303
　12.7　练习题306
第13章　有向图和网络310
　13.1　有向图310
　13.2　网络316
　13.3　回顾二分图匹配321
　13.4　练习题326
第14章　Pólya计数330
　14.1　置换群与对称群330
　14.2　Burnside定理337
　14.3　Pólya计数公式341
　14.4　练习题351
练习题答案与提示354
参考文献363
索引364