组合数学常用公式汇总

基本计数

生成函数

生成函数的运算

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 做了个备份。版权归原作者所有。