本书写作方法非常出色，第2版保持了前一版的高质量，并进行了大量更新。书中内容叙述非常翔实，便于学生理解，例子讲解生动并富有启发性，而且所涉及的应用范围之广更是罕见。
　　——John Elwin，圣迭戈州立大学

　　本书介绍组合数学的基本知识和应用，涉及计算机科学、生物学、化学、心理学及基因工程等前沿学科中的最新应用，应用层面非常宽泛。本书布局精巧、内容翔实，对题材的讨论深入浅出，简明扼要，包含了很多高级的组合数学技术与方法。全书分为四个部分：第一部分介绍组合数学的基本工具，第二部分介绍计数问题，第三部分讲述组合数学求解中的存在问题，第四部分讨论优化问题。
　　本书第1版曾被国外多所大学采纳为教材，这一版根据最新技术发展进行了大量修改，书中包含大量出色的实例和练习，可作为高等院校数学专业和计算机科学专业“组合数学”课程的教材。

无

本书第2版的面世距初版时间已有20年之久．新版进行了大幅度修订，加入200多页新材料，许多章节有了重大变更，并增加了大量新的例子与练习．但是，本书的宗旨没有改变．下面三段话引自第1版前言，这些文字至今仍是适用的．
　这是指英文原书。——编辑注当代数学发展最快的领域可能就是组合数学了．它之所以发展快速，一个主要原因是它在计算机科学、通信、交通运输、遗传学、实验设计和排程等方面的广泛应用．因此，本书将从应用的观点向读者介绍组合数学的工具．
　　组合数学的发展是同计算机的发展齐头并进的．当今的高速计算机使得各领域中实际组合问题的求解成为可能，而这些问题在不久以前还是无法解决的．这种情况增强了研究组合问题求解方法的重要性．与此同时，计算机科学的发展本身又带来了大量具有挑战性的组合问题．因此，我们很难把组合数学和计算技术割裂开来．读者将会看到本书中对计算技术的强调，我们会经常采用计算机科学中的大量应用实例，频繁讨论算法，等等．另一方面，我们认为：组合数学在大量学科中有着广阔的应用前景，我们强调的重点是应用的多样性，而不限于某一方面．
　　本书选取的数学题材中，许多是快速发展的组合数学教科书中相对而言称为标准的内容．另一部分题材的选择，或者来自当前的研究文献，或者由于其学科应用价值而被选用．我们相信，本书在对应用的广泛讨论方面是与众不同的．书中有若干完整的小节专门介绍这样的应用，例如开关函数，使用酶揭示未知的RNA链，信息检索中的搜索与排序，错误校正码的构造，化学成分的计算，选举中的势力预测以及斐波那契数的应用．还有一些小节介绍与卷积有关的递推的应用、欧拉链的应用以及生成函数的应用等，这在许多教材中是没有的．
　　第2版中的新内容
　　本书之所以受到欢迎，大部分原因在于它引用了最新文献和各种实际应用．推动着组合数学发展的应用仍然在不断扩展，尤其是在自然科学和社会科学中．在第2版中，许多新应用更是来自计算机科学和生物学．在增加应用题材的同时，我们也增加了某些新的主题，删去了一些特殊的内容，改变了组织结构，并对例子、练习和参考文献也做了改进与更新．
　　下面说明第2版中所做的某些主要修改．
　　第1章：增加了有关列表着色的新材料，扩充了对州立法会议日程安排的讨论．列表着色问题在书中许多地方还会出现．
　　第2章：在第1版中，216节仅限于讨论生成排列的算法方法，第2版现在补充了大量材料，并分成几个小节．218节介绍“好算法”的概念和NP完全问题，进行了大幅度改写和更新．此外，还添加了有关“鸽巢原理”的新章节．讨论拉姆齐理论的小节是由第1版81节的材料和82节的部分材料合成的．另外，我们还增加了讨论排列之间的倒位距离和进化论生物学中的突变问题的内容．
　　第3章：在33节中增加了图着色问题的一小节，着重讨论图着色的扩展，例如多重着色和T着色．这类着色问题是由现实应用引起的，例如移动电话问题、交通灯切换和信道分配．此外，在本章中我们还增加了物种进化树重构的内容．对于第1版第8章有关拉姆齐理论的许多材料中没有写进第2章的部分，已改写为新的一节．
第4章：这一章是全新的．内容包括二元关系的定义及其与有向图的联系，用有向图和关系引入的顺序以及对线性序和弱序的处理，偏序、线性扩展和维数，链和可比较图，格，布尔代数，开关函数和门网络．该章紧密结合应用来讨论，其中涉及信息论、效用理论、搜索与排序以及诸如开关函数这样一些较早的应用．这一章包含的某些应用在组合数学的文献中没有受到广泛关注，如优先选择、搜索引擎、杂交顺序和心理物理量表法等．基于该章中的概念的许多例子也出现在以后各章中．第4章涉及的范围可以一直延续到第11章之后．
　　第5章：在第1版中这是第4章．前面几章引入的许多新概念与例子在这一章又重新出现，例如第4章的弱序和第3章的列表着色．
　　第6章：这是第1版中的第5章．该章增加了有关DNA序列对位的新材料，作为排列的“转置平均值”的内容．
　　第7章：这是第1版中的第6章．该章增加了有关密码技术和整数因子分解的新素材（在本书后面还要提到）．
　　第1版原第8章：这一章已经被删去，其中的重要材料加进第2章，而其余的材料已纳入书中其他章节．
　　第8章：这是第1版中的第7章．该章中新增加了一些例子，这些例子以第4章中的概念（如弱序）为基础．同时，该章中还增加了一小节，讨论图的自同构，并在该章多处地方提到．
　　第9章：该章增加了讨论正交阵列和密码技术的一节，内容涉及识别码和秘密分享．与此同时，该章还讨论了模算术与RSA密码系统之间的联系，以及秘密分享应用的一个可求解设计的内容．此外，该章关于“组群测试”的新内容涉及几个应用，其中包括次品鉴别、疾病筛查、基因组图谱测绘和卫星通信．
　　第10章：有关“合意解码”的小节是新增的，这同寻找分子序列中的蛋白质有关，同时加入了涉及光盘错误校正码的内容．关于“判读”DNA产生蛋白质的材料也是新增加的．
　　第11章：在112节中增加了讨论单行线问题的几小节．这些新的内容涉及有关广场取向和栅格的最新结果，分别反映不同城市类型的需要．该章还增加了关于测试巨大图的连通性问题的内容，这类问题出现在与电信业务量和网上数据有关的最新应用中．此外，该章还包括关于DNA杂交顺序的内容．
　　第12章：这一章用若干新的例子解释概念，包括天花疫苗接种、音响系统和石油钻井的例子．我们写了新的一节讨论稳定婚姻问题及其许多最新的应用，包括医院实习医生分配等．第1版第13章中有关最大权匹配的内容已移至该章中．
　　第13章：我们引入有关门格定理的新内容．该章还收入许多新的实例，讨论诸如建筑物疏散、聚类和数据挖掘以及分布式计算等问题．
　　保留的特点
　　尽管第2版对第1版做了重大修改，但仍然突出了使本书具有独特价值的那些特点．
　　 强调来自不同领域中的应用，把这些应用作为本来的主题而不只是一些孤立的例子，并且从最新文献中寻找应用．
　 许多例子在书中反复出现，特别是那些与新旧主题都有联系的例子．
　 强调通过不同的练习求解问题，用这些练习检测对常规概念掌握的程度，引入新的概念和应用，或者试图对读者提出应用现有组合数学技术的挑战．本书依然坚持这样一个原则，即学习组合数学的最佳方式是通过求解问题学习，实际上这也是学习任何一门数学的最佳方式．
　把不同难度的主题组合在一起，再加以详细的注释，使本书可以在各种不同层次的课程中使用．
　本书的组织方式允许读者按各种不同的顺序使用其中的题材，这一方面反映出组合数学中主题的某种独立性，同时这样灵活的方式又使各主题相得益彰，便于读者学习．
　　本书的组织方式
　　本书分为四个部分．第一部分包括第2、3、4章，介绍组合数学中使用的基本工具及其应用，其中引入基本计数规则以及图论与关系中使用的工具．其余三部分围绕组合数学的三个基本问题（计数问题、存在问题和优化问题）组织．这些问题在第1章中讨论．本书第二部分涉及处理计数问题的更高级工具，其中包括生成函数、递推关系、容斥原理以及波利亚理论．第三部分涉及解的存在问题，其中讨论组合设计、编码理论和图论中的特殊问题．这也是有关图论和网络的连续三章（第11章至第13章）的开始，并作为图算法的导论．第四部分讨论组合优化，通过对图和网络的连续研究说明各种基本思想．这部分从过渡性的匹配与覆盖一章开始，其中又以存在问题开头，以优化问题结束．第四部分最后讨论图和网络的优化问题．将本书分为四个部分的做法带有某种主观性，因为书中的许多主题涉及组合数学的若干方面，例如某些主题既包括存在问题，又包括优化问题．然而，对于庞大的现代组合学题材，把本书分成四个部分看起来又是很合理的．
　　预备知识
　　本书可以在不同层次的课程中使用．本书大部分内容是针对主修和非主修数学和计算机科学专业的低年级和高年级学生编写的．本书也适用于具有足够数学基础的大学二年级学生（书中已清晰地指明了在入门课程中可以省略的题材）．另一方面，书中包含足够的材料，能以一种快速的进度用于具有难度的研究生课程．作为本科课程的教材，本书已在拉特格大学中使用过，选课的大部分学生来自数学系和计算机科学系，其余的学生来自商学、经济学、生物学和心理学系．在狄克森学院，书中的材料已在主修数学的低年级或高年级的学生中使用过．这些课程以及本书的预备知识（包括熟悉函数和集合），至少可以从微积分课程中获得．第5章和第6章要用到无穷序列和无穷级数（其实第6章大部分只用到无穷序列的基本性质，并不需要极限的概念）．这里无需了解微积分中的其他传统的主题．但是，从微积分这样的课程中获得数学上的素质训练则是很必要的．此外，读者需要了解某些线性代数的工具，特别是熟悉矩阵运算．我们还假定读者了解数学归纳法（有一些教师会在课程的早期阶段复习数学归纳法，并快速复习集合的知识）．书中少数可选读的几节需要用到本书所述以外的概率知识．另有几节介绍近世代数的内容，例如群和有限域．上述这些节是自足的，但是对于没有足够基础的学生而言，这样的进度可能过快．
　　算法
　　本书在很多部分把重点放在算法上．由于组合数学日益用于研究精确和有效求解复杂问题的过程，以及组合数学和计算机科学如此紧密的结合，这样做是不可避免的．我们的目标是引入算法的概念并介绍一些重要的算法实例．我们在讨论大部分的算法时，都采用一种相对形式化的方式．这种方式很少去揭示算法的概念以及如何描述算法．主要目标在于提出算法的基本思想，而不试图以最简洁或适合计算机的形式描述算法．有人不同意用这种方法介绍算法．我们的观点则是不能用组合数学的课程代替算法的学习．计算机科学系的学生需要学习一门单独的算法课程，其中应包括对实现所述算法的数据结构的讨论．然而，学习组合数学的全体学生需要接受算法的思想，具备算法的思维方式，这种思维方式对于本学科而言是重要的也是基本的．我们认识到，我们对如何介绍算法的折中方案并不能使所有的人满意．但是这里应当指出，对于具有计算机背景的学生来说，应完成书中那些有趣的且重要的练习，把其中非形式化的算法转换成更精确的计算机算法甚至是计算机程序．
　　例子和应用所起的作用
　　书中的各种应用起了很大作用，使本书在众多的组合数学书籍中独树一帜．作者建议教师对应用进行挑选，或把它们作为课外阅读材料．书中的许多应用是用例子的形式介绍的，并在全书中重复展现．无论对教师或是学生而言，都不必成为书中不同实例和各个小节所述的应用领域的专家．应用和例子多半是自足的，倘若不是这种情况，也很容易通过因特网上的相关搜索获得对应用的理解．
　　组合数学同计算机科学之间的联系极其重要，在此无需特别强调．
　　本书中取材于生物科学的例子非常重要．我们把重点放在这样的例子上是基于下述观察：生物科学和数学科学之间的联系正在以极快的速度加强，数学和计算机科学的方法在现代生物学中扮演了且仍在扮演着重要的角色，例如，在“人类基因工程”和疾病传播建模中.让数学工作者认识到专业领域需要像组合数学这样的数学方法已变得越来越重要．此外，已经有越来越多的学校开设数学和生物学相结合的交叉课程．
　　数学与社会科学之间的联系程度也在迅速增加，尽管其进展速度不如数学同生物科学的联系程度．现在，计算机科学的工具和数学建模方法已应用于处理日益复杂的社会科学问题．所以，我们介绍了出现在社会科学方面的种种应用，重点是决策和投票问题．
　　数学证明
　　作出证明是数学区别于其他学科的一个重要方面．组合数学可能是一种非常好的学习数学证明的途径，通过它可以向学生介绍数学证明的概念，并教会他们如何写出完善的证明．有些学校以组合数学作为数学证明课程的入门课程．但这不是我们写这本书的目的．虽然使用本书的教师应把证明包括在内，但我们却倾向于把证明处理成略带非形式化的，而非把重点放在如何写证明上．我们将书中许多比较难的证明加上了星号，表示是可选的．
　　练习
　　本书的练习处于主角的地位．练习用于检验对常规概念掌握的程度，引入新的概念和应用，并试图作为对读者运用书中既有的组合技术提出的挑战．组合数学的本质在于，越是通晓它，越能应付种种难题，这也是大部分数学的本质．在本书中，我们尽量收入各种实用性和理论性的练习以及具有不同难度的练习．
　　在不同情况下使用本书的方法
　　本书可适用于不同层次的不同课程．我们已在几门课程中使用书中的材料，特别是在名为“组合数学”的一学期课程和名为“应用图论”的一学期课程中使用．对低年级和高年级讲授的组合数学课程，用第1、2、3、5、6、7、9、10章的大部分材料，略去正文中由脚注指明的各节（通常为证明）．在拉特格大学一门快进度的一年级研究生课程中，Fred Roberts把课程的重点放在证明上，此外还在课程中融入许多可选的章节，同时采用第8章或第12章的材料．无论在本科生或研究生的课程中，教师都应该用第8章或第11章以及第12章和第13章的部分内容代替第9章和第10章．在不单独开设图论课程的情况下，特别推荐把第11章包括在内．类似地，如果不开设运筹学课程，特别推荐把第13章的部分内容包括在内．在拉特格大学，对本科生和研究生分别开设的课程，讲授第11章至第13章的大部分材料．
　　其他的一学期或暑期课程应按照本书的材料设计，因为大多数章是相对独立的（请参考下面的讨论）．在拉特格大学，应用图论课程是围绕第3章和第11章讲授的，并从书中的其余部分（第4、12和13章）及别的地方补充图论的题材（需要快速讲授21节至27节，或者还有218节）．第3、11、12、13章也适于在一门介绍图算法的课程或者名为“图与网络”的课程中讲授．全书非常适合作为现代组合数学及其应用引论的一学年教材．对于学习过组合数学的人来说，若要将重点放在组合数学的应用上，可以把书中有关应用的小节和例子包括在内．
　　本书可以用于大学二年级的一学期或暑期课程．这样的课程应包含第1章至第3章，跳过第4章和第5章，然后选用第6章的61节和62节，以及第7章和第11章的部分内容，带有星号的各节和大多数证明应予省略．其他的题材可由教师酌情增加．
　　主题之间的相关性和使用本书题材的顺序
　　在组织任何课程时，希望教师了解对题材相对独立性的说明．在讲授组合数学引论的主题时，没有被普遍接受的顺序，对这样的引论应包含哪些主题也没有一致的看法．我们在写本书时力求采用这样一种方法，使各章的内容相对独立，并能按不同的顺序讲授．
　　第2章是本书的基础部分，介绍全书用到的基本计数规则．第3章只包含足以进入到主题的图论知识，它的重点是用以说明第2章提出的基本计数规则的那些图论题材．第3章引入的概念在全书各处都会涉及，尤其是在第4、11、12和13章．教师可以把本书用于一学期或暑期的组合数学课程，不讲授第3章．但是，我们建议至少应把图着色（33节和34节）的材料包含在内．除第3章外，主要依赖关系是：第4章依赖第3章；第6章62节之后的内容依赖第5章；第7章引用第3章和第6章中的几个例子；第11章至第13章依赖第3章；105节依赖第9章；第12章中提到的几个概念在1338节中会用到．
　　处于快速发展时期的组合数学
　　最后应该强调，组合数学是一门快速发展的学科，它的方法正在迅速建立，它的应用正在迅速扩展．本书介绍的许多主题同研究工作的前沿紧密相关．它是一门可以把新手很快带到前沿领域的典型学科．我们尽力收集组合数学及其应用的参考文献，以便使有兴趣的读者能更深入地钻研本书所讨论的主题．
　　致谢
　　作者之一Fred Roberts于1976年开始第1版的写作，当时为拉特格大学组合数学的本科课程写了一部分手稿．经过几年时间的修改和增补，本书正式用于组合数学课程和前述的其他课程，Barry Tesman也这样使用本书．同时还有很多人也同样把本书作为他们的教材，并反馈了大量意见，这使作者受益匪浅．作者特别要感谢下列使用者提出的非常有价值的评论：Midge Cozzens,在东北大学使用第1版的草稿；Fred Hoffman，在佛罗里达大西洋大学使用；Doug West,在普林斯顿大学使用；Garth Isaak，在Lehigh大学使用第2版的草稿;Buck McMorris，在伊利诺伊理工学院使用第2版的草稿．
　　我们特别感谢现在和过去的学生们，他们在本书两个版本的准备阶段以多种方式提供了帮助，包括校对、核对练习、检查各种错误，此外他们还提出了各种宝贵的意见．Fred Roberts对Midge Cozzens、Shelly Leibowitz、Bob Opsut、Arundhati RayChaudhuri、Sam Rosenbaum和Jeff Steif等人的帮助表示感谢．Barry Tesman对Kathy Clawson和John Costango的帮助表示感谢．
　　我们收到许多人对本书的评论．我们要特别感谢以下人士，他们在审阅第1版的各个阶段和其他时间曾做出极其有价值的评论：John Cozzens、Paul Duvall、Marty Golumbic、Fred Hoffman、Steve Maurer、Ronald Mullin、Robert Tarjan、Tom Trotter以及Alan Tucker．在准备第2版的时候，我们收到了Steve Maurer对第1版提供的非常有用的评论．Jeff Dinitz对第9章和第10章的草稿提出了具体的意见．关于第2版，我们收到审阅者很有价值的评论，他们是：Edward Allen、Martin Billik、John Elwin、Rodney WForcade、Kendra Killpatrick、Joachim Rosenthal、SungYell Song、Vladimir Tonchev和CunQuan Zhang．尽管我们收到大量的意见和评论，但书中的疏误仍然在所难免,我们会对此负责．
　　本书第1版的成书过程，几经录入、复制和剪贴（剪刀加浆糊）．在这期间，Fred Roberts得到Lynn Braun、Carol Brouillard、Mary Anne Jablonski、Kathy King、Annette Roselli和Dotty Westgate的莫大帮助．由于出版业务的显著变化，第2版又由Barry Tesman进行录入和剪贴（电子编辑）等工作．由于第1版没有电子副本，其扫描任务是由Barry Tesman以前的学生Jennifer Becker完成的．在此，Barry Tesman对她承担这一艰巨任务表示感谢，同时还要感谢狄克森学院数学与计算机科学系的人员提供的支持和所做的贡献．
　　两位作者在这里还要感谢家人的支持．写作意味着要占用大部分的家庭时间：为了校对要停用电话，为了写作要取消旅游，为了某处改进要牺牲休息时间．我们的家人对此给予极大的帮助和理解．Fred Roberts感谢已故双亲Louis和Frances Roberts的关爱与支持；感谢已故岳母Lily Marcus在技术上和其他方面提供的帮助；感谢妻子Helen的帮助，虽然她看上去就像是一位因丈夫写书而“独守空房的女子”，但她的帮助不只限于一如既往的支持、劝导和鼓励，同时她也是本书其中一章的合作者，在书中引入了她在教学中使用的各种题材和例子，这些材料遍及书中各处；最后还要感谢Sarah和David，在写第1版时，孩子们的贡献就是保持稳定良好的情绪，更为重要的是在成年以后，他们以其他方式对本书做出了贡献，比如Sarah介绍的公共卫生的理念目前已反映在本书中，David对计算机科学的许多方面做出了解释，对此在本书的一处脚注中对他表示感谢．Barry Tesman感谢双亲Shirley和Harvey Tesman的关爱和支持；感谢妻子Johanna，在这项任务中，她是默默的同伴,而在过去的20年岁月中，她却是活跃的伴侣和朋友；最后要感谢Emma和Lucy，因为他们是最可爱的．

