#️⃣组合数学—期末笔记

status
Published
type
Post
date
Jun 12, 2025
slug
combinatorics-final
summary
本文汇总了组合数学课程中的大部分知识点以及定理。
tags
组合数学
category
期末复习
icon
password
🗒️
这篇文章是笔者在复习南京大学 组合数学 课程时的笔记。这门课程口碑极佳，很大程度上得益于尹老师的授课。尹老师备课极其充分，slides 衔接连贯、条理清晰，甚至在医院挂水时也坚持来上课，实在是一位难得的好老师。尹老师所讲授的课程通常都配有非常详尽的 lecture notes，质量很高，丝毫不逊于国外同类课程。

知识点

The Twelvefold Way

notion image
  1. 第一行： 可区分， 可区分
    1. Trivial
    2. : 表示下降阶乘，即从 开始，连续乘以比前一个数小 的数，共乘 项。相当于 .
    3. : 第二型斯特林数，表示将 个可区分元素分成 个不可区分子集的数量（见第三行第三列）
  1. 第二行： 不可区分， 可区分
    1. : multiset coefficient, 表示将 个球放入 个盒子中（允许空盒子）的数量（求解时转换为不允许）。.
    2. Trivial
    3. 个球放入 个盒子中，每个盒子至少一个球
  1. 第三行： 可区分， 不可区分
    1. Easy to understand
    2. Easy to understand
    3. 定义
  1. 第四行： 不可区分， 不可区分
    1. : 表示把数字 分为 份。
    2. Trivial
    3. 定义

生成函数 (OGF)

普通生成函数（Ordinary Generating Function, 简称 OGF）是一种用形式幂级数来表示和操作数列的数学工具。
对一个数列：
它的 OGF 定义为：
OGF 可以用于生成组合的数量。这是 OGF 的一种典型的应用场景，通过构造多项式，我们可以利用代数运算生成我们想要的组合问题的答案：
notion image
斐波那契数列是递归问题的一个典型例子。用生成函数解决递归问题的通常步骤如下：
  1. 给出一个递归式:
  1. 等式两边乘 并对全部的 求和: . 将等式右边适当操作，转换为 的表达式: .
  1. 求解方程得到 的公式:
  1. 将 展开为幂级数， 就是 的系数（需要用到几何展开式：

Pólya 计数法

首先引入轨道的概念。轨道指的是 被置换群 中的元素全部作用一遍之后在 的落点（记忆方法： 是 乘上 表示 上的元素作用在 上）：
一个 的不变集指的是这个 在 中的不动点：
一个 的稳定器指的是那些以这个 为不动点的排列：
Pólya 计数就是将旋转对称产生的重复计数产生的元素全部算在一个元素（可以视为代表元）的轨道里面，这样只需要找到一种方法计算所有的轨道数。下面的 Burnside’s Lemma 给出了计算轨道数的方法。
Burnside’s Lemma 是一个元素 的稳定器和轨道数大小的关系。即 中的所有操作可以拆解为“将 变为不同状态的操作（轨道）”和“将 保持不变的操作（稳定子群）”的结合：
Burnside 引理说的是：一个集合的轨道数 就是在置换群 作用下的各元素不动点的平均数。
notion image
Burnside 引理巧妙地将计算轨道数这么一个复杂的问题转换为计算所有元素的不动点数量。
然而，计算不动点的数量有时候显得过于繁琐。Pólya 计数就是专门处理“使用最多 种颜色给 个对象染色”的问题。
首先引入一个概念，称为 cycle index. cycle index 是定义在一个 上面。一个置换可以表示为一个或多个 "cycles"，由于一个 "cycle" 中的点是“等价”的，所以只能染一个颜色。因此如果置换 可以分解为 个 cycles, 那么在 作用下不变的着色数为 （假设 种颜色）。定义任何一个 的 cycle index 为：
其中 是第 个 cycle 的长度。定义置换群 的 cycle index 为：
根据 Burnside 引理，不考虑置换群 描述的对称性， 个对象的 -着色的等价类的数量由下式给出：
也就是说，我们得出了（一种简单的情况）：
其中 表示 的循环个数。

Cayley 公式

关于树的 Cayley 公式：

Prüfer Code

