组合数学原书第5版 组合数学(原书第5版)

2017/5/29 19:27:45

在这一新版本中,我做了一些细微的改变,具体概括如下: 在第1章,新增加了一节(1.6节),讨论相互重叠圆的问题,用来具体说明后面章节中所讨论的某些计数问题。之前,这一节的相关内容出现在第7章。 第1章中原来关于切割立方体的一节已经删除,但是相关内容放在练习题中。

组合数学原书第5版 组合数学(原书第5版)

之前版本中的第2章(鸽巢原理)改成了第3章。之前版本中关于排列和组合的第3章改成了第2章。帕斯卡公式在之前的版本中第一次出现在第5章中,现在出现在第2章中。

组合数学原书第5版 组合数学(原书第5版)

另外,为了清晰起见,在关于集合的论述中我们不再强调“组合”这一术语,而启用了一个本质上等价的术语“子集”。然而,在多重集合的情况下,我们继续使用“组合”,而不使用在我们看来易产生混淆的术语“多重子集”。

组合数学原书第5版 组合数学(原书第5版)

此版本的第2章包含一节(2.6节)有限概率简介。 此版本的第3章包含Ramsey定理的证明。 第7章的变化比较大,其中生成函数和指数生成函数移到了本章靠前部分(7.2节和7.3节),成为更核心的内容。

组合数学原书第5版 组合数学(原书第5版)

分拆数这一节(8.3节)做了扩展。 之前版本中关于二分图匹配的第9章做了根本的改变。现在的第9章是新插入的章节,讨论的是相异代表系(SDR)的问题,包括婚姻和稳定婚姻匹配问题,而不再讨论二分图。

组合数学原书第5版 组合数学(原书第5版)

第9章这样改动的结果是,介绍图论的章节(第11章)不再假设先前已介绍过二分图的知识。 再论图论一章(之前版本中的第13章)现在变成了第12章。在本章中,新增加了关于图的匹配数一节(12.

组合数学原书第5版 组合数学(原书第5版)

5节),在这一节中,第9章中SDR的基础结果被用于二分图。 有向图和网络这一章(之前是第12章)现在是第13章。它新增加了一节,回顾了二分图的匹配,其中有些相关内容出现在之前版本的第9章中。 对于第5版,除了以上列出的这些变化之外,还更正了我注意到的所有印刷错误;增加了少量的说明;改动了一些顺序,使前后文更加通顺;另外还增加了练习题,第5版中共有700道练习题。

组合数学原书第5版 组合数学(原书第5版)

根据多年来很多读者的评论,这本书似乎已经通过了时间的检验。

因此,我总是犹豫不决而迟迟没有做出更多的改变,也没有增加更多的新话题。我不希望一本书“太长”(这一前言也不会太长),也不愿意让这本书迎合每个人的癖好。不过,我的确做了上述细节上的改变,相信这些改变会使这本书更加完善。

组合数学原书第5版 组合数学(原书第5版)

与之前各版本一样,这一版可以用于一到两个学期的本科生课程。第一个学期可以侧重计数,而第二个学期可以侧重图论和设计。也可以把相关内容合并在一起作为一个学期的课程,如讲解一些计数和图论知识,或者一些计数与设计理论知识,或者选择其他的组合搭配。

下面简要说明各章以及它们之间的相互关系。 第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