组合数学（英文版·第4版）[按需印刷]

　　 本书是系统阐述组合数学基础、理论、方法和实例的优秀教材，出版近30年来多次改版，被MIT、哥伦比亚大学、UIUC、威斯康星大学等众多国外高校采用，对国内外组合数学教学产生了较大影响，也是相关学科的主要参考文献之一。
　　 本书侧重于组合数学的概念和思想，包括鸽巢原理、计数技术、排列组合、Polya计数法、二项式系数、容斥原理、生成函数和递推关系以及组合结构(匹配、实验设计、图)等，深入浅出地表达了作者对该领域全面和深刻的理解，介绍了历史上源于数学游戏和娱乐的大量实例，其中对Polya计数、Burnside定理等的完美处理使得不熟悉群论的学生也能够读懂。除包含第3版中的内容外，本版又进行了更新，增加了莫比乌斯反演(作为容斥原理的推广)、格路径、Schroder数等内容。此外，各章均包含大量练习题，并在书末给出了参考答案与提示。
　　

前言
chapter 1. what is combinatorics?
1.1 example. perfect covers of chessboards
1.2 example. cutting a cube
1.3 example. magic squares
1.4 example. the 4-color problem
1.5 example. the problem of the 36 officers
1.6 example. shortest-route problem
1.7 example. the game of nim
1.8 exercises
chapter 2. the pigeonhole principle
2.1 pigeonhole principle: simple form
2.2 pigeonhole principle: strong form
2.3 a theorem of ramsey
2.4 exercises
chapter 3. permutations and combinations
3.1 four basic counting principles
3.2 permutations of sets
3.3 combinations of sets
3.4 permutations of multisets

　　 在第3版的前言中曾经提到如何重写某些章节以及如何添加某些新的材料和练习。从第2版到第3版一些主要的变化如下：
　　 第4章添加了偏序和等价关系的介绍。
　　 第5章增加了再论偏序集一节，其中证明了Dilworth定理及其对偶。
　　 第8章加写了正整数分拆的新内容。
　　 第11章是本书讨论图论的第一章，其中，树被定义为移去任意一边后都不再连通的连通图，并删掉了介绍有向图的一节。
　　 第12章是新的一章，讨论有向图和网络。这一章包括Ford和Fulkerson的最大流最小割定理的证明，由此，第9章的Menger定理和Konig定理作为推论而导出。
　　 第2版第12章讨论的图论中基本的数构成第3版的第13章。Polya计数法原先在第13章，后来改成第14章。
　　 第4版修正了我所知道的所有排印错误，从语言上做了一些小的调整(包括在论述图论的各章中用"路径"代替"链")，插入某些零星内容，并增加了60多道新的具有挑战性的练习题。我不愿把这本书改变过多或是加入太多新的课题，也不喜欢有过多词汇的书籍(而本前言就没有太多的词汇)，不想陷进那样的陷阱。此外，本版添加两节新内容。第6章添加新的最后一节，论述莫比乌斯反演，作为容斥原理的推广。第8章新增了一节，论述格路径以及小Schroder数和大Schroder数。
　　 如同早期版本一样，可以使用本书作为一学期或两学期的本科课程。第一学期可侧重于计数法，而第二学期则侧重图论和设计。也可以合在--起作为一学期的课程，讨论某些计数法和图论，或者讨论一些计数法和设计理论。下面是对每章的简短评述和各章间相互关系的介绍：
　　 第1章是引论性的一章；我通常从这章选择一两个课题并最多花费两节课讲述这一章。第2章讨论鸽巢原理，至少应该以缩减的形式讨论。不过要注意，这对于后面鸽巢原理某些困难的应用以及Ramsey定理的理解却无济于事。第3章到第8章主要讨论计数技术和计数结果序列的某些性质。应该按顺序讨论它们。第4章涉及排列和组合的生成方法，还有上面提到的偏序和等价关系的介绍。然而，除第5章论述偏序集的那一节外，第4章后面各章基本上都与第4章无关。因此，第4章可以略去或压缩，甚至根本不讨论偏序集。第5章论述二项式系数的性质，第6章讨论容斥原理，论述莫比乌斯反演的新的一节在后面各章都用不到。第7章比较长，讨论递推关系的求解以及计数中生成函数的使用。第8章主要关于Catalan数、第一类和第二类Stifling数、分拆数以及小Schroder数和大Schroder数。后面各章与第8章无关。
　　 第9章讨论二分图中的匹配问题。虽然本书在介绍图之前引入了二分图，但本章与后面的图论各章基本上没有什么关系。除匹配理论对拉丁方的应用外，论述设计的第10章独立于本书其余部分。不过，在10．4节末尾用到第9章建立的匹配理论。第11章和第13章对图论进行了广泛的讨论，重点放在图论算法上。第12章涉及有向图和网络流。第14章处理在置换群作用下的计数问题，这里确实用到了先前许多的计数思想。除最后一个例子外，本章与图论和设计的各章无关。
　　 当教授本书一学期的课程时，我喜欢以论述P61ya计数法的第14章作为结束，这能够使我们解决许多计数问题，而这些问题用前面各章的方法是无法解决的。在第14章之后，给出了本书大约650道练习题中的部分解答和提示。一些练习旁边标有星号"*"，表明它们更具有挑战性。在证明的最后和例子的末尾均标有符号"口"以示结束。
　　 确定阅读本书的前提条件比较困难。如同所有想要作为教材的著作一样，高度激发学生的热情和兴趣是有帮助的。或许奉书更适合那些成功地学习过微积分和线性代数初等课程的读者。这里对微积分的使用很少，而涉及的线性代数也不多，因此对于不熟悉它的读者阅读本书也不应该有任何问题。
　　 自从第1版发行以来已经25年了，但本书仍然受到专业数学同行的欢迎，我很知足；
　　 非常感谢鼓励我修订第4版以及向我提供有益建议的许多专家：Russ Rowlett(坎裴尔北加州大学)，James Sellers(Penn州立大学)，Michael Buchner(新墨西哥大学)。正如第3版一样，我特别感谢Leroy F．Meyers(俄亥俄州立大学)和Tom Zaslavsky(SUNY系统Binghamton分校)，他们每位都向我提供了对第3版的广泛而详尽的建议。对于第4版，我得到了Nils Andersen(哥本哈根大学)、James Propp(威斯康星大学)和Louis Deatt(威斯康星大学)许多有用的建议，他们阅读了新版并对格路径的新的一节发表了看法。我希望本书继续反映我对组合数学的热爱以及我讲授这门课程的热情和讲授的方式。
　　 最后，再次感谢我亲爱的妻子Mona；是她给我的生活带来幸福、激情和勇气。
　　 理查德A．布鲁迪
　　 brualdi@math．wisc．edu