Prüfer code 是一种编码树的手段。它将 个顶点的树映射到 长度的元组：
  1. 编码：设当前树最小的叶子为 ，与其相连的顶点为 。去掉 并将 添加到元组中。重复 次。首先我们知道最后剩下的一定是最大的顶点（即 ），因为一个树至少有两个叶子。根据上一条结论我们知道 ，因此这一位也可以省略。一个树的 Prüfer code 就是 .
  1. 性质
    1. 原图中的非叶子节点 在 Prüfer code 中出现 次。
    2. 与 Prüfer code 对应的 序列是互不相同的 个数，因为每个数在该序列中出现意味着它被删掉了，每个顶点对应的编号只能被删除一次。
    3. 对于 ，我们由性质 1 知道它不可能是 中的元素，因为这些元素在当前图中的度至少为 2. 由性质 2 知道它不可能是 中的元素，因为序列 u 中的元素是两两不同的。根据定义 又是最小的一个数，因此我们有下面的解码方案。
  1. 解码：根据一个 Prüfer code， 是不在 中的最小的数。这样就还原出 u 序列，进而还原出图上的所有边，进而还原出原来的树。

存在性问题

Shannon’s Circuit Lower Bound

香农的电路下界说明了，对于任意足够大的输入长度 ，几乎所有的布尔函数 都需要至少指数级大小的布尔电路来实现：

Sperner’s Lemma

Sperner 引理说的是有关三角剖分着色的存在性。三角剖分指的是将一个大三角形 分解为小三角形（cells），任意两个 cells 要么不相交，要么共享一个顶点或一条边。三角形 的一个适当着色（proper coloring）指的是对三角剖分中的所有顶点用红绿蓝三种颜色着色，并且满足：
  1. 颜色各不相同
  1. 每条边上只有两种颜色
Sperner Lemma claims:

Erdős-Szekeres Theorem

A sequence of more than different real numbers must contain either an increasing subsequence of length , or a decreasing subsequence of length .
考虑元组 ， 表示以 结尾（或开始）的最长递增子序列的长度， 表示以 结尾（或开始）的最长递减子序列的长度。这个元组的有趣性质是对任何 ，。现有 个元组，将其放入 的矩阵中，由于鸽笼原理，至少有一个元组的在矩阵之外，即 或 .

概率法

Szele Theorem

该定理被认为是概率法的首次应用。它说明了一个 顶点的竞赛图中哈密尔顿路径的数量：

Independent Sets

该定理的证明先随机以概率 选择一个顶点集合 ，然后删除冲突边的一个端点，将 转换为独立集 ，然后通过贪心调整参数 获取 期望的最大值。

Erdős Theorem

定义图的 girth 指的是图上最短的环的长度，这是图的一个局部属性。直觉上讲，一个 girth 较大的图的染色应该比较容易，因为一个很大的环只需要 2 或 3 种颜色。但 Erdős 的定理表明，即使一个图的 girth 很大，其色数也可能很高。

Lovász Local Lemma (LLL)

symmetric case:
Let be a set of events, and assume that the following hold:
  1. for all ,
  1. the maximum degree of the dependency graph for the events is , and
Then:
即，如果满足了上面两个条件，那么避开所有事件 的概率 ，意味着存在一个避开所有事件的 instance.

极值图论

极值图论研究的内容：如果一个图 具有某种性质，那么它最多有多少条边？

Mantel’s Theorem

Mantel 定理说的是一个具有 “triangle free” 这个性质的图，最多有多少条边：

Turán’s Theorem

该定理是 Mantel 定理的一般化。它研究的是在一个不含某个完全子图的简单图中，最多能有多少条边：
一个 Turán graph 指的是一个完全 部图，这个图不含 且边数最多。
通过顶点复制（vertex duplication）的方法，可以证明 Turán graph 是唯一的极值图。

Erdős–Stone Theorem

该定理被称为“极值图论基本定理”。首先定义 指的是 部图，每个部分恰有 个顶点（即 ）。 表示不具备图 的顶点数为 的图具有的最大边数。则：
该定理的一个重要的推论，图 的点染色数（chromatic number）与不含 的图的最大边数之间的渐近关系：
该定理说明，一个图越难染色，则不含它的图就越稀疏。

极值集合论