　　Fred SRoberts
　　froberts@dimacsrutgersedu
　　Barry Tesman
　　tesman@dickinsonedu

本书写作方法非常出色，第2版保持了前一版的高质量，并进行了大量更新。书中内容叙述非常翔实，便于学生理解，例子讲解生动并富有启发性，而且所涉及的应用范围之广更是罕见。
　　——John Elwin，圣迭戈州立大学

　　本书介绍组合数学的基本知识和应用，涉及计算机科学、生物学、化学、心理学及基因工程等前沿学科中的最新应用，应用层面非常宽泛。本书布局精巧、内容翔实，对题材的讨论深入浅出，简明扼要，包含了很多高级的组合数学技术与方法。全书分为四个部分：第一部分介绍组合数学的基本工具，第二部分介绍计数问题，第三部分讲述组合数学求解中的存在问题，第四部分讨论优化问题。
　　本书第1版曾被国外多所大学采纳为教材，这一版根据最新技术发展进行了大量修改，书中包含大量出色的实例和练习，可作为高等院校数学专业和计算机科学专业“组合数学”课程的教材。

Fred S.Roberts;Barry Tesman：Fred S.Roberts: 美国拉特格大学数学系教授，研究方向包括数学模型在社会学、行为学、生物学、环境科学以及传媒和交通方面的应用，图论与组合数学，测度论等。
Barry Tesman: 于美国拉特格大学获得数学专业博士学位，现任美国宾夕法尼亚州狄克森学院数学与计算机科学系副教授。他的研究方向包括图论、组合数学和测度论。

