50.组合数学

组合数学

容斥原理

容斥原理的简单形式，设 $A$ 和 $B$ 是分别具有性质 $P_{1}$ 和 $P_{2}$ 的有限集，有

A \cup B = | A | + | B | - | A \cap B |

e.g. 求正整数 $1$ 到 $n$ 中，既不是 $2$ 的倍数也不是 $3$ 的倍数的数的个数

设 $S = {1, 2, \dots, n}$ ， $A$ 是 $2$ 的倍数， $B$ 是 $3$ 的倍数，那么答案就是 $| S | - | A \cup B |$

由于 $| A \cup B | = | A | + | B | - | A \cap B |$ ，所以答案就是 $n - ⌊ \frac{n}{2} ⌋ - ⌊ \frac{n}{3} ⌋ + ⌊ \frac{n}{6} ⌋$

e.g. 求由 $n$ 个元素 $1, 2, \dots, n$ 全排列中，满足 $1$ 和 $2$ 不相邻， $3$ 和 $4$ 不相邻的排列数

设 $A$ 是 $1$ 和 $2$ 相邻， $B$ 是 $3$ 和 $4$ 相邻，那么答案就是 $n! - | A \cup B |$

所以答案就是 $n! - 2 (n - 1)! - 2 (n - 1)! + 4 (n - 2)!$

考虑三个子集的容斥原理

| A \cup B \cup C | = | A | + | B | + | C | - | A \cap B | - | A \cap C | - | B \cap C | + | A \cap B \cap C |

推广到 $n$ 个集合

设 $S$ 是一个有限集， $A_{1}, A_{2}, \dots, A_{n}$ 是 $S$ 的 $n$ 个子集，那么

| A_{1} \cup A_{2} \cup \dots \cup A_{n} | = \sum_{i = 1}^{n} (- 1)^{i - 1} \sum_{1 \leq j_{1} < j_{2} < \dots < j_{i} \leq n} | A_{j_{1}} \cap A_{j_{2}} \cap \dots \cap A_{j_{i}} |

我们对答案取补集的形式也很常见：

S - | A_{1} \cup A_{2} \cup \dots \cup A_{n} | = \sum_{i = 0}^{n} (- 1)^{i} \sum_{1 \leq j_{1} < j_{2} < \dots < j_{i} \leq n} | A_{j_{1}} \cap A_{j_{2}} \cap \dots \cap A_{j_{i}} |

这里需要定义 $| \cap \emptyset | = S$

e.g. $m$ 件不同的物品，分配给 $n$ 个人，要求每个人至少要分得一件物品，求不同的分配方案数

设 $S =$ 总方案数， $A_{i} =$ 第 $i$ 个人没有分到物品的方案数

答案就是

S - | A_{1} \cup A_{2} \cup \dots \cup A_{n} | = \sum_{i = 0}^{n} (- 1)^{i} \sum_{1 \leq j_{1} < j_{2} < \dots < j_{i} \leq n} | A_{j_{1}} \cap A_{j_{2}} \cap \dots \cap A_{j_{i}} |

$| A_{j_{1}} \cap A_{j_{2}} \cap \dots \cap A_{j_{i}} |$ 就是 $n - i$ 个人分配 $m$ 件物品的方案数，即 $C (n, n - i) \times (n - i)^{m} = C (n, i) \times (n - i)^{m}$

得到了答案的递推式：

\sum_{i = 0}^{n} (- 1)^{i} C (n, i) \times (n - i)^{m}

e.g. 错排问题： $p$ 是一个排列，满足 $p_{i} \neq i$ 的数的个数称为错排数，求错排数

设 $S$ 是所有排列数， $A_{i}$ 是 $i$ 不在 $p_{i}$ 的位置的排列数

| S - \cup_{i = 1}^{n} A_{i} | = \sum_{i = 0}^{n} C_{n}^{i} (n - i)!

容斥原理的符号形式

设 $S$ 是一个有限集， $a_{1}, a_{2}, \dots, a_{n}$ 是 $n$ 种性质

记 $N (a_{i})$ 为 $S$ 中有 $a_{i}$ 性质的元素的数量。特殊的，记 $N (1) = | S |$
记 $N (1 - a_{i})$ 为 $S$ 中没有 $a_{i}$ 性质的元素的数量
$N (a_{i_{1}}, a_{i_{2}}, \dots, a_{i_{k}})$ 为 $S$ 中同时有 $a_{i_{1}}, a_{i_{2}}, \dots, a_{i_{k}}$ ，性质的元素的数量
记 $N (a + b) = N (a) + N (b)$

