组合计数·基本理论
lihongru
·
·
算法·理论
第一节 计数原理
加法原理
若完成 A \to B 有 x 种方案一，有 y 种方案二，则完成 A \to B 的总方案数为 x + y。
要么选 x 种中的一种，有 x 种方案；要么选 y 种中的一种，有 y 种方案。因此总方案数为 x + y 种。同步之间用加法。
乘法原理
若完成 A \to B 有 x 种方案，完成 B \to C 有 y 种方案，则完成 A \to B \to C 有 xy 种方案。
对于 A \to B 的 x 种方案中的每一种，下一步 B \to C 都可选 y 种中的一种，所以总方案数为 xy 种。异步之间用乘法。
排列数
排列数用于解决 n 个相互区分的物品中选出 m 个排成一横排（区分顺序）的方案数。
考虑 m 个位置的每个位置：第一个位置可放 n 个物品，第二个位置可放 n - 1 个物品（已经选出一个，但选出的这一个是哪一个并不重要，因为无论选出的是哪一个，依然还剩 n - 1 个物品）……最后一个位置可以放 n - m + 1 个物品。
根据上面的加法原理和乘法原理，我们总结出排列数 A^m_n = n(n-1) \cdots (n - m + 2)(n - m + 1)。若 n < m 或 m < 0，A^m_n = 0。
记 n 的阶乘 n! 为 A^n_n，特殊地，0!=1。它一般的意义是 1 \sim n 的数的排列数。所以组合数 A^m_n 也可写成 \frac{n!}{(n-m)!}。
第二节 组合数
记 C^m_n 或 \binom{n}{m} 为在 n 个物品中选出 m 个物品（不区分顺序）的方案数。若 n < m 或 m < 0，\binom{n}{m} = 0，否则：
\binom{n}{m} = \frac{n!}{m!(n-m)!}
我们可以用排列数来理解组合数公式。首先从 n 个里选 m 个，区分顺序时为 A^m_n = \frac{n!}{(n-m)!}。然后如果不想区分顺序了，我们需要除以所有 1 \sim m 的排列，即为 m!。
或是理解为先将 n 个物品排列，取前 m 个，前面 m 个重复了 m! 次，后面还有 n - m 个重复了 (n - m)! 次。
组合数有递推式：
\binom{n}{m} = \binom{n - 1}{m - 1} + \binom{n - 1}{m}
我们可以用数学推导理解：\binom{n - 1}{m - 1} + \binom{n - 1}{m} = \frac{(n-1)!}{(m-1)!(n-m)!} + \frac{(n-1)!}{m!(n-m-1)!} = \frac{(n-1)!}{m!(n-m)!}(m + (n - m)) = \frac{n!}{m!(n-m)!} = \binom{n}{m}。
中间一步加法，使用通分的方法进行变形。
也可以用组合意义理解：我们指定其中一个物品，如果选，那么有 \binom{n - 1}{m - 1} 种方案（在剩下的 n-1 个选 m-1 个），如果不选，那么有 \binom{n - 1}{m} 种方案（在剩下 n-1 个选 m 个）。
第三节 范德蒙德卷积
\sum^{k}_{i=0}\binom{n}{i}\binom{m}{k-i} = \binom{n + m}{k}
用组合意义可以很轻松地理解这个问题：n 个红球和 m 个蓝球，在这 n + m 个中选出 k 个。
还有一个很常用的式子：
\sum^{n}_{i=0}\binom{n}{i}^2= \sum^{n}_{i=0}\binom{n}{i}\binom{n}{n-i} = \binom{2n}{n}
第四节 组合数计算
递推
已证，可用递推式：
\binom{n}{m} = \binom{n - 1}{m - 1} + \binom{n - 1}{m}
解决 n \le 5 \times 10^3 时的组合数计算。时间复杂度 O(n^2)。
逆元
在组合数计算时，一般会要求结果对某个数 p（一般是质数）取余数，因为结果实在太大了。
记 x^{-1} 为满足 x \cdot x^{-1} \equiv 1 \pmod p 的数，即为 x 的逆元。则组合数公式变为：
\binom{n}{m} = n! \cdot (m!)^{-1} \cdot ((n-m)!)^{-1}
所以我们需要预处理阶乘和阶乘的逆元。
Ⅰ 利用线性求逆元
有：
x^{-1} = -\lfloor\frac{p}{x}\rfloor \cdot (p \bmod x)^{-1}
证明：因为 p = \lfloor \frac{p}{x}\rfloor \cdot x + (p \bmod x)，所以 p \bmod x \equiv -\lfloor\frac{p}{x}\rfloor \pmod p，得出 x^{-1} = -\lfloor\frac{p}{x}\rfloor \cdot (p \bmod x)^{-1}。
再利用 (n!)^{-1}=((n-1)!)^{-1} \cdot n^{-1} 直接求出阶乘的逆元。
Ⅱ 利用可递推性正反求逆元
有：
(n!)^{-1} = (n+1)^{-1} \cdot (n+1)
先预处理阶乘，然后根据费马小定理，直接用快速幂求 (n!)^{p-2} \bmod p 的结果，再反过来递推一遍。
求组合数
利用 \binom{n}{m} = n! \cdot (m!)^{-1} \cdot ((n-m)!)^{-1} 直接计算即可，注意取模。
一些位置上的递推
我们可能要处理：\sum^{k}_{i=1} \binom{n}{i}, \sum^{k}_{i=1} \binom{n+i}{m}, \sum^{k}_{i=1} \binom{n+i}{m-1}。分别代表一横行，反斜线和正斜线。
预处理逆元，通过提出阶乘中的一些数，有：
\binom{n}{i} = \frac{n - i + 1}{i}\binom{n}{i-1}
\binom{n + i}{m} = \frac{n + i}{n + i - m}\binom{n + i - 1}{m}
\binom{n + i}{m - i} = \frac{(n+i)(m-i+1)}{(n-m+2i)(n-m+2i-1)}\binom{n+i-1}{m-i+1}
分别作用于三种。第一种是线性的，后两种需要先用快速幂求出起始位置的组合数。
在组合数计算中，除非必须，我们不建议将所有组合全部拆开。
第五节 组合数的分步计数
分步计数，即为分步骤，分阶段计数。这类问题有可能出现在树上。
定义一种多重组合数 \binom{n}{m_1, m_2, \cdots, m_k}，其中 m_1 + m_2 + \cdots + m_k = n。它表示的是分步取走 m_1, m_2, \cdots, m_k 个数。
我们可以分步理解，第一步从 n 个数里取走 m_1 个，第二步从剩下 n - m_1 个取走 m_2 个……因此，多重组合数：
\binom{n}{m_1, m_2, \cdots, m_k} = \prod^{k}_{i=1}\binom{n-\sum^{i-1}_{j=1}m_j}{m_i}
而在分步计数中，我们将多重组合数乘起来，计算不同步的答案。
第六节 容斥原理
对于集合 A_1, A_2, \cdots, A_n，记集合 S 的大小为 |S|，有：
|\bigcup^{n}_{i=1} A_i| = \sum_{i} |A_i| - \sum_{i<j} |A_i \cap A_j| + \cdots + (-1)^{n+1}|\bigcap^{n}_{i=1} A_i|
证明，可用数学归纳法：
当 n = 1 时，|A_1| = |A_1|。
当 n = 2 时，|A_1 \cup A_2| = |A_1| + |A_2| - |A_1 \cap A_2|。
当 n \ge 3 时，|(A_1 \cup A_2 \cup \cdots \cup A_{n-1}) \cup A_n| = |A_1 \cup A_2 \cup \cdots \cup A_{n-1}| + |A_n| - |(A_1 \cup A_2 \cup \cdots \cup A_{n-1}) \cap A_n|。
其中，由 (X \cup Y) \cap Z = (X \cap Z) \cup (Y \cap Z) 可得 |(A_1 \cup A_2 \cup \cdots \cup A_{n-1}) \cap A_n| = |(A_1 \cap A_n) \cup (A_2 \cap A_n) \cup \cdots \cup (A_{n-1} \cap A_n)|。
部分情况下，|A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_k}| 与 i_1, i_2, \cdots, i_k 无关，只与 k 有关，记 f(k) = |\bigcap^{k}_{i=1} A_i|，则：
|\bigcup^{n}_{i=1} A_i| = \sum^{n}_{k=1}\binom{n}{k}f(k)(-1)^{k+1}
下面介绍几种常用的容斥原理应用。
动态规划容斥
在容斥原理中，每一项都有其系数，称其为“容斥系数”。
有时候，|A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_k}| 有阶段性，可应用动态规划。
状态的设计一般是带容斥系数的状态设计。
树上容斥
树上的容斥大多依赖树形动态规划转移，结合上面讲过的动态规划的容斥和分步计数，解决这类题目。
第七节 斯特林数
第一类斯特林数
定义：将 n 个不同元素划分进 m 个相同的非空环的方案数，记为 n \brack m。
注意环是可以转动且有序的。有：
{n \brack m} = {n - 1 \brack m - 1} + (n-1){n-1 \brack m}
用组合意义解释：前者表示这个元素和其他元素不在一个环，后者表示这个元素和其他元素在一个环。
边界：{n \brack 0} = [n = 0]。
第二类斯特林数
定义：将 n 个不同元素划分进 m 个相同的非空集合的方案数，记为 n \brace m。
有：
{n \brace m} = {n - 1 \brace m - 1} + m{n-1 \brace m}
也可用组合意义解释，前者表示这个元素和其他元素不在一个集合，后者表示这个元素和其他元素在一个集合。
边界：{n \brace 0} = [n = 0]
或用容斥原理，令集合两两互不相同，集合内元素可被区分，则重复了 m! 次，因此有：
{n \brace m} = \frac{1}{m!}\sum^{m}_{k=0}(-1)^k\binom{m}{k}(m-k)^n
划分数
引入一种划分数，表示把非负整数数 n 分成 m 个非负整数的方案数（分出的数不区分顺序），记作 f(n, m)。
钦定 x_1 \ge x_2 \ge x_3 \ge \cdots \ge x_n。基于构造，我们可以想到动态规划中，每一次操作要么在末尾加个 0，要么将前面所有数字增大 1，所以有：
f(n, m) = f(n, m-1) + f(n-m, m)
边界：f(0, m) = 1。
第八节 二项式反演
用于解决一类具有恰好二字的组合计数。
令 f(x) 表示恰好 x 个满足条件的方案数，g(x) 表示指定 x 个位置满足条件的方案数，即 g(t) = \sum_{1 \le i_1 \le i_2 \le \cdots \le i_t \le n} |A_{i_1} \cap A_{i_2} \cap \cdots A_{i_t}|。
可以用 f(t) 表示出 g(t)，然后通过二项式反演由 g(t) 表示出 f(t)。
第九节 倍数容斥
倍数容斥用于解决与最大公约数，约数倍数有关的问题。
令 f(x) 表示该数值（指最大公约数，约数或倍数其一）为 x 的方案数，g(x) 表示该数值为 x 的倍数的方案数，还是利用二项式反演解答。