本文是[算法竞赛入门] 容斥原理与组合计数 (蒋炎岩)的学习笔记.

大家都会的计数问题 #

枚举基本定理 #

$$ \vert A\vert =\sum_{a\in A}1 $$

• 解释了加法和乘法的本质, 枚举基本定理可以推导出加法/乘法原理
• $\sum$ 是 “求和程序”
• 提示我们寻找 $A\mapsto B$ 的一一映射, 如果有这个映射, 那么有 $\vert A\vert = \vert B\vert$

计数的本质 #

计数的本质是集合的生成(枚举). $$ \vert A\vert =\sum_{a\in A}1 $$

扩展到两个集合:

• 加法原理: $\vert A\cup B\vert = \vert A\vert +\vert B\vert$ , 当 $A\cap B=\emptyset$ 时成立
• 乘法原理: $\vert A\times B\vert = \vert A\vert \cdot\vert B\vert$

二进制串计数 #

Case 0 #

$n-bit$ 二进制串一共有多少个?

• $2^n$ (乘法原理)

实际上, 我们的大脑帮忙处理了一些过程:

• 集合划分, 考虑第一位可以分成 $0$ 和 $1$ , 之后的 $n - 1$ 位可以两两对应, 这两个子集是大小是一样的, 因此有 $f(n) = 2f(n - 1)$ , 边界情况 $f(0) = 1$ .

Case 1 #

$n-bit$ 二进制串中 $0$ 比 $1$ 多的一共有多少个?

从集合的角度思考, 同样考虑第一位是 $0$ 还是 $1$ , 先把集合划分成两个子集 $A_0, A_1$. 可以发现, $A_0$ 中每个 $0$ 比 $1$ 多的二进制串, 都对应着 $A_1$ 中的一个 $1$ 比 $0$ 多的二进制串 (按位取反即可) . 记$0$ 比 $1$ 多的二进制串数量为 $f(n)$ , $0$ 和 $1$ 数量相同的二进制串为 $g(n)$ , 可以得到这样的恒等式: $$ 2f(n) + g(n) = 2^n $$

如果直接枚举 $0$ 的数量, 由加法原理, 我们可以得到: $$ f(n) = \sum_{k = \lfloor\frac{n}{2}+1\rfloor}^{n}C_{n}^{k} $$

这样我们在解决问题之外, 还可以得到一个关于组合数的恒等式.

Case 2 #

如果把 $0$ 看作 $($ , $1$ 看作 $)$ ,配对的括号序列有多少个?

首先 $n$ 为奇数时不存在配对的括号序列, 我们下面讨论基于 $n$ 为偶数的假设. 同样地, 先写出集合. 这里我们考虑长度为 $n$ 的配对序列集合, 记集合大小为 $f(n)$ . 接下来, 寻找一种划分集合的方式. 每个配对序列的最左侧一定是一个 $($ , 它会与某个 $)$ 配对, 我们考虑 $)$ 的位置. 显然, $)$ 可以在左起任意偶数位置上. 考虑这个配对部分的长度, 设为 $k$ , 则 $k$ 内部长度为 $k - 2$ 的部分是一个配对序列, 有 $f(k - 2)$ 种, 而右侧剩余的长度为 $n - k$ 的序列同样是一个配对序列, 有 $f(n - k)$ 种. 基于加法与乘法原理, 我们有 $$ f(n) = \sum_{k = 2}^{n}f(k - 2)\cdot f(n - k) $$

考虑另外一种映射处理: 有一个二维坐标系中的计数器, 遇到 $0$ 则 $+1$ , 遇到 $1$ 则 $-1$ , 则这个计数器应当是从 $(0, 0)$ 出发, 最后落在 $(n, 0)$ , 且从未到达过第四象限. $f(n)$ 就是满足该条件的折线段数量. 因为不能到达第四象限, 也就是折线段与 $y = -1$ 没有交点. 现在考虑不满足条件的折线段, 这些折线段与 $y = -1$ 有交点, 将交点右侧折线段沿 $y = -1$ 翻折, 则终点变为 $(n, -2)$ , $(0, 0)$ 到 $(n, 0)$ 的每一条不合法的折线段都与 $(0, 0)$ 到 $(n, -2)$ 的某条折线段对应. 故合法折线段数量 $f(n) = C_{n}^{\frac{n}{2}} - C_{n}^{\frac{n}{2} - 1}$ .