通过符号形式，我们可以把容斥原理改成多项式来处理

则，容斥原理可以写成：

N ((1 - a_{1}) (1 - a_{2}) \dots (1 - a_{n})) = \sum_{i = 0}^{n} (- 1)^{i} \sum_{1 \leq j_{1} < j_{2} < \dots < j_{i} \leq n} N (a_{j_{1}}, a_{j_{2}}, \dots, a_{j_{i}})

e.g. 求正整数 $1$ 到 $n$ 中，既不是 $2$ 的倍数，也不是 $3$ 的倍数，但是 $5$ 的倍数的数的数量

设 $a_{1}$ 设 $2$ 的倍数， $a_{2}$ 是 $3$ 的倍数， $a_{3}$ 是 $5$ 的倍数

答案就是 $N ((1 - a_{1}) (1 - a_{2}) a_{3}) = N (a_{3} - a_{1} a_{3} - a_{2} a_{3} + a_{1} a_{2} a_{3})$

特殊的数

Catalan 数

Catalan 数有三种计算公式

公式 $1$ ：

C_{n} = \frac{1}{n + 1} (\binom{2 n}{n}) = (\binom{2 n}{n}) - (\binom{2 n}{n + 1}) = (\binom{2 n}{n}) - (\binom{2 n}{n - 1})

公式 $1$ 可以从一个基本模型推导出来：把 $n$ 个 $1$ 和 $n$ 个 $0$ 排成一行，使这一行的任意 $k$ 个数中 $1$ 的数量总是大于或等于 $0$ 的数量，这样的排列一共有 $C_{n}$ 个

公式 $2$ ：

C_{n} = \sum_{k = 0}^{n} C_{k} C_{n - 1 - k}, C_{0} = 1

公式 $3$ ：

C_{n} = \frac{4 n - 2}{n + 1} C_{n - 1}

模型 1：棋盘问题

一个 $n$ 行 $n$ 列的棋盘，从左上角走到右上角，一直在对角线右下方走，不穿过主对角线，走法有多少种？

对方向编号，向上为 $0$ ，向右为 $1$ ，那么从左下角到右上角一定会经过 $n$ 个 $1$ 和 $n$ 个 $0$ ，如果第 $k$ 步之前 $0$ 的个数超过 $1$ 的个数了，就说明一定超过对角线了

从左下角到右上角的路线方案总共有 $3$ 种：

A ：在对角线下方的方案数
B ：在对角线上方的方案数
C ：穿过对角线的方案数

显然， $(\binom{2 n}{n}) = A + B + C$ ，现在的问题转化成如何求 $B + C$

我们需要找一条穿过对角线或者完全在对角线上方的路线，然后按照一条虚线映射

我们发现，一条穿过对角线的路线和新路线是一一对应的，而新路线的方案数是 $(\binom{2 n}{n + 1}) = (\binom{2 n}{n - 1})$ ，从 $2 n$ 个里面选 $n + 1$ 个 $0$ ，选 $n - 1$ 个 $1$

所以 $C_{n} = (\binom{2 n}{n}) - (\binom{2 n}{n - 1})$

使用生成函数推导

根据递推公式：

C_{n} = \sum_{k = 0}^{n} C_{k} C_{n - 1 - k}

定义生成函数 $f (x) = \sum_{n = 0}^{\infty} C_{n} x^{n}$ ，那么：

\begin{aligned} C (x) & = \sum_{n \geq 0} C_{n} x^{n} \\ = 1 + x + x \sum_{n \geq 1} \sum_{i = 0}^{n} C_{i} C_{n - 1} x^{n} \\ = 1 + x + x (C (x)^{2} - 1) \\ = 1 + x C^{2} (x) \end{aligned}

考虑类似于实数的二次方程，解得：

C (x) = \frac{- 1 + \sqrt{1 - 4 x}}{2 x}

其中：

\begin{aligned} (1 - 4 x)^{\frac{1}{2}} & = \sum_{n = 0}^{\infty} (\binom{\frac{1}{2}}{n}) (- 4)^{n} x^{n} \\ = \sum_{n \geq 0} \frac{\frac{1}{2} (\frac{1}{2} - 1) (\frac{1}{2} - 2) \dots (\frac{1}{2} - n + 1)}{n!} (- 4)^{n} x^{n} \end{aligned}

所以：

C (x) = - \sum_{n \geq 0} \frac{\frac{1}{2} (\frac{1}{2} - 1) (\frac{1}{2} - 2) \dots (\frac{1}{2} - n)}{(n + 1)!} (- 4)^{n} x^{n}

