《组合数学》（第4版）[（美）Richard.A.Brualdi]

---

点击下面的链接进行在线阅读，获取操作。

注意！Lbook业务已经进行改版，请从Lbook入口进入并获取PDF资源，下面的资源现在无法访问！

组合数学（第4版）[（美）Richard.A.Brualdi].pdf

---

简介

组合数学的起源很早，在古代世界各地都有出现，无论是国内的《九章算术》还是国外的《Sushruta Samhita》中都有简单的组合问题的出现，或者说古代一切关于计数的问题都可以归于组合数学的范畴。

文艺复兴之后，和物理、化学、还有数学的其他分支一样，组合数学迎来了真正意义上的发展，牛顿、雅各布、帕斯卡和欧拉等人的工作为这一学科奠定了坚实的基础。而在近代，西尔维斯特和麦克马洪等人的工作也为这一学科增添了一抹亮色。其中以图论中的一些问题为代表，四色猜想，Ramsey问题，Turan问题等等都是很有意思也很有价值的问题。

组合数学并不像代数、分析、几何等是数学最主要的分支，尽管ta只是一个小学科，但是其理论和工具往往会涵盖和横跨数学的各个分支，从代数到概率论，从分析到数论，正是这种和其他学科的新联系和应用使得组合数学在二十世纪下半叶有了飞速的发展。这种联系打破了组合数学和其他数学分支间甚至和理论计算机科学之间的界限，同时也产生了一些分裂，由此也诞生了很多很有活力的新分支。

分支

• 计数组合（Enumerative combinatorics）

这是组合数学中最经典的研究领域，简而言之，就是研究满足某种性质的集合的大小。组合、排列是最基本的方法，代数变形和递推等是最常见处理的手段，这个大概会在下一章补充。典型问题：各种一共有多少方案的问题、套了实际背景的数列求解（斐波那契、卡特兰）等。

• 解析组合（Analytic combinatorics）

解析组合关心对组合结构的计数，主要通过解析的工具来研究问题，从复分析到概率论都有，一个比较常见的工具是生成函数，常用的有普通型生成函数、指数型生成函数、Dirichlet生成函数。这个会在之后的篇章进行介绍。另外，因为对于某些问题求得一个精确解比较困难，所以有时候我们会更关心对于答案的阶的渐进分析。

• 图论（Graph theory）

图论和组合没有包含关系，应该说是互有交叉，有很多联系的学科。图论中在涉及对一些图论对象和概念的计数的时候会应用到组合数学的思想，尽管组合数学适用于许多图论问题，但二者关心的问题并不一样。

• 偏序理论（Order theory）

偏序理论是研究集合上的偏序集的理论，在代数、几何、数论、图论和组合数学中都有丰富的偏序集的出现，从格到布尔代数等等。著名的Dilworth’s theorem是一个很典型的代表，也是一个很有意思的东西，之后应该会写。

• 极值组合（Extremal combinatorics）

其实应该叫极值图论的，研究满足某些性质的(最大或者最小)极值图。对于不同的图的不变量,我们都可以考虑他们的极值问题,例如图的顶点数,边数,最短圈,最长圈,染色数等等。更加抽象的来说,极值图论研究图的整体性质如何影响图的局部结构。典型的问题就是Turan Type Problem和Ramsey Theory，这些问题算是目前图论领域最热门的方向，基本有些进展就会是big news，像前一阵的Ashwin Sah改进了Ramsey的上界的渐进阶就引起了不少轰动。关于极值图论，知乎上有很多优秀的答主，以Yifan和等待小蜗牛为代表，感兴趣的同学可以关注一下，非常推荐。

• 概率组合（Probabilistic combinatorics）

通过概率的方法来研究，在Paul Erdős引入概率论的方法后，组合数学迎来了崭新的发展面貌，通过与概率论中的诸多工具结合，发展出了很多卓有成效的方法和耳目一新的结果，Ramsey的下界的渐进阶就可以通过这样的方法得到估计。一些典型的问题像随机离散对象，像随机图中某一特性的概率是多少。其实不应该作为这样学科的分类，应该说是一个应用概率论的思想和方法。

ps.以上分类不是一个对组合数学不交并的拆分，仅仅为了说明一些组合数学的思想工具和应用领域。

---

总的来说，组合数学对大部分人没啥用，但是如果你是处理计算机的一些内容的话，那么可能有点帮助。

组合数学更类似于离散数学的一个分支。

2023年7月1日