本书是系统阐述组合数学基础、理论、方法和实例的优秀教材，出版近30年来多次改版，被MIT、哥伦比亚大学、UIUC、威斯康星大学等众多国外高校采用，对国内外组合数学教学产生了较大影n向，也是相关学科的主要参考文献之一。 \r\n 本书侧重于组合数学的概念和思想，包括鸽巢原理、计数技术、排列组合、Polya计数法、二项式系数、容斥原理、生成函数和递推关系以及组合结构(匹配、实验设计、图)等，深入浅出地表达了作者对该领域全面和深刻的理解，介绍了历史上源于数学游戏和娱乐的大量实例，其中对Polya计数、Burnside定理等的完美处理使得不熟悉群论的学生也能够读懂。除包含第3版中的内容外，本版又进行了更新，增加了莫比乌斯反演(作为容斥原理的推广)、格路径、Schroder数等内容。此外，各章均包含大量练习题，并在书末给出了参考答案与提示。
出版者的话\r\n专家指导委员会\r\n译者序\r\n前言\r\n第1章 什么是组合数学\r\n 1.1 例:棋盘的完美覆盖\r\n 1.2 例:切割立方体\r\n 1.3 例:幻方\r\n 1.4 例:四色问题\r\n 1.5 例:36军官问题\r\n 1.6 例:最短路径问题\r\n 1.7 例:Nim取子游戏\r\n 1.8 练习题\r\n 第2章 鸽巢原理\r\n 2.1 鸽巢原理:简单形式\r\n 2.2 鸽巢原理:加强形式\r\n 2.3 Ramsey定理\r\n 2.4 练习题\r\n 第3章 排列与组合\r\n 3.1 四个基本的计数原理\r\n 3.2 集合的排列\r\n 3.3 集合的组合\r\n 3.4 多重集的排列\r\n 3.5 多重集的组合\r\n 3.6 练习题\r\n 第4章 生成排列和组合\r\n 4.1 生成排列\r\n 4.2 排列中的逆序\r\n 4.3 生成组合\r\n 4.4 生成r组合\r\n 4.5 偏序和等价关系\r\n 4.6 练习题\r\n 第5章 二项式系数\r\n 5.1 Rascal公式\r\n 5.2 二项式定理\r\n 5.3 一些恒等式\r\n 5.4 二项式系数的单峰性\r\n 5.5 多项式定理\r\n 5.6 牛顿二项式定理\r\n 5.7 再论偏序集\r\n 5.8 练习题\r\n 第6章 容斥原理及应用\r\n 6.1 容斥原理\r\n 6.2 具有重复的组合\r\n 6.3 错位排列\r\n 6.4 带有禁止位置的排列\r\n 6.5 另外的禁排位置问题\r\n 6.6 莫比乌斯反演\r\n 6.7 练习题\r\n 第7章 递推关系和生成函数\r\n 7.1 一些数列\r\n 7.2 线性齐次递推关系\r\n 7.3 非齐次递推关系\r\n 7.4 生成函数\r\n 7.5 递归和生成函数\r\n 7.6 一个几何的例子\r\n 7.7 指数生成函数\r\n 7.8 练习题\r\n 第8章 特殊计数序列\r\n 8.1 Catalan数\r\n 8.2 差分序列和Stirling数\r\n 8.3 分拆数\r\n 8.4 一个几何问题\r\n 8.5 格路径和Schrodr数\r\n 8.6 练习题\r\n 第9章 二分图中的匹配\r\n 9.1 一般问题表述\r\n 9.2 匹配\r\n 9.3 互异代表系统\r\n 9.4 稳定婚姻\r\n 9.5 练习题\r\n 第10章 组合设计\r\n 10.1 模运算\r\n 10.2 区组设计\r\n 10.3 Steiner三元系统\r\n 10.4 拉丁方\r\n 10.5 练习题\r\n 第11章 图论导引\r\n 11.1 基本性质\r\n 11.2 欧拉迹\r\n 11.3 Hamilton路径和Hamilton圈\r\n 11.4 二分多重图\r\n 11.5 树\r\n 11.6 Shsnnon开关游戏\r\n 11.7 再论树\r\n 11.8 练习题\r\n 第12章 有向图及网络\r\n 12.1 有向图\r\n 12.2 网络\r\n 12.3 练习题\r\n 第13章 再论图\r\n 第14章 Polya计数法\r\n练习题的答案与提示\r\n参考文献\r\n索引
本书着重于组合学思想的阐述, 包括对鸽巢原理. 计数技术. 排列与组合. Polya计数法. 二项式系数. 容斥原理. 生成函数与递推关系以及一些组合结构如匹配. 设计和图等的讨论. 第三版经过较大的修订, 添加了有关偏序集. Dilworth定理. 整数分拆和生成函数的新内容, 并重写了有关图论的各章. 第四版除改正了所发现的排印错误外, 又增加了6.6节墨比乌斯反演作为对容斥原理的推广和8.5节论述格路径和大. 小Schr?der数两节, 这两节与其后各章无关. 此外, 第四版还新补充了60多道练习题, 并在一些地方插入不多的零星内容.
在原著第四版的序言中, 作者比较详细地介绍了各章的内容和它们之间的关系, 谈到了使用本书伸缩性的授课方案以及作者讲授时的经验和偏好. 这对于我们深入了解本书的内容和结构以便将它作为教材恰当地使用是很有帮助的.
本书原著通俗流畅, 深入浅出. 生动灵活的写作风格反映作者对该领域的热情和作为课程讲授的乐趣. 书中对Polya计数定理的完美处理使得读者不必具备相关的群论知识.
在《组合数学》第四版, 我们几位译者的分工与第三版没有明显的变化. 能够在出版社热心关怀下及时地把它介绍给我国广大读者, 实在是我们的荣幸.
非常感谢卢开澄教授. 赵平女士和班春红同志对本书第三版的真诚帮助, 并感谢天津理工大学白苓副教授以及孙华副教授对第四版翻译工作的热情支持.
由于时间和水平的限制, 书中难免疏漏和错误, 我们期盼广大读者的批评与教正.
译者
2004年8月
Richard A.Brualdi 1964年于美国锡拉丘兹大学获得博士学位，现为美国威斯康星大学麦迪逊分校数学系教授，曾任该系主任多年。他的研究方向包括组合数学，图论，线性代数和矩阵理论，编码理论等。Brualdi教授的学术活动非常丰富，担任过多种学术期刊的主编。2000年由于“在组合数学研究中所做出的杰出终身成就”而获得组合数学及其应用学会颁发的欧拉奖章。
在第3版的前言中曾经提到如何重写某些章节以及如何添加某些新的材料和练习. 从第2版到第3版一些主要的变化如下：
第4章添加了偏序和等价关系的介绍.
第5章增加了再论偏序集一节, 其中证明了Dilwonh定理及其对偶.
第8章加写了正整数分拆的新内容.
第11章是本书讨论图论的第一章, 其中, 树被定义为移去任意一边后都不再连通的连通图, 并删掉了介绍有向图的一节.
第12章是新的一章, 讨论有向图和网络. 这一章包括Ford和Fulkermn的最大流最小割定理的证明, 由此, 第9章的Menger定理和K6nig定理作为推论而导出.
第2版第12章讨论的图论中基本的数构成第3版的第13章. P61ya计数法原先在第13章, 后来改成第14章.
第4版修正丁我所知道的所有排印错误, 从语言上做了一些小的调整(包括在论述图论的各章中用"路径"代替"链"), 插入某些零星内容, 并增加了60多道新的具有挑战性的练习题. 我不愿把这本书改变过多或是加入太多新的课题, 也不喜欢有过多词汇的书籍(而本前言就没有太多的词汇), 不想陷进那样的陷阱. 此外, 本版添加两节新内容. 第6章添加新的最后一节, 论述莫比乌斯反演, 作为容斥原理的推广. 第8章新增了一节, 论述格路径以及小Schroder数和大Schfoder数.
如同早期版本一样, 可以使用本书作为一学期或两学期的本科课程. 第一学期可侧重于计数法, 而第二学期则侧重图论和设计. 也可以合在一起作为一学期的课程, 讨论某些计数法和图论, 或者讨论一些计数法和设计理论. 下面是对每章的简短评述和各章间相互关系的介绍：
第1章是引论性的一章, 我通常从这章选择一两个课题并最多花费两节课讲述这一章. 第2章讨论鸽巢原理, 至少应该以缩减的形式讨论. 不过要注意, 这对于后面鸽巢原理某些困难的应用以及Rarnsey定理的理解却无济于事. 第3章到第8章主要讨论计数技术和计数结果序列的某些性质. 应该按顺序讨论它们. 第4章涉及排列和组合的生成方法, 还有上面提到的偏序和等价关系的介绍. 然而, 除第5章论述偏序集的那一节外, 第4章后面各章基本上都与第4章无关. 因此, 第4章可以略去或压缩, 甚至根本不讨论偏序集. 第5章论述二项式系数的性质, 第6章讨论容斥原理, 论述莫比乌斯反演的新的一节在后面各章都用不到. 第7章比较长, 讨论递推关系的求解以及计数中生成函数的使用. 第8章主要关于Catalan数. 第一类和第二类Stirling数. 分拆数以及小Schroder数和大Schroder数. 后面各章与第8章无关.
第9章讨论二分图中的匹配问题. 虽然本书在介绍图之前引入了二分图, 但本章与后面的图论各章基本上没有什么关系. 除匹配理论对拉丁方的应用外, 论述设计的第10章独立于本书其余部分. 不过, 在10. 4节末尾用到第9章建立的匹配理论. 第11章和第13章对图论进行了广泛的讨论, 重点放在图论算法上. 第12章涉及有向图和网络流. 第14章处理在置换群作用下的计数问题, 这里确实用到了先前许多的计数思想. 除最后一个例子外, 本章与图论和设计的各章无关.
当教授本书一学期的课程时, 我喜欢以论述Polya计数法的第14章作为结束, 这能够使我们解决许多计数问题, 而这些问题用前面各章的方法是无法解决的. 在第14章之后, 给出了本书大约650道练习题中的部分解答和提示. 一些练习旁边标有星号"*", 表明它们更具有挑战性. 在证明的最后和例子的末尾均标有符号"口"以示结束.
确定阅读本书的前提条件比较困难. 如同所有想要作为教材的著作一样, 高度激发学生的热情和兴趣是有帮助的. 或许本书更适合那些成功地学习过微积分和线性代数初等课程的读者. 这里对微积分的使用很少, 而涉及的线性代数也不多, 因此对于不熟悉它们的读者阅读本书也不应该有任何问题.
自从第1版发行以来已经25年了, 但本书仍然受到专业数学同行的欢迎, 我很知足.
非常感谢鼓励我修订第4版以及向我提供有益建议的许多专家：RussRowlett(坎裴尔北加州大学), James Sellers(Perin州立大学), Michael Buchner(新墨西哥大学). 正如第3版一样, 我特别感谢Leroy P. Meyers(俄亥俄州立大学)和Tom Zaslavsky(SUNY系统Binghamton分校), 他们每位都向我提供了对第3版的广泛而详尽的建议. 对于第4版, 我得到了NilsAndersen(哥本哈根大学). James Propp(威斯康星大学)和Louis Deatt(威斯康星大学)许多有用的建议, 他们阅读了新版并对格路径的新的一节发表了看法. 我希望本书继续反映我对组合数学的热爱以及我讲授这门课程的热情和讲授的方式.
最后, 再次感谢我亲爱的妻子Mona, 是她给我的生活带来幸福. 激情和勇气.
Richard A. Brualdi
brualdi@math. wisc. edu
第二书店&China-pub战略联盟提供专业服务
第二书店联系方式 010-64348411 webmaster@dearbook.com