A Course in Combinatorics（组合数学教程）

引用

van Lint, J. H., & Wilson, R. M. (2001). A Course in Combinatorics (2nd ed.). Cambridge University Press.

章节概要

第二版共38个简短的章，前有两版的序言，后有参考文献和索引；印刷本约600页。剑桥大学出版社把它描述为一本讨论事物如何排列与分配的书，涉及几何、代数和分析的思想，以统一的方式处理图论、极值问题、设计、着色和编码，适合高年级本科或研究生起始阶段的课程。各章以主题命名，下面的分组依照目录顺序。

第1–4章：图；树；图的着色与拉姆齐定理；图兰定理与极值图

全书以基础图论和树开篇，随即转入着色、拉姆齐定理和图兰定理所代表的极值问题。

第5–9章：相异代表系；迪尔沃思定理与极值集合论；网络中的流；德布鲁因序列；两个(0, 1, ⋆)问题：图的编址与哈希编码方案

这几章涵盖相异代表系、迪尔沃思定理与极值集合论、网络中的流、德布鲁因序列，以及关于图的编址和一种哈希编码方案的一对问题。

第10–12章：容斥原理与反演公式；积和式；范德瓦尔登猜想

计数的线索从容斥原理开始，然后转向积和式以及关于积和式的范德瓦尔登猜想。

第13–15章：基本计数与斯特林数；递推与生成函数；分拆

计数技术继续展开，涉及斯特林数、递推、生成函数和分拆。

第16–18章：(0, 1)矩阵；拉丁方；哈达玛矩阵与里德–穆勒码

接下来的一组转向由0和1构成的矩阵、拉丁方以及哈达玛矩阵，并以里德–穆勒码结束。

第19–23章：设计；码与设计；强正则图与部分几何；正交拉丁方；射影几何与组合几何

书中在这里汇集了核心的结构：设计及其与码的关系、强正则图与部分几何、正交拉丁方，以及射影几何与组合几何。

第24–26章：高斯数与q类比；格与默比乌斯反演；组合设计与射影几何

这一组讨论q类比、格与默比乌斯反演，并再次回到组合设计与射影几何。

第27–31章：差集与自同构；差集与群环；码与对称设计；结合方案；图论中的（更多）代数技巧

代数部分处理差集、群环、对称设计与码、结合方案，以及图论中更多的代数方法。

第32–36章：图的连通性；平面性与着色；惠特尼对偶；图在曲面上的嵌入；电网络与方块剖分

最后一组图论章节涉及连通性、平面性与着色、对偶、图在曲面上的嵌入，以及电网络与“方块剖分正方形”问题。

第37–38章：波利亚计数理论；巴拉尼艾定理

全书以波利亚计数理论和巴拉尼艾定理收尾。

核心概念

第1–18章：图、极值问题与计数

• 拉姆齐理论与极值图：拉姆齐定理和图兰定理（第3–4章）。
• 容斥与积和式：第10–12章。
• 生成函数与分拆：第13–15章。
• 拉丁方与哈达玛矩阵：第17–18章。

第19–38章：设计、码、几何与更多图论

• 设计、码与结合方案：第19–20章、第29章和第30章。
• 强正则图、差集与群环：第21、27和28章。
• 平面性、对偶与图的嵌入：第33–35章。
• 波利亚计数与巴拉尼艾定理：第37–38章。

评析

优点

• 在简短的章节中展现广度。 38个紧凑的章节给出这一学科的一幅宽广地图，剑桥大学出版社称其以统一方式处理图论、极值问题、设计、着色和编码。迪特尔·荣格尼克尔在 Zentralblatt MATH 上评论时预期它会成为组合学教材中的标准选择之一。
• 优雅的证明与好问题。 《数学公报》称它是优雅证明和诱人例子的来源；剑桥引用的另一篇评论则指出，书中有大量有趣的问题、具体的例子，以及有用的注记和参考文献。
• 在两个层次上都有用。 剑桥引用了署名 EMS 的一篇评论，称它值得推荐给任何学习组合学的学生，并说由于内容广泛，对研究者也有许多新东西。
• 代数与几何思想并置。 目录把码、设计、有限几何、群环和结合方案放在一本书里，让学生从多个侧面看到同样的结构。

局限

• 要求较高。 《数学公报》的评论说，没有人会觉得这本书容易，并称它毫不掩饰地、令人印象深刻地“数学”。作者设定的读者是高年级本科生或研究生起步阶段的学生。
• 不是一条单一的叙事线。 各章按主题而不是连续的论证来编排，因此从第1章到第38章没有一条贯穿始终的线索，读者要预期自己选择一条路线。
• 先修要求不均。 前面的章节除离散数学课程外几乎不需要什么，而代数性的章节（群环、结合方案）要用到读者必须已有的抽象代数。

在课程中的定位

在一份其余多为入门课程的书单里，这是高阶的组合学著作。Susanna Epp 的《Discrete Mathematics with Applications》、Kenneth Rosen 的《Discrete Mathematics and Its Applications》以及 Oscar Levin 的开放教材，面向初次接触这类数学的读者，讲授逻辑、证明、计数与图。Lovász、Pelikán 和 Vesztergombi 的《Discrete Mathematics: Elementary and Beyond》是一本以问题为导向的简短入门书，自然地排在本书之前。Graham、Knuth 和 Patashnik 的《Concrete Mathematics》在生成函数和递推上与本书有重叠，但面向算法分析，而 van Lint 和 Wilson 的书更偏向设计、码与有限几何。

如何使用本书

本书适合已修完离散数学课程和第一门线性代数课程的高年级本科生与研究生；一些抽象代数知识对后面的章节有帮助。

• 核心路径： 第1–4章（图与极值问题）、第10–15章（计数）以及第19、20章（设计与码），可以构成一门自足的入门课。
• 代数路径： 关于强正则图、几何、差集与结合方案的第21、23和27–30章，对懂一些抽象代数的读者回报更大。
• 图论路径： 第32–36章构成关于连通性、平面性与曲面的第二门图论课。
• 练习： 由于各章简短而相对独立，可以每周读一章，也可以不按顺序阅读；做书中的问题，并利用评论者称赞的注记和参考文献。