组合数学学习笔记
henry_qwh
·
·
算法·理论
Part 1 基础知识
一、加法原理
若一件事有 n 种完成方式，而每种方式有 m 种方法，那么这件事的完成方法有 \sum_{i=1}^nm_i 种。
二、乘法原理
若完成一件事有 n 个步骤，而完成每个步骤有 m 种方法，那么这件事的完成方法有 \prod_{i=1}^nm_i 种。
三、排列
-
定义： 在 n 个元素中按顺序选出 m 个的方案数，记为 A_n^m。
-
求法：
我们知道第一个元素有 n 种选择方案，第二个元素有 n-1 种选择方案，以此类推，第 m 个元素有 n-m+1 种选择方案。根据乘法原理可知，总的选择方法有：
n\cdot(n-1)\cdot(n-2)\cdots (n-m+1)
方便起见，我们定义：
阶乘： 记 n!=\prod_{i=1}^ni=1\cdot2\cdots (n-1)\cdot n 为 n 的阶乘。规定 0! = 1
下降（阶乘）幂： 记 n^{\underline{m}}=\prod_{i=0}^{m-1}(n-i)=n\cdot(n-1)\cdot(n-2)\cdots (n-m+1) 为 n 的 m 次下降（阶乘）幂
结合排列的定义可得
A_n^m=\frac{n!}{(n-m)!}=n^{\underline m}
当 n=m 时，称为 n 的全排列。
四、组合
- 定义: 从 n 个元素中，选出 m 个的方案数，记为 C_n^m，又记为 n\choose m。
事实上，组合就是不考虑顺序的排列。
- 求法
因为组合数选出来的是没有顺序的，而排列选出来的是有顺序的，而这选出来的 m 个元素的排列方式有 A_m^m=m! 种。那么这 n 个元素的组合有：
C_n^m=\frac{A_n^m}{A_m^m}=\frac{n!}{(n-m)!m!}
Part 2 一些定理
一、组合数的性质定理
{n\choose m}={n\choose n-m}
由以上定理，可以容易地推出组合数的递推式：
{n\choose m}={n-1\choose m}+{n-1\choose m-1}
根据递推式，我们便可以 O(n^2) 求出组合数。
二、二项式定理
(a+b)^n=\sum_{i=0}^n{n\choose i}a^ib^{n-i}
我们可以考虑右式由 n 个多项式 (a+b) 相乘得到。若 a 的幂为 i，说明在 n 个多项式中，有 i 个选择了 a。从 n 个多项式中选择 i 个的数量为 n\choose i。
三、二项式反演
f(n)=\sum_{i=0}^n{n\choose i}g(i)\iff g(n)=\sum_{i=0}^n{n\choose i}(-1)^{n-i}f(i)
证明：
\begin{aligned}
\sum_{i=0}^n{n\choose i}(-1)^{n-i}f(i)&=\sum_{i=0}^n{n\choose i}(-1)^{n-i}\sum_{j=0}^i{i\choose j}g(j)\\
&=\sum_{i=0}^n\sum_{j=0}^i{n\choose i}{i\choose j}(-1)^{n-i}g(j)\\
&=\sum_{i=0}^n\sum_{j=0}^i{n\choose j}{n-j\choose i-j}(-1)^{n-i}g(j)\\
&=\sum_{j=0}^n{n\choose j}g(j)\sum_{i=j}^n{n-j\choose i-j}(-1)^{n-i}\\
&=\sum_{j=0}^n{n\choose j}g(j)\sum_{i=0}^{n-j}{n-j\choose i}(-1)^{n-j-i}\\
&=\sum_{j=0}^n{n\choose j}g(j)\cdot 0^{n-j}\\
&=g(n)\\
\end{aligned}
\square
在上面的证明中，为了方便，我们认为 0^0 = 1。
四、一些特殊的排列组合
-
可重排列： 从 n 个元素中可重复地选取 m 个，总方案数为 n^m。
-
圆排列: 从 n 个元素中选取 r 个排成一个圆的方案数称为圆排列数，记为 Q_n^r。
由于循环的位移可以带来相同的排列，所以 Q_n^r=\frac{A_n^r}{r}。
- 可重组合： 从 n 个元素中可重复地选取 m 个组成一个集合的方案数称为可重组合数，记为 H_n^m。
设这 n 个元素为 1,2,\cdots,n，设取出的 m 个元素为 x_1,x_2,\cdots,x_m(x_1\le x_2\le\cdots\le x_m)。我们令 y_k=x_k+k-1，得到另一组数 y_1,y_2,\cdots,y_m(y_1\le y_2\le\cdots\le y_m)，这组数可以看作是从 n-m+1 个不同元素中选出来的，于是有 H_n^m=C_{n-m+1}^m。
五、卢卡斯定理
这是一个特别重要的定理。
先给出这个定理的内容：
对于质数 p，有
{n\choose m} \bmod p= {\lfloor n/p \rfloor\choose\lfloor m/p\rfloor} \cdot{n\bmod p\choose m\bmod p}\bmod p
时间复杂度 O(f(p)+g(n)\log n)，其中 f(n) 为预处理组合数的复杂度，g(n) 为单次处理组合数的复杂度。
具体的证明可以参考 oi-wiki 的证明。
通过上式，我们便可以递归求出一个组合数对质数取模的结果。现给出具体的代码实现。
int Lucas(int n,int m)
{
if (m == 0) return 1;
return (C(n%p,m%p)*Lucas(n/p,m/p))%p;
}
六、组合数的其他性质
-
{n\choose m} = {n\choose n-m} = \frac{n}{m}{n-1\choose m-1}
-
{n+1\choose m} = {n\choose m}+{n\choose m-1}
-
{n\choose k}\cdot{k\choose m}={n\choose m}\cdot{n-m\choose k-m}={n\choose k-m}\cdot{n-k+m\choose m}
Part 3 卡特兰数
卡特兰数是一种特殊的组合递推数列，记为 H_n，应用十分广泛。
一、定义
- 卡特兰数的计算公式
H_n=\frac{2n\choose n}{n+1}(n\ge2,n\in \mathbb{N_+})
- 其他的卡特兰数公式
H_n=
\begin{cases}
\sum\limits_{i=1}^nH_{i-1}H_{n-i}&n\ge2,n\in\mathbb{N_+}\\
1&n=0,1
\end{cases}
H_n=\frac{H_{n-1}(4n-2)}{n+1}\\
H_n={2n\choose n}-{2n\choose n-1}
二、应用
卡特兰数可以应用于以下问题：
-
有 2n 个人排成一行进入剧场。入场费 5 元。其中只有 n 个人有一张 5 元钞票，另外 n 人只有 10 元钞票，剧院无其它钞票，问有多少种方法使得只要有 10 元的人买票，售票处就有 5 元的钞票找零？
-
有一个大小为 n\times n 的方格图左下角为 (0, 0) 右上角为 (n, n)，从左下角开始每次都只能向右或者向上走一单位，不走到对角线 y=x 上方（但可以触碰）的情况下到达右上角有多少可能的路径？
-
在圆上选择 2n 个点，将这些点成对连接起来使得所得到的 n 条线段不相交的方法数？
-
对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方法数？
-
一个栈（无穷大）的进栈序列为 1,2,3, \cdots ,n 有多少个不同的出栈序列？
-
-
由 n 个 +1 和 n 个 -1 组成的 2n 个数 a_1,a_2, \cdots ,a_{2n}，其部分和满足 a_1+a_2+ \cdots +a_k \geq 0~(k=1,2,3, \cdots ,2n)，有多少个满足条件的数列？
Part 4 常考模型与方法
一、分组问题
球全部相同，盒子之间互不相同。若每个盒子至少放有 k(k\ge2) 个小球，求放置方法数。
应用 隔板法，我们可以在朴素隔板法的基础上给每个盒子去除 k-1 个，最后将这 k-1 个补齐。此时的物品总数有 n-(k-1)m 个，因此答案为 \Large{m-(k-1)m-1\choose m-1}。
二、相邻问题
将 n 个元素排成一排，要求其中 m 个特定元素相邻，求排列方法数。
对于这种问题，我们应用捆绑法。我们将这 m 个特定元素视为一个元素，此时一共有 n-m+1 个元素，排法有 A_{n-m+1}^{n-m+1} 种。考虑到这 m 个特定元素之间有 A_m^m 种排列方法，因此总排法有 A_{n-m+1}^{n-m+1}A_m^m 种。
三、定序问题
将 n 个元素排成一排，要求其中 m 个元素的相对位置固定但不必相邻，求排列方法数。
我们可以使用 缩倍法，相当于这 m 个元素相同。这时便可容易地得到排列方法有 \frac{n!}{m!} 种。
四、不相邻问题
将 n 个元素排成一排，要求其中 m 个特定元素不相邻，求排列方法数。
对此，我们应用 插空法。我们先排没有要求的 n-m 个元素，一共 A_{n-m}^{n-m} 种排法。这 n-m 个元素构成了 n-m+1 个空隙，我们可以在空隙中放入至多一个元素，一共 A_{n-m+1}^{m}。所以总方法有 A_{n-m}^{n-m}A_{n-m+1}^{m} 种。
不相邻问题还有以下表现形式：
从排成一排的 n 个座位中选出 m 个，要求这 m 个座位不相邻，求总选择方案数。
考虑除去这 m 个座位，一共有 n-m 个座位，构成了 n-m+1 个空隙，可以从中选出 m 个座位即可。答案为 n-m+1 \choose m。
五、直线染色问题
有 n 个排成一排的物品，用 m 种颜色对其染色，要求相邻的颜色不同，求染色方法。
第一个物品可以用这 m 种颜色随意染色，而其他的物品可以用与它们上一个物品不同的 m-1 种颜色染色。由乘法原理可知一共有 n(m-1)^{n-1} 种染法。
六、环形染色问题
如图，用 m 种颜色给 n 个区域染色，要求相邻两区域颜色不同，求染色方法。
我们将 A_1 和 A_n 分开，将其变成一条直线，就转化为了第五种题型。我们记有 n 个区域时的染色方法有 a_n 种。
由加法原理，可知
a_n+a_{n-1}=m(m-1)^{n-1}
且有 a_2=m(m-1)。
由数列的知识可知答案为
a_n=(m-1)^n+(-1)^n(m-1)
七、传球问题
设共有 m 人传球，求传递 n 次后，球回到了发球人手中的方案数。
设答案为 a_n，我们知道，传递 n-1 次时，球不在发球人手中的方案数为 a_n。那么，此问题即为 n-1 个区域的环形染色问题。由环形染色问题的结论可知：
a_n=\frac{(m-1)^n}{m}+\frac{(-1)^n(m-1)}{m}
八、错位排列问题
将 n 个排好的元素重新排列，要求每个元素均与原位置不同，记这样的排列为 D_n。
一般地，我们有以下公式：
\begin{aligned}
D_n &= n!(\frac{1}{2!}-\frac{1}{3!}+\cdots+(-1)^n\frac{1}{n!})\\
&= n!\sum_{i=2}^n(-1)^i\frac{1}{i!}
\end{aligned}
现给出该公式的证明：
对于位置 1 上的原元素，可放与出位置 1 以外的 n-1 个位置种任一位置 k。此时，位置 k 上的原元素 a_k 有两种选择：
-
放于位置1，此时问题转化为除 a_1 和 a_k 外 n-2 个元素的错位排列问题。
-
放于除位置 1 和位置 k 之外的其他任一位置 m，此时省略元素 a_k 和位置 m，问题转化为 n-1 个元素的错位排列。
由加法、乘法原理，得
D_n=(n-1)(D_{n-1}+D_{n-2})
即
D_n-D_{n-1}=-1[D_{n-1}-(n-2)D_{n-2}]
结合数列相关知识，得
a_n-nD_{n-1}=(-1)^{n-3}(D_3-D_2)
易知 D_2=1,D_3=2
则
D_n-nD_{n-1}=(-1)^n
即
\frac{D_n}{n!}-\frac{D_{n-1}}{(n-1)!}=\frac{(-1)^n}{n!}
累加即得
\begin{aligned}
D_n &= n!(\frac{1}{2!}-\frac{1}{3!}+\cdots+(-1)^n\frac{1}{n!})\\
&= n!\sum_{i=2}^n(-1)^i\frac{1}{i!}
\end{aligned}
\square
Part 5 容斥原理与抽屉原理
一、容斥原理
设全集 U 中元素有 n 种不同的属性，而第 i 种属性为 P_i，拥有属性 P_i 的元素构成集合 S，那么
\begin{aligned}
\left|\bigcup_{i=1}^{n}S_i\right|=&\sum_{i}|S_i|-\sum_{i<j}|S_i\cap S_j|+\sum_{i<j<k}|S_i\cap S_j\cap S_k|-\cdots\\
&+(-1)^{m-1}\sum_{a_i<a_{i+1} }\left|\bigcap_{i=1}^{m}S_{a_i}\right|+\cdots+(-1)^{n-1}|S_1\cap\cdots\cap S_n|
\end{aligned}
二、抽屉原理
- 简单情况
将 n+1 个物体，划分为 n 组，那么有至少一组有两个（或以上）的物体。
证明考虑反证法：假如每个分组有至多 1 个物体，那么最多有 1\times n 个物体，而实际上有 n+1 个物体，矛盾。
- 推广
将 n 个物体，划分为 k 组，那么至少存在一个分组，含有大于或等于
推广的形式也可以使用反证法证明：若每个分组含有小于
$\left \lceil \dfrac{n}{k} \right \rceil$ 个物体，则其总和 $S\leq (\left \lceil \dfrac{n}{k} \right \rceil -1 ) \times k=k\left\lceil \dfrac{n}{k} \right\rceil-k < k(\dfrac{n}{k}+1)-k=n $ 矛盾。
此外，划分还可以弱化为覆盖结论不变。
给定集合 $S$, 一个 $S$ 的非空子集构成的簇 $\{A_1,A_2\ldots A_k\}$：
- 若满足 $\bigcup_{i=1}^k A_i$ 则称为 $S$ 的一个覆盖（cover）。
- 若一个覆盖还满足 $i\neq j\to A_i\cap A_j=\varnothing$ 则称为 $S$ 的一个划分。
抽屉原理可以有如下叙述：对于 $S$ 的一个覆盖 $\{A_1,A_2\ldots A_k\}$ 有至少一个集合 $A_i$ 满足 $\left\vert A_i \right\vert \geq \left\lceil \dfrac{\left\vert S \right\vert}{k} \right\rceil$。
### Part 6 斯特林数
**一、第二类斯特林数**
1. **定义：** 第二类斯特林数又称为斯特林子集数，记为 ${n\brace k}$，也记为 $S(n,k)$，表示将 $n$ 个互不相同的元素，划分为 $k$ 个互不区分的非空子集的方案数。
2. **递推式**
$$
{n\brace k}={n-1\brace k-1}+k{n-1\brace k}
$$
其边界条件为 ${n\brace 0}=\lbrack n=0\rbrack$。
**证明：**
我们考虑组合数的意义。
当我们插入一个新元素时，有两种方案：
- 将新元素单独放入一个子集，有 ${n-1\brace k-1}$ 种方案。
- 将新元素放入一个现有的非空子集，有 $k{n-1\brace k}$ 种方案。
由加法原理，将两式相加即可得到递推式。
$\square
- 通项公式
{n\brace m}=\sum_{i=0}^m\frac{(-1)^{m-i}i^n}{i!(m-i)!}
证明：
可以使用容斥原理。
设将 n 个两两不同的元素，划分到 i 个两两不同的集合（允许空集）的方案数为 G_i，将 n 个两两不同的元素，划分到 i 个两两不同的非空集合（不允许空集）的方案数为 F_i。
那么有
G_i=i^n\\
G_i=\sum_{j=0}^i{i\choose j}F_j
根据二项式反演
\begin{aligned}
F_i&=\sum\limits_{j=0}^{i}(-1)^{i-j}\binom{i}{j}G_j\\
&=\sum\limits_{j=0}^{i}(-1)^{i-j}\binom{i}{j}j^n\\
&=\sum\limits_{j=0}^{i}\dfrac{i!(-1)^{i-j}j^n}{j!(i-j)!}
\end{aligned}
考虑 F_i 与 n\brace i 的关系。第二类斯特林数要求集合之间互不区分，因此 F_i 正好是 n\brace i 的 i! 倍。于是有
{n\brace m}=\frac{F_m}{m!}=\sum_{i=0}^m\frac{(-1)^{m-i}i^n}{i!(m-i)!}
\square
- 同一行第二类斯特林数的计算
“同一行”的定义为对于相同的 n，求 \begin{Bmatrix}n\\i\end{Bmatrix}。也就是对 i=0\dots n 求出将 n 个不同元素划分为 i 个非空集的方案数。
我们可以根据上面的通项公式，使用卷积计算即可。其时间复杂度为 O(n\log n)。
限于本人能力，代码部分暂时先跳过。
二、第一类斯特林数
-
定义： 第一类斯特林数又称为斯特林轮换数，记为 \begin{bmatrix}n\\k\end{bmatrix}，也记为 s(n,k)，表示将 n 个互不相同的元素，划分为 k 个互不区分的非空轮换（圆排列）的方案数。
-
递推式
{n\brack k}={n-1\brack k-1}+(n-1){n-1\brack k}
其边界条件为 \begin{bmatrix}n\\0\end{bmatrix}=\lbrack n=0\rbrack。
证明：
仍然考虑组合数的意义。
当我们插入一个新元素时，有两种方案：
- 将新元素至于一个单独的轮换中,有 \begin{bmatrix}n-1\\k-1\end{bmatrix} 种方案。
- 将新元素插入到任何一个现有的轮换中，共有 (n-1)\begin{bmatrix}n-1\\k\end{bmatrix} 种方案。
根据加法原理，将两者相加即可得到递推式。\square
由于第一类斯特林数的用途并不广泛，我们仅作了解，不展开讲述。
三、自然幂、上升幂和下降幂的转换
1，定义
在本文的 \textsf{\textbf{Part 1}} 部分，我们已经对下降幂作出了定义，这里我们进行一个回顾。
自然幂： 记 n^m=\prod_{i=1}^mn 为 n 的 m 次幂。
下降幂： 记 n^{\underline{m}}=\prod_{i=0}^{m-1}(n-i)=n\cdot(n-1)\cdot(n-2)\cdots (n-m+1) 为 n 的 m 次下降幂。
上升幂： 记 n^{\overline{m}}=\prod_{i=0}^{m-1}(n+i)=n\cdot(n+1)\cdot(n+2)\cdots(n+m-1) 为 n 的 m 次上升幂。
- 上升幂与自然幂的相互转换
我们可以通过以下恒等式将上升幂转换为自然幂：
x^{\overline{n}}=\sum_k{n\brack k}x^k
而将自然幂转化为上升幂则有下面的恒等式：
x^n=\sum_k{n\brace k}(-1)^{n-k}x^k
- 下降幂与自然幂的相互转换
我们可以通过以下恒等式将下降幂转换为自然幂：
x^{\underline{n}}=\sum_k{n\brack k}(-1)^{n-k}x^k
联想到排列的定义，我们可以得到第一类斯特林数的一个性质：
A_n^m=n^{\underline{m}}=\sum_k{m\brack k}(-1)^{m-k}n^k
若要将自然幂转换为下降幂，有以下恒等式：
x^n=\sum_k{n\brace k}x^k
Part 7 范德蒙德卷积
一、定义
范德蒙德卷积是一种合并组合数的公式，主要用于组合数学的公式推导，其公式如下
\sum_{i=0}^k{n\choose i}{m\choose k-i}={n+m\choose k}
证明：
考虑二项式定理。
\begin{aligned}
\sum_{k=0}^{n+m}{n+m\choose k}x^k
&=(x+1)^{n+m}\\
&=(x+1)^n(x+1)^m\\
&=\sum_{r=0}^n{n\choose r}x^r\sum_{s=0}^m{m\choose s}x^s\\
&=\sum_{k=0}^{n+m}\sum_{r=0}^k{n\choose r}{m\choose k-r}x^k
\end{aligned}
化简后即得
{n+m\choose k}=\sum_{i=0}^k{n\choose i}{m\choose k-i}
\square
二、推论
- 推论一
\sum_{i=-r}^{s}\binom{n}{r+i}\binom{m}{s-i}=\binom{n+m}{r+s}
证明仅需将原证明的 i 从 -r 开始枚举即可。
- 推论二
\sum_{i=1}^n\binom{n}{i}\binom{n}{i-1}=\binom{2n}{n-1}
证明：
根据组合数的性质定理，有
\begin{aligned}
\sum_{i=1}^n{n\choose i}{n\choose i-1}
&=\sum_{i=0}^{n-1}{n\choose i+1}{n\choose i}\\
&=\sum_{i=0}^{n-1}{n\choose n-1-i}{n\choose i}\\
&={2n\choose n-1}
\end{aligned}
\square
- 推论三
\sum_{i=0}^n{n\choose i}^2={2n\choose n}
证明：
根据组合数的性质定理，易得
\begin{aligned}
\sum_{i=0}^n{n\choose i}^2&=\sum_{i=0}^n{n\choose n-i}\\
&={2n\choose n}
\end{aligned}
\square
- 推论四
\sum_{i=0}^m\binom{n}{i}\binom{m}{i}=\binom{n+m}{m}
证明：
\begin{aligned}
\sum_{i=0}^m{n\choose i}{m\choose i}&=
\sum_{i=0}^m{n\choose i}{m\choose m-i}\\
&={n+m\choose m}
\end{aligned}
\square