$f(n)$ 有一个名称, 叫做卡特兰数 (Catalan number) .

排列计数 #

Case 0 #

求 $1, 2, …, n$ 的所有排列的数量.

• $n!$

从集合的角度, 考虑所有的排列, 按照第一个元素划分子集为 $A_1, A_2, …, A_n$ , 除了第一个元素, 各个子集后面的排列一一对应, 故有 $f(n) = n\cdot f(n - 1)$ , 边界情况 $f(0) = 1$ .

考虑一个另外一种划分方式, 先把 $n$ 个数划分成 $k$ 和 $n - k$ 两组数. 两组数可以分别排列, 再组合成一个新的排列. 对于 $k$ 个数的一个排列, 和 $n - k$ 的一个排列, 考虑这两个排列怎么组合, 由于顺序两个子排列顺序已经固定, 我们可以抽象地把看成 $k$ 个红球和 $n - k$ 的蓝球的组合, 记这个组合数为 $C_{n}^{k}$ , 则有 $n! = k!\cdot (n - k)!\cdot C_{n}^{k}$ , 这样我们推导出了组合数: $$ C_{n}^{k} = \frac{n!}{k!\cdot (n - k)!} $$ 需要注意的是这里集合的划分对于每个 $k$ 都成立, 但不能应用加法公式, 因为这些划分交集非空.

Case 2 #

错位排列: $1, 2, …, n$ 的所有排列中, 每个数字都不在原位的排列的数量.

从集合的角度, 考虑所有的排列, 按照第一个元素划分子集为 $A_1, A_2, …, A_n$ . 第一个元素有 $n - 1$ 种可能, $A_i$ 中排列的后 $n - 1$ 个数构成的排列集合可以建立一一对应 (都是 $n - 2$ 个有对应位置的数与 $1$ 个没有对应位置的数构成的错排) . 因此我们可以得到 $f(n) = (n - 1)\cdot g(n - 1)$ . 与上一个问题不同的是, $g(n - 1)$ 并不是一个更小情况的 $f(n)$ , 没有简单的递归关系, 但我们直觉上可以感觉到 $g(n)$ 是一个近似的错排问题. 同样对 $g(n - 1)$ 的集合分类, 我们取没有对应位置的元素 (即 $1$ ) 是否在缺乏对应元素的位置 (不妨设为 $2$ ) 为划分标准. 假如 $1$ 填补了这个空缺, 那么剩余 $n - 2$ 个元素构成了一个错排, 恰好是 $f(n - 2)$ ; 假如 $1$ 没有填补这个空缺, 那么把这个位置替换成 $1$ 对问题不构成影响, 此时恰好是 $n - 1$ 个元素构成的错排. 因此 $g(n - 1) = f(n - 1) + f(n - 2)$ , 最终我们有 $$ f(n) = (n - 1)\cdot (f(n - 1) + f(n - 2)) $$

边界情况是 $f(0) = 1$ .

容斥原理 #

集合视角的计数 #

加法原理: $$ \vert A\cup B\vert = \vert A\vert + \vert B\vert $$

成立条件: $A\cap B = \emptyset$ 加法原理允许我们把集合拆成不相交的子集来计数.

如果 $A, B$ 存在关联, 能不能求解?

• 求 $1, 2, …, 100$ 中有多少数能被 $2$ 或 $3$ 整除?
  • $A$ 是能被 $2$ 整除的数构成的集合, $B$ 是能被 $3$ 整除的数构成的集合, $A\cap B$ 是能被 $6$ 整除的数构成的集合, 那么 $|A\cup B| = |A| + |B| - |A\cap B|$ .

求交容易, 求并难 #

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

许多问题都有 “交比并简单” 的性质.

• 凸多边形的交 v.s. 并
  • 任意两个凸多边形的交还是一个凸多边形

