$$ \gdef\seq#1#2{{#1}_{1}, {#1}_{2}, \cdots, {#1}_{#2}} \gdef\num#1{1, 2, \cdots, #1} \gdef\stra#1#2{\begin{bmatrix} #1 \\ #2 \end{bmatrix}} \gdef\strb#1#2{\begin{Bmatrix} #1 \\ #2 \end{Bmatrix}} \gdef\dw#1{\underline{#1}} \gdef\up#1{\overline{#1}} $$

组合数

多重集的排列数

设 $S$ 由 $n_{i}(1 \le i \le k)$ 个 $a_{i}$ 组成，那么 $S$ 的全排列个数为：

$$ \binom{n}{\seq{n}{k}} = \frac{n!}{\prod_{i = 1} ^ {k} n_{i}!} $$

多重集的组合数

设 $S$ 由 $n_{i}(1 \le i \le k)$ 个 $a_{i}$ 组成，那么从 $S$ 中选择 $r$ 个元素组成的一个多重集的方案数可以用线性方程的解的个数来表示：

$$ \forall i \in [1, k], x_{i} \le n_{i}, \sum_{i = 1} ^ {k} x_{i} = r $$

当 $r \le n_{i}$ 时可以直接用插板法计算，否则可以用容斥原理计算。

不相邻的排列

一排 $n$ 个数中选择 $k$ 个使得这 $k$ 个数中两两不相邻的方案数为 $\dbinom{n - k + 1}{k}$ 种，可以直接插板法。

圆排列

$n$ 个人中选出 $m$ 个人围成一个圆的方案数为：

$$ \operatorname{Q}_{n}^{m} = \frac{\operatorname{A}_{n} ^ {m}}{m} $$

特殊地，当 $m = n$ 时，$\operatorname{Q}_{n} ^ {n} = (n - 1)!$。

组合数推论

对称性

$$ \binom{n}{m} = \binom{n}{n - m} $$

递推式

$$ \binom{n}{m} = \frac{n}{m}\binom{n - 1}{m - 1} \\ \binom{n}{m} = \binom{n - 1}{m} + \binom{n - 1}{m - 1} $$

二项式定理的特殊情况

$$ \sum_{i = 0} ^ {n} \binom{n}{i} = 2 ^ {n} \\ \sum_{i = 0} ^ {n} (-1) ^ {i} \binom{n}{i} = [n = 0] $$

拆组合数

$$ \sum_{i = 0} ^ {m} \binom{n}{i} \binom{m}{m - i} = \binom{n + m}{m} \\ \sum_{i = 0} ^ {n} \binom{n}{i} ^ 2 = \binom{2n}{n} \\ \sum_{i = 0} ^ {n} \binom{i}{m} = \binom{n + 1}{m + 1} $$

带权和

