组合数学常用公式汇总

基本计数

生成函数

生成函数的运算

Let and ,

按项展开

泰勒级数：

等比数列级数：

牛顿公式： where

卡特兰数

闭式解：

容斥原理

通常使用它的补集形式

Cayley 公式

个顶点可以构成 棵不同的树。

Pólya 计数定理

在排列集 上给定一个操作群 ，则轨道数： 其中 是颜色的个数， 是 中包含的环的个数。

鸽巢原理

把 只鸽子放在 个笼子里，存在一个笼子里有多于 只鸽子。

概率方法

• 如果某个 object 被选中的概率 ，那它就存在；互补地，如果某个 object 没被选中的概率 ，那它就存在。
• 如果某个随机变量的期望（均值）为 ，至少存在一个取值不小于 ，至少有一个取值不大于 。

Lovász 局部定理

定义 是一系列的“坏”事件（我们希望它不发生），并且

1. 对于所有 ，
2. 依赖图的最大度数 满足

那么：

即，有可能所有“坏”事件都不发生。

极值图论 *

• Mantel 定理：如果图 中没有三角形，则
• Turán 定理：如果图 中没有 -clique，，那么
• Erdős–Stone 定理：记 为：一个定点数为 的图 如果要满足 ，最多可能有多少条边。则

极值集合论 *

• Erdős–Ko–Rado 定理：记 ，其中 且 。 如果 中的各集合两两有（非空）交集, 那么
• Sperner 系统：记 ，其中 。如果 是一个 antichain，那么

Ramsey 定理 *

（图论版本）定义 为正整数。存在一个数 满足：当 时，无论怎样着色（红色和蓝色），必然存在一个红色的 或 蓝色的

匹配论

Hall 定理

集合 ，每个集合都能选出唯一代表，当且仅当， for all

这个充要条件 for all 被称为 Hall's condition。

相关定理：

• König-Egerváry 定理：二部图中，最大匹配的大小等于最小点覆盖集的大小。
• Menger 定理：在图上分开两个点至少要去掉几个点？等于这两点间不相交的路径的个数。
• Dilworth 定理：一个偏序集分成多少个 chian？等于最大 antichain 的大小。

最大流最小切定理

流网络中，最大流等于最小切。

---

Ref.

1. 尹一通老师的组合数学课程（Fall 2015）
2. 波利亞計數定理 - 维基百科

P.S.

• 给 Ref.1 做了个备份。版权归原作者所有。