忘掉容斥原理, 考虑如下的方程组: $$ \begin{pmatrix} x_0\ x_1\ x_2\ x_3\ x_4\ x_5\ x_6\ x_7 \end{pmatrix} \begin{pmatrix} \vert\emptyset\vert\ \vert A\vert\ \vert B\vert\ \vert C\vert\ \vert A\cap B\vert\ \vert A\cap C\vert\ \vert B\cap C\vert\ \vert A\cap B\cap C\vert\ \end{pmatrix} =\vert A\cup B\cup C\vert\ $$

从单个元素的集合角度思考, 例如对于 $e\in A, e\not \in B, e\not \in C$ , 可以得到 $$ \begin{pmatrix} x_0\ x_1\ x_2\ x_3\ x_4\ x_5\ x_6\ x_7 \end{pmatrix} \begin{pmatrix} 0\ 1\ 0\ 0\ 0\ 0\ 0\ 0\ \end{pmatrix} =1\ $$

类似地, 选取不同的 $e$ , 我们可以 “解出” 容斥原理. 知道这一点对的好处在于, 容斥原理的具体形式完全可以交给计算机来求解.

容斥原理 (Principle of Inclusion and Exclusion) #

用若干个集合 “覆盖” 一个不规则的集合, 即可化并为交. $$ \vert \bigcup_{i = 1}^{n}A_i\vert = \sum_{\emptyset \not ={I\subseteq[n]}}(-1)^{\vert I\vert + 1}\vert \bigcap_{i\in I}A_i\vert $$

容 (Inclusion)

• $(-1)^{\vert I\vert + 1} = 1\Rightarrow \vert I\vert \in 1, 3, 5, 7, …$

斥 (Exclusion)

• $(-1)^{\vert I\vert + 1} = -1\Rightarrow \vert I\vert \in 2, 4, 6, 8, …$

什么问题求交容易, 求并难? #

求错位排列: $1, 2, …, n$ 的所有排列中, 每个数字都不在原位的排列的数量.

例子: $n = 4$

• $A, B, C, D$ 表示 $1, 2, 3, 4$ 恰好在第 $1, 2, 3, 4$ 个位置的排列;
• $n! - \vert A\cup B\cup C\cup D\vert$ 就是答案.
  • $\vert A\vert = (n - 1)!$
  • $\vert A\cap B\vert = (n - 2)!$
  • $\vert A\cap C\cap D\vert = (n - 3)!$
  • …

通过容斥原理, 我们能够直接得到错排数公式: $$ D_n = n!C_{n}^{0} - (n - 1)!C_{n}^{1} + (n - 2)!C_{n}^{2} - (n - 3)!C_{n}^{3} + … $$

容斥原理为什么是原理? #

“集合” 和 “并” 是非常具有一般性的结构.

例子: $\phi(n)$ 是 $1, 2, …, n$ 中与 $n$ 互质的数的数量

• 如何求 $\phi(n)$ ?
• $\phi$ 和 $\mu$ 的关系?
  • $\mu(n) = (-1)^k$ (如果 $n$ 是 $k$ 个素数的乘积)
  • $\mu(n) = 0$ (如果 $p^2$ 整除 $n$)
  • 例子: $n = 5\times 7\times 13$
    • 把 “互质” 这一关系取反, “不互质” $\Rightarrow$ “公因数”
    • $A = {5, 10, 15, …, n}$
    • $B = {7, 14, 21, …, n}$
    • $C = {13, 26, 39, …, n}$
    • $\vert A\cup B\cup C\vert = \frac{n}{5} + \frac{n}{7} + \frac{n}{13} - \frac{n}{5\cdot 7} - \frac{n}{5\cdot 13} - \frac{n}{7\cdot 13} + \frac{n}{5\cdot 7\cdot 13}$
    • 在利用容斥原理写出的求和式的形式里, 所有分母都是 $n$ 的约数, 同时每个质因子在分母里只出现一次; 那些拥有重复质因子的约数则没有出现在求和式中, 也就是系数为 $0$ .

利用容斥原理写出的求和式, 恰好就是莫比乌斯反演的形式: $$ \phi(n) = \sum_{d\mid n}\mu(d)\frac{n}{d} $$

更一般地, 有 $$ g(A) = \sum_{S\subseteq A}f(S)\Rightarrow f(A) = \sum_{S\subseteq A}\mu(A - S)g(S) $$