组合数学（原书第5版·典藏版） [美]理查德·A.布鲁迪_[美]理查德·A.布鲁迪_9787111748861

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

前　言

在这一新版本中，我做了一些细微的改变，具体概括如下:
在第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章讨论的是鸽巢原理，这一章至少应该做简单介绍。但是,需要注意的是，后面没有用到一些较难的鸽巢原理应用以及关于Remsey定理那一节的内容。第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章之后，我给出了本书一些练习题的答案和提示。少数练习题旁边标上了“*” 号，表明它们有相当的挑战性。每一个证明结束及每一个例子结束处都标有 “□”号予以明示。
很难评说学习这本书所需要的前提条件。与其他教科书一样，高度激发学生的热情、提起学生的兴趣是很有用的，另外还需要指导教师的热情投入。也许这些前提条件应该这样描述为好:有完备的数学知识。即成功地学习了数学分析相关内容以及线性代数的初等课程。本书对数学分析使用

你还可能感兴趣

我要评论