$$ \sum_{i = 0} ^ {n} i \binom{n}{i} = {\color{#C0C0C0}{\sum_{i = 0} ^ {n} \binom{i}{1} \binom{n}{i} = \sum_{i = 0} ^ {n} \binom{n}{1} \binom{n - 1}{i - 1}}} = n \cdot 2 ^ {n - 1} \\ \sum_{i = 0} ^ {n} i ^ {2} \binom{n}{i} = {\color{#C0C0C0}{n \sum_{i = 0} ^ {n} i \binom{n - 1}{i - 1} = n \sum_{i = 0} ^ {n - 1} (i + 1)\binom{n - 1}{i}}} = n(n + 1) \cdot 2 ^ {n - 2} $$

斐波那契数列

$$ \sum_{i = 0} ^ {n} \binom{n - i}{i} = F_{n + 1} $$

卡特兰数

通项公式

$$ H_{n} = \frac{\binom{2n}{n}}{n + 1} $$

递推式

$$ H_{n} = \begin{cases} \sum_{i = 1} ^ {n} H_{i - 1} H_{n - i} & n \ge 2 \\ 1 & n = 0, 1 \end{cases} $$

等价问题

  • 满足通项公式：

    1. 只包含 $1$ 和 $-1$ 的的序列 $\seq{a}{2n}$ 满足 $\forall k \in [1,2n], \sum_{i = 1} ^ {k} a_{i} \ge 0$ 的序列的方案数。
    2. 合法括号序列的方案数。
    3. 进栈序列 $\num{n}$ 的出栈序列的方案数。
    4. 用 $n$ 条不相交的线段连接圆上 $2n$ 个点的方案数。

  • 满足递推式：

    1. 大小为 $n$ 的二叉树的方案数。
    2. 凸 $n$ 边形三角划分的方案数。

斯特林数

定义

第一类斯特林数：$\stra{n}{m}$ 表示将 $n$ 个有序的球排成 $m$ 个无序的非空循环的方案数。

第二类斯特林数：$\strb{n}{m}$ 表示将 $n$ 个有序的球放入 $m$ 个无序的非空盒子的方案数。

递推式

$$ \begin{aligned} \stra{n}{m} & = \stra{n - 1}{m - 1} + (n - 1) \stra{n - 1}{m} \\ \strb{n}{m} & = \strb{n - 1}{m - 1} + m \strb{n - 1}{m} \end{aligned} $$

通项公式

$$ \strb{n}{m} = \frac{1}{m!}\sum_{i = 0} ^ {m} (-1) ^ {m - i} \binom{m}{i} i ^ {n} $$

证明：考虑容斥和组合意义。

性质

阶乘 - 第一类斯特林数

$$ n! = \sum_{i = 0} ^ {n} \stra{n}{i} $$

证明：一个排列唯一对应了一个置换。

整数幂 - 第二类斯特林数、下降幂

$$ x ^ {n} = \sum_{i = 0} ^ {n} \strb{n}{i} x ^ {\dw{i}} $$

证明：组合意义为 $n$ 个有序球放在 $x$ 个有序可为空的盒子里。

下降幂 - 第一类斯特林数、整数幂

$$ x ^ {\dw{n}} = \sum_{i = 0} ^ {n} (-1) ^ {n - i} \stra{n}{i} x ^ {i} \\ $$

证明：数学归纳法。

$$ \begin{aligned} x ^ {\dw{n + 1}} & = (x - n) x ^ {\dw{n}} \\ & = \sum_{i = 0} ^ {n} (-1) ^ {n - i} \stra{n}{i} x ^ {i + 1} - n \sum_{i = 0} ^ {n} (-1) ^ {n - i} \stra{n}{i} x ^ {i} \\ & = \sum_{i = 1} ^ {n + 1} (-1) ^ {n + 1 - i} \stra{n}{i - 1} x ^ {i} + n \sum_{i = 0} ^ {n} (-1) ^ {n + 1 - i} \stra{n}{i} x ^ {i} \\ & = \sum_{i = 1} ^ {n + 1} (-1) ^ {n + 1 - i} \left( \stra{n}{i - 1} + n \stra{n}{i} \right) x ^ {i} \\ & = \sum_{i = 0} ^ {n + 1} (-1) ^ {(n + 1) - i} \stra{n + 1}{i} x ^ {i} \end{aligned} $$

上升幂 - 第一类斯特林数、整数幂

$$ x ^ {\up{n}} = \sum_{i = 0} ^ {n} \stra{n}{i} x ^ i $$

证明：和「下降幂 - 第一类斯特林数、整数幂」的式子本质相同。

整数幂 - 第二类斯特林数、上升幂

$$ x ^ {n} = \sum_{i = 0} ^ {n} (-1) ^ {n - i} \strb{n}{i} x ^ {\up{i}} $$

证明：和「整数幂 - 第二类斯特林数、下降幂」的式子本质相同。

斯特林反演

基本公式

$$ \sum_{i = 0} ^ {n} \stra{n}{i} \strb{i}{m} (-1) ^ {n - i} = [n = m] \\ \sum_{i = 0} ^ {n} \strb{n}{i} \stra{i}{m} (-1) ^ {n - i} = [n = m] $$

证明：

反演公式 1

$$ \begin{aligned} g(n) & = \sum_{i = 0} ^ {n} \strb{n}{i} f(i) \\ f(n) & = \sum_{i = 0} ^ {n} (-1) ^ {n - i} \stra{n}{i} g(i) \end{aligned} $$

证明：

$$ \begin{aligned} f(n) & = \sum_{i = 0} ^ {n} f(i) [n = i] \\ & = \sum_{i = 0} ^ {n} f(i) \sum_{j = 0} ^ {n} \stra{n}{j} \strb{j}{i} (-1) ^ {n - j} \\ & = \sum_{i = 0} ^ {n} (-1) ^ {n - i} \stra{n}{i} \sum_{j = 0} ^ {n} \strb{i}{j} f(j) \\ & = \sum_{i = 0} ^ {n} (-1) ^ {n - i} \stra{n}{i} g(i) \end{aligned} $$

反演公式 2

$$ \begin{aligned} g(n) & = \sum_{i = 0} ^ {n} \stra{n}{i} f(i) \\ f(n) & = \sum_{i = 0} ^ {n} (-1) ^ {n - i} \strb{n}{i} g(i) \end{aligned} $$

证明：

$$ \begin{aligned} f(n) & = \sum_{i = 0} ^ {n} f(i) [n = i] \\ & = \sum_{i = 0} ^ {n} f(i) \sum_{j = 0} ^ {n} \strb{n}{j} \stra{j}{i} (-1) ^ {n - j} \\ & = \sum_{i = 0} ^ {n} (-1) ^ {n - i} \strb{n}{i} \sum_{j = 0} ^ {n} \stra{i}{j} f(j) \\ & = \sum_{i = 0} ^ {n} (-1) ^ {n - i} \strb{n}{i} g(i) \end{aligned} $$

快速求斯特林数 - 行

第一类斯特林数

上升幂的系数即为第一类斯特林数的某一行：

$$ x ^ {\up{n}} = \sum_{i = 0} ^ {n} \stra{n}{i} x ^ i $$

第二类斯特林数

利用通项公式构造卷积形式即可。

最后修改：2022 年 06 月 12 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