冯速：暂无简介

本书以组合数学的实际应用为背景，非常全面地讲述了组合数学的基本知识和基本问题，以及这些知识在计算机科学、密码学、政治经济学、生物学、医学、遗传学等各个领域的实际应用．
　　本书分四个部分．第一部分讲述组合数学的基本工具，而其余三个部分分别讲述组合数学的三个基本问题：计数问题、存在问题和优化问题．各章以实际应用为例，引出该章的主要课题，然后对前后关联的知识点逐步展开讨论，在讨论中又提出更多的示例，力图让读者掌握所讲述的思想并灵活运用相关的方法．另外，各节给出很多相关的练习，使读者能够检验所学知识，同时引入新概念和新应用，为读者灵活运用书中的组合技术提供素材．因此，本书的一大特点就是包含大量的实际例子及练习，其中许多例子和练习都来自于最新的文献．这些例子和练习前后呼应、反复出现，形成若干系列，可以看出经过了作者的精心筛选．
　　本书的另一个特点是强调算法．当今计算机的快速发展和各种算法的开发是促进组合数学快速发展和广泛应用的主要动力之一，而组合数学的快速发展同样促进了计算机理论的发展及计算机在各个领域的广泛应用．所以，组合数学与计算机科学之间已经形成了密不可分的关系，组合数学是计算机科学——特别是计算机算法的基础．现在，组合数学已经成为多数大学计算机专业研究生的必修课程．
　　本书的第三个特点是，不仅给出了绝大多数结果的严密证明，而且不拘泥于通常教科书所用的概念和结果，对一些概念和结果进行了扩展．
　　本书可以作为计算机专业和数学专业高年级本科生或研究生的教材，也可以作为相关科研人员的参考书．不满足于“离散数学”课程所学内容的学生可以通过本书继续自学，而本书各章后的参考文献则为希望继续深入学习、了解科研前沿及应用前沿的读者提供了参考．
　　在翻译本书时，我们遇到了许多不同专业的术语．我们力图使术语简单、易懂，一些术语没有采用数学专业的说法，而是采用计算机科学专业的说法．对于中文特别难以反映其本质内容的术语，我们采取了不译的做法．由于书中涉及应用的多样性和译者的水平所限，难免有不当之处，敬请读者批评指正．