\begin{aligned} C (x) & = \frac{\frac{1}{2} (\frac{1}{2} - 1) (\frac{1}{2} - 2) \dots (\frac{1}{2} - n)}{(n + 1)!} (- 4)^{n} \\ = - \frac{\frac{1}{2} (- \frac{1}{2}) (- \frac{3}{2}) \dots (- \frac{2 n - 1}{2}) \cdot 1 \cdot 2 \dots n}{(n + 1)! (n)!} (- 4)^{n} \\ = \frac{1 \cdot 3 \cdot 5 \dots 2 n - 1 \cdot 2 \cdot 4 \dots 2 n}{(n + 1)! n!} \\ = \frac{(2 n)!}{(n + 1)! n!} = \frac{1}{n + 1} (\binom{2 n}{n}) \end{aligned}

斯特林数

第二类斯特林数

考虑一个问题：

有 $n$ 个互不相同的求球，放到 $k$ 个互不区分的盒子里，每个盒子里至少要有一个球，球方案数

用动态规划来解决这个问题

f (n, k) = k f (n - 1, k) + f (n - 1, k - 1)

我们定义 $f (n, k)$ 为第二类斯特林数，记作 $S_{2} (n, k)$ ，这种方法的时间复杂度为 $O (n k)$

考虑用容斥原理求出 $O (k \log n)$ 的递推式

先把盒子按照 $1 \sim k$ 编号，设 $a_{i}$ 表示第 $i$ 个盒子没有球，答案就是

N ((1 - a_{1}) \dots (1 - a_{k})) = \sum_{i = 0}^{k} (- 1)^{i} (\binom{k}{i}) (k - i)^{n} = S_{2} (n, k) \times k!

则我们能得到第二类斯特林数的通项公式

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

第二类斯特林数还有一个重要的公式

n^{m} = \sum_{k = 0}^{m} {\binom{m}{k}} n^{\underset{―}{k}}

可以思考组合意义来理解，把 $m$ 个相互区分的球放到 $n$ 个相互区分盒子里面，朴素的方法就是 $n^{m}$

我们可以先去 $k$ 个盒子放球，要求每个盒子中至少有一个球，这个的方案数就是 $C_{n}^{k} S_{2} (m, k) k! = S_{2} (m, k) n^{\underset{―}{k}}$

第二类斯特林数有关于 $n$ 的指数生成函数

\sum_{n \geq 0} S_{2} (n, k) \frac{x^{n}}{n!} = \frac{1}{k!} (\exp (x) - 1)^{k}

这样就可以求一行的斯特林数，就是 $n$ 固定

我们有

{\binom{n}{k}} = \frac{1}{k!} \sum_{i = 0}^{k} (- 1)^{i} (\binom{k}{i}) (k - i)^{n} = \sum_{i = 0}^{k} (- 1)^{i} \frac{1}{i!} \times \frac{1}{(k - i)!} (k - 1)^{n}

设 $f (x) = \sum_{i = 0}^{n} (- 1)^{i} \frac{1}{i!} x^{i}, g (x) = \sum_{j = 0}^{n} \frac{1}{j!} j^{n}$

所以

{\binom{n}{k}} = [x^{k}] f (x) \cdot g (x)

总时间复杂度为 $O (n \log n)$

分拆数

$n$ 个无标号的球分配到 $k$ 和无标号的盒子的方案数，每个盒子不为空，记为 $p (n, k)$

有递推关系

p (n, k) = p (n - 1, k - 1) + p (n - k, k)

构造一种排列方式，一共有 $k$ 行，每一行的球的数量都比上一行少，每一列考虑：

如果最后一行只有一个球 $p (n - 1, k - 1)$
如果最后一行不止一个球 $p (n - k, k)$

关于 $n$ 的常生成函数： $\sum_{n \geq 0} p (n, k) x^{n} = x^{k} \prod_{i = 1}^{k} \frac{1}{1 - x^{i}}$

如何快速求 $p (n, k)$ ：先取 ln 再 exp

$n$ 个无标号的球分配到一些无编号盒子，每个盒子不为空的方案数，记为 $p (n)$

有 $p (n) = \sum_{k = 1}^{n} p (n, k)$

递推关系

p (n) = \sum_{k \geq 1} (- 1)^{k - 1} (p (n - \frac{3 k^{2} - k}{2}) + p (n - \frac{3 k^{2} + k}{2}))

常生成函数

\sum_{n \geq 0} p (n) x^{n} = \prod_{i \geq 1} \frac{1}{1 - x^{i}}

这个表展示了一些经典的分配问题