Sunflower Lemma (Erdős-Rado)

集族 是一个 大小的 Sunflower，它的核心（Core）为 ，则 .
Sunflower 引理说明了在集合 的 -uniform 的子集 中，如果 的大小足够大，那么 一定存在一个 sunflower:
这个引理的证明是通过对 k 进行归纳。证明过程中寻找了一个最大不相交子族 ，如果 那么得证，如果 那么构造一个 ，这里 ，该数值和定理给出形式类似，我们在这个数值上应用归纳假设，筛选出高频元素 ，并将原问题转为 规模的子问题，再将 和子问题的解一起构成原问题的解，完成证明。

Erdős-Ko-Rado Theorem

集族 被称为 intersecting（相交）如果对任何 ，都有 。Erdős–Ko–Rado 定理给出了非平凡（）相交集族的最大基数。
设 ， 且 。如果 是相交的，那么：

Sperner Theorem

该定理可以被称为极值集合论基本定理。它说的是集合子集族中最大反链的大小：

LYM Inequality

这个不等式比 Sperner Theorem 更强，它说的是一条链和反链最多有一个交点：

Kruskal–Katona Theorem

Kruskal–Katona theorem 说的是在所有大小为 的 元集族 中， ，即按照 序排列的前 个集合组成的集合影子最小：
其中 是 cascade 表示：
Erdős-Ko-Rado Theorem 是该定理 的一种特殊情况。

Ramsey 理论

Ramsey Theorem

表示任意对完全图 的边进行二染色，如果 ，那么一定存在一个红色的 或一个蓝色的 . 该数有一个不等式：
根据这个不等式， 是有穷的。最小的 成为 Ramsey number. Spencer Theorem Lower bound for diagonal Ramsey number:
Prove using Lovász Local Lemma.

The “Happy Ending” problem

平面上任意的 5 个点（三点不共线）都有 4 个点可以构成凸四边形

Yao’s lower bound

在一个大小为 的有序数组中, 任何算法都需要至少 次访问来查找某个特定元素。

Linial’s lower bound

一个 轮的局部算法，在一个 个节点的环上计算最大独立集（maximal independent set, MIS），有：
这个下界回答了一个问题，即：局部定义的问题不能被局部计算。

匹配论

Hall’s Theorem

集合版本：集合 有相异代表系（SDR）当且仅当：
图论版本：二分图 has a matching of 当且仅当：

Min-Max Theorems

König-Egerváry Theorem (König’s Theorem)
图版本：二分图的最大匹配大小 = 最小点覆盖大小
将二分图 转换为一个 的 0-1 矩阵 ， 当且仅当 。这样，匹配转换为不同行不同列 的个数，点覆盖转换为能覆盖所有 的行和列的个数。矩阵版本：
是一个 的 - 矩阵，独立的 的最大数量 覆盖所有 的行列数

Dilworth’s Theorem

在一个有限的偏序集中，覆盖整个集合的链的最小数量 最大反链的大小

Erdős-Szekeres Theorem

一个至少含有 个相异实数的序列, 要么含有一个长度为 的递增子序列, 要么含有一个长度为 的递减子序列

往年卷

23 spring

1

考察 The Twelvefold Way

2

二项式定理：
左右两边平方，考察 的系数。

3

这道题的关键是利用几何展开式对第二问得到的 进行展开：

4

全班 个同学，分为 个群，每个群 个人。现在要选出一个班委集合。在每个群中，成员可以是被推荐或被不推荐称为班委，一个成员在不同群的评价可以不同。若每个人最多加入 个群，利用概率法证明：存在一种班委选择方式，使得每个群对成员的意见（推荐或不推荐）至少有一个符合。
解答：随机地产生对每个群中成员的评价。设 表示第 个群中的意见全都不符合。则 . 和 相关当且仅当 两个群有共同的成员。由于每个人最多加入 个群，因此 最多与 个事件相关，即 . 我们现在验证对称 LLL 的条件。
因此我们知道 ，得证。

5

这道题很迷。在看到正确答案之前我是不会说一句话的。

6

一个 Hall 定理的简单应用。

25 srping updated

考了 40 分的概率法大题，看来老师真的很喜欢概率法。
Loading...

© Qiyue Zhang 2026