　　译者
　　于北京师范大学

译者序
前言
记号
第1章什么是组合数学
11组合数学的三个问题
12组合数学的历史和应用
练习
参考文献
第一部分组合数学的基本工具
第2章基本计数规则
21乘法规则
22加法规则
23排列
24计算的复杂度
25r排列
26子集
27r组合
28概率
29放回取样
210分装问题
2101分装问题的类型
2102情况1：可区分球和可区分
盒子
2103情况2：不可区分球和可区分
盒子
2104情况3：可区分球和不可区分
盒子
2105情况4：不可区分球和不可区分
盒子
2106例子
211多项式系数
2111带有特殊分配的分装问题
2112带有不可区分对象类的排列
212酶的完全分解
213再论带有不可区分对象类的排列
214二项式展开
215简单游戏中的势力
2151简单游戏的例子
2152ShapleyShubik势力指数
2153联合国安理会
2154两院制立法机构
2155成本分摊
2156特征函数
216生成排列和组合
2161生成排列的算法
2162生成集合子集的算法
2163生成组合的算法
217排列间的倒位距离和突变研究
218好算法
2181渐近分析
2182NP完全问题
219鸽巢原理及其扩展
2191最简单的鸽巢原理
2192鸽巢原理的扩展和应用
2193拉姆齐数
附加练习
参考文献
第3章图论概述
31基本概念
311一些例子
312有向图和图的定义
313标签有向图和同构问题
32连通性
321有向图中的可达性
322图中的连通性
323强连通有向图和连通图
324子图
325连通分支
33图着色及其应用
331一些应用
332平面图
333计算色数
3342可着色图
335图着色变形
34色多项式
341定义和例子
342化简定理
343色多项式的性质
35树
351树的定义和例子
352树的性质
353定理315的证明
354支撑树
355定理316的证明和相关结果
356化学键和树的数量
357种系发生树的重建
36根树的应用
361定义
362搜索树
363定理324的证明
364排序
365完美种系发生问题
37计算机中图的表示
38再论拉姆齐数
参考文献
第4章关系
41关系
411二元关系
412关系的性质/有向图中的
模式
42顺序关系及其变形
421定义顺序关系的概念
422顺序关系的图表示
423线性序
424弱序
425稳定婚姻
43偏序的线性扩展
431线性扩展和维数
432链和反链
433区间顺序
44格和布尔代数
441格
442布尔代数
参考文献
第二部分计数问题
第5章生成函数及其应用
51生成函数的例子
511幂级数
512生成函数
52生成函数的运算
53计数的应用
531取样问题
532关于分装问题的一个注释
54二项式定理
55指数生成函数和排列的生成函数
551指数生成函数的定义
552排列计数的应用
553可区分球到不可区分盒子的
分配
56概率生成函数
57Coleman和 Banzhaf的势力指数
参考文献
第6章递推关系
61一些例子
611一些简单的递推关系
612斐波那契数及其应用
613错位排列
614涉及多个序列的递推关系
62特征根方法
621不同根的情况
622第k个斐波那契数的计算
623重根的情况
63使用生成函数求解递推关系
631方法
632错位排列
633生成函数的联立方程
64一些涉及卷积的递推关系
641简单有序根树的数量
642计算机中数的序列相乘的方法
643RNA中的二级结构
644由苯环所构建的有机化合物
参考文献
第7章容斥原理
71容斥原理及其应用
711一些简单例子
712定理71的证明
713素数、密码学和筛
714概率情况
715可区分球和盒子的分装问题
716色多项式
717错位排列
718计数组合
719车多项式
72正好有m个性质的对象数量
721主要结果及其应用
722定理74和定理75的证明
参考文献
第8章波利亚计数理论
81等价关系
811不同的构形与数据库
812等价关系的定义
813等价类
82排列群
821排列群的定义
822排列群衍生的等价关系
823图的自同构
83伯恩赛德引理
831伯恩赛德引理的陈述
832伯恩赛德引理的证明
84不同的着色
841着色的定义
842等价着色
843自同构下的图着色等价
844开关函数的情况
85循环指标
851作为循环积的排列
852波利亚定理的特殊情况
853再论自同构下的图着色等价
854开关函数的情况
855排列群的循环指标
856定理86的证明
86波利亚定理
861着色的目录
862计算模式目录
863开关函数的情况
864波利亚定理的证明
参考文献
第三部分存在问题
第9章组合设计
91区组设计
92拉丁方
921一些例子
922正交拉丁方
923有关正交族的存在结果
924定理93的证明
925正交阵列及其在密码学中的
应用
93有限域与拉丁方族
931模算术
932模算术和RSA密码系统
933有限域GF（pk）
934当n是素数幂时，n×n拉丁方的
完全正交族的构造
935当n=pk时，完全正交族的
构造的证明
94平衡不完全区组设计
941（b，v，r，k，λ）设计
942（b，v，r，k，λ）设计存在的
必要条件
943费希尔不等式的证明
944可分解设计
945施泰纳三元系统
946对称平衡不完全区组设计
947从已有的设计构建新的
（b，v，r，k，λ）设计
948组群测试及其应用
949施泰纳系统和国家彩票
95有限射影平面
951基本性质
952射影平面、拉丁方和（v，k，λ）
设计
参考文献
第10章编码理论
101信息传输
102编码与解码
103错误校正码
1031错误校正和汉明距离
1032汉明界
1033错误的概率
1034合意解码及其与寻找分子序列
中的模式之间的关系
104线性代码
1041生成矩阵
1042使用线性代码的错误校正
1043汉明码
105运用区组设计确定错误校正码
1051阿达马码
1052构建阿达马设计
1053最丰富的（n，d）代码
1054一些应用
参考文献
第11章图论中的存在问题
111深度优先搜索：连通性测试
1111深度优先搜索
1112深度优先搜索的计算复杂度
1113深度优先搜索算法的形式
描述
1114巨大图的连通性测试
112单行线问题
1121Robbin定理
1122深度优先搜索算法
1123高效单行线分配
1124栅格的高效单行线分配
1125环状城市和互联网中的通信
113欧拉链和欧拉路径
1131哥尼斯堡桥问题
1132寻找欧拉闭链的算法
1133关于欧拉链和欧拉路径的更多
结果
114欧拉链和欧拉路径的应用
1141“中国邮差”问题
1142计算机绘图
1143街道清扫
1144寻找未知的RNA/DNA链
1145编码应用
1146德布鲁因序列和电信
115哈密顿链和哈密顿路径
1151定义
1152图存在哈密顿回路的充分
条件
1153有向图存在哈密顿循环的
充分条件
116哈密顿链和哈密顿路径的应用
1161锦标赛
1162拓扑排序
1163运筹学中的调度问题
1164设备设计
1165杂交顺序
参考文献
第四部分组合优化
第12章匹配与覆盖
121一些匹配问题
122一些存在结果：二部匹配和相异
表示系统
1221二部匹配
1222相异表示系统
123任意图的完美匹配的存在性
124最大匹配和最小覆盖
1241顶点覆盖
1242边覆盖
125寻找最大匹配
1251M增广链
1252定理127的证明
1253寻找最大匹配的算法
126匹配尽可能多X的元素
127最大权匹配
1271再论“中国邮差”问题
1272最优分配问题（最大权匹配）
的算法
128稳定匹配
1281GaleShapley算法
1282稳定匹配的数量
1283稳定匹配的结构
1284稳定婚姻的扩展
参考文献
第13章图和网络的优化问题
131最小支撑树
1311 Kruskal算法
1312定理131的证明
1313Prim算法
132最短路径问题
1321问题
1322Dijkstra算法
1323对调度问题的应用
133网络流
1331最大流问题
1332分割
1333一个不完善的最大流算法
1334增广链
1335最大流算法
1336寻找增广链的标记过程
1337最大流算法的复杂度
1338再论匹配
1339门格定理
134最小成本流问题
参考文献
人名索引
主题索引