专栏文章

组合计数·基本理论

llihongru
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mlo0516b
此快照首次捕获于
2026/02/16 01:11
4 天前
此快照最后确认于
2026/02/19 01:12
16 小时前
查看原文

第一节 计数原理

加法原理

若完成 A→BA \to B 有 xx 种方案一，有 yy 种方案二，则完成 A→BA \to B 的总方案数为 x+yx + y。
要么选 xx 种中的一种，有 xx 种方案；要么选 yy 种中的一种，有 yy 种方案。因此总方案数为 x+yx + y 种。同步之间用加法。

乘法原理

若完成 A→BA \to B 有 xx 种方案，完成 B→CB \to C 有 yy 种方案，则完成 A→B→CA \to B \to C 有 xyxy 种方案。
对于 A→BA \to B 的 xx 种方案中的每一种，下一步 B→CB \to C 都可选 yy 种中的一种，所以总方案数为 xyxy 种。异步之间用乘法。

排列数

排列数用于解决 nn 个相互区分的物品中选出 mm 个排成一横排（区分顺序）的方案数。
考虑 mm 个位置的每个位置：第一个位置可放 nn 个物品，第二个位置可放 n−1n - 1 个物品（已经选出一个，但选出的这一个是哪一个并不重要，因为无论选出的是哪一个，依然还剩 n−1n - 1 个物品）……最后一个位置可以放 n−m+1n - m + 1 个物品。
根据上面的加法原理和乘法原理，我们总结出排列数 Anm=n(n−1)⋯(n−m+2)(n−m+1)A^m_n = n(n-1) \cdots (n - m + 2)(n - m + 1)。若 n<mn < m 或 m<0m < 0，Anm=0A^m_n = 0。
记 nn 的阶乘 n!n! 为 AnnA^n_n，特殊地，0!=10!=1。它一般的意义是 1∼n1 \sim n 的数的排列数。所以组合数 AnmA^m_n 也可写成 n!(n−m)!\frac{n!}{(n-m)!}。

第二节 组合数

记 CnmC^m_n 或 (nm)\binom{n}{m} 为在 nn 个物品中选出 mm 个物品（不区分顺序）的方案数。若 n<mn < m 或 m<0m < 0，(nm)=0\binom{n}{m} = 0，否则：
(nm)=n!m!(n−m)!\binom{n}{m} = \frac{n!}{m!(n-m)!}
我们可以用排列数来理解组合数公式。首先从 nn 个里选 mm 个，区分顺序时为 Anm=n!(n−m)!A^m_n = \frac{n!}{(n-m)!}。然后如果不想区分顺序了，我们需要除以所有 1∼m1 \sim m 的排列，即为 m!m!。
或是理解为先将 nn 个物品排列，取前 mm 个，前面 mm 个重复了 m!m! 次，后面还有 n−mn - m 个重复了 (n−m)!(n - m)! 次。
组合数有递推式：
(nm)=(n−1m−1)+(n−1m)\binom{n}{m} = \binom{n - 1}{m - 1} + \binom{n - 1}{m}
我们可以用数学推导理解：(n−1m−1)+(n−1m)=(n−1)!(m−1)!(n−m)!+(n−1)!m!(n−m−1)!=(n−1)!m!(n−m)!(m+(n−m))=n!m!(n−m)!=(nm)\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}。
中间一步加法，使用通分的方法进行变形。
也可以用组合意义理解：我们指定其中一个物品，如果选，那么有 (n−1m−1)\binom{n - 1}{m - 1} 种方案（在剩下的 n−1n-1 个选 m−1m-1 个），如果不选，那么有 (n−1m)\binom{n - 1}{m} 种方案（在剩下 n−1n-1 个选 mm 个）。

第三节 范德蒙德卷积

∑i=0k(ni)(mk−i)=(n+mk)\sum^{k}_{i=0}\binom{n}{i}\binom{m}{k-i} = \binom{n + m}{k}
用组合意义可以很轻松地理解这个问题：nn 个红球和 mm 个蓝球，在这 n+mn + m 个中选出 kk 个。
还有一个很常用的式子：
∑i=0n(ni)2=∑i=0n(ni)(nn−i)=(2nn)\sum^{n}_{i=0}\binom{n}{i}^2= \sum^{n}_{i=0}\binom{n}{i}\binom{n}{n-i} = \binom{2n}{n}

第四节 组合数计算

递推

已证，可用递推式：
(nm)=(n−1m−1)+(n−1m)\binom{n}{m} = \binom{n - 1}{m - 1} + \binom{n - 1}{m}
解决 n≤5×103n \le 5 \times 10^3 时的组合数计算。时间复杂度 O(n2)O(n^2)。

逆元

在组合数计算时，一般会要求结果对某个数 pp（一般是质数）取余数，因为结果实在太大了。
记 x−1x^{-1} 为满足 x⋅x−1≡1(modp)x \cdot x^{-1} \equiv 1 \pmod p 的数，即为 xx 的逆元。则组合数公式变为：
(nm)=n!⋅(m!)−1⋅((n−m)!)−1\binom{n}{m} = n! \cdot (m!)^{-1} \cdot ((n-m)!)^{-1}
所以我们需要预处理阶乘和阶乘的逆元。

Ⅰ 利用线性求逆元

有：
x−1=−⌊px⌋⋅(p mod x)−1x^{-1} = -\lfloor\frac{p}{x}\rfloor \cdot (p \bmod x)^{-1}
证明：因为 p=⌊px⌋⋅x+(p mod x)p = \lfloor \frac{p}{x}\rfloor \cdot x + (p \bmod x)，所以 p mod x≡−⌊px⌋(modp)p \bmod x \equiv -\lfloor\frac{p}{x}\rfloor \pmod p，得出 x−1=−⌊px⌋⋅(p mod x)−1x^{-1} = -\lfloor\frac{p}{x}\rfloor \cdot (p \bmod x)^{-1}。
再利用 (n!)−1=((n−1)!)−1⋅n−1(n!)^{-1}=((n-1)!)^{-1} \cdot n^{-1} 直接求出阶乘的逆元。

Ⅱ 利用可递推性正反求逆元

有：
(n!)−1=(n+1)−1⋅(n+1)(n!)^{-1} = (n+1)^{-1} \cdot (n+1)
先预处理阶乘，然后根据费马小定理，直接用快速幂求 (n!)p−2 mod p(n!)^{p-2} \bmod p 的结果，再反过来递推一遍。

求组合数

利用 (nm)=n!⋅(m!)−1⋅((n−m)!)−1\binom{n}{m} = n! \cdot (m!)^{-1} \cdot ((n-m)!)^{-1} 直接计算即可，注意取模。

一些位置上的递推

我们可能要处理：∑i=1k(ni),∑i=1k(n+im),∑i=1k(n+im−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}。分别代表一横行，反斜线和正斜线。
预处理逆元，通过提出阶乘中的一些数，有：
(ni)=n−i+1i(ni−1)\binom{n}{i} = \frac{n - i + 1}{i}\binom{n}{i-1}
(n+im)=n+in+i−m(n+i−1m)\binom{n + i}{m} = \frac{n + i}{n + i - m}\binom{n + i - 1}{m}
(n+im−i)=(n+i)(m−i+1)(n−m+2i)(n−m+2i−1)(n+i−1m−i+1)\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}
分别作用于三种。第一种是线性的，后两种需要先用快速幂求出起始位置的组合数。
在组合数计算中，除非必须，我们不建议将所有组合全部拆开。

第五节 组合数的分步计数

分步计数，即为分步骤，分阶段计数。这类问题有可能出现在树上。
定义一种多重组合数 (nm1,m2,⋯ ,mk)\binom{n}{m_1, m_2, \cdots, m_k}，其中 m1+m2+⋯+mk=nm_1 + m_2 + \cdots + m_k = n。它表示的是分步取走 m1,m2,⋯ ,mkm_1, m_2, \cdots, m_k 个数。
我们可以分步理解，第一步从 nn 个数里取走 m1m_1 个，第二步从剩下 n−m1n - m_1 个取走 m2m_2 个……因此，多重组合数：
(nm1,m2,⋯ ,mk)=∏i=1k(n−∑j=1i−1mjmi)\binom{n}{m_1, m_2, \cdots, m_k} = \prod^{k}_{i=1}\binom{n-\sum^{i-1}_{j=1}m_j}{m_i}
而在分步计数中，我们将多重组合数乘起来，计算不同步的答案。

第六节 容斥原理

对于集合 A1,A2,⋯ ,AnA_1, A_2, \cdots, A_n，记集合 SS 的大小为 ∣S∣|S|，有：
∣⋃i=1nAi∣=∑i∣Ai∣−∑i<j∣Ai∩Aj∣+⋯+(−1)n+1∣⋂i=1nAi∣|\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=1n = 1 时，∣A1∣=∣A1∣|A_1| = |A_1|。
当 n=2n = 2 时，∣A1∪A2∣=∣A1∣+∣A2∣−∣A1∩A2∣|A_1 \cup A_2| = |A_1| + |A_2| - |A_1 \cap A_2|。
当 n≥3n \ge 3 时，∣(A1∪A2∪⋯∪An−1)∪An∣=∣A1∪A2∪⋯∪An−1∣+∣An∣−∣(A1∪A2∪⋯∪An−1)∩An∣|(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∪Y)∩Z=(X∩Z)∪(Y∩Z)(X \cup Y) \cap Z = (X \cap Z) \cup (Y \cap Z) 可得 ∣(A1∪A2∪⋯∪An−1)∩An∣=∣(A1∩An)∪(A2∩An)∪⋯∪(An−1∩An)∣|(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)|。
部分情况下，∣Ai1∩Ai2∩⋯∩Aik∣|A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_k}| 与 i1,i2,⋯ ,iki_1, i_2, \cdots, i_k 无关，只与 kk 有关，记 f(k)=∣⋂i=1kAi∣f(k) = |\bigcap^{k}_{i=1} A_i|，则：
∣⋃i=1nAi∣=∑k=1n(nk)f(k)(−1)k+1|\bigcup^{n}_{i=1} A_i| = \sum^{n}_{k=1}\binom{n}{k}f(k)(-1)^{k+1}
下面介绍几种常用的容斥原理应用。

动态规划容斥

在容斥原理中，每一项都有其系数，称其为“容斥系数”。
有时候，∣Ai1∩Ai2∩⋯∩Aik∣|A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_k}| 有阶段性，可应用动态规划。
状态的设计一般是带容斥系数的状态设计。

树上容斥

树上的容斥大多依赖树形动态规划转移，结合上面讲过的动态规划的容斥和分步计数，解决这类题目。

第七节 斯特林数

第一类斯特林数

定义：将 nn 个不同元素划分进 mm 个相同的非空环的方案数，记为 [nm]n \brack m。
注意环是可以转动且有序的。有：
[nm]=[n−1m−1]+(n−1)[n−1m]{n \brack m} = {n - 1 \brack m - 1} + (n-1){n-1 \brack m}
用组合意义解释：前者表示这个元素和其他元素不在一个环，后者表示这个元素和其他元素在一个环。
边界：[n0]=[n=0]{n \brack 0} = [n = 0]。

第二类斯特林数

定义：将 nn 个不同元素划分进 mm 个相同的非空集合的方案数，记为 {nm}n \brace m。
有：
{nm}={n−1m−1}+m{n−1m}{n \brace m} = {n - 1 \brace m - 1} + m{n-1 \brace m}
也可用组合意义解释，前者表示这个元素和其他元素不在一个集合，后者表示这个元素和其他元素在一个集合。
边界：{n0}=[n=0]{n \brace 0} = [n = 0]
或用容斥原理，令集合两两互不相同，集合内元素可被区分，则重复了 m!m! 次，因此有：
{nm}=1m!∑k=0m(−1)k(mk)(m−k)n{n \brace m} = \frac{1}{m!}\sum^{m}_{k=0}(-1)^k\binom{m}{k}(m-k)^n

划分数

引入一种划分数，表示把非负整数数 nn 分成 mm 个非负整数的方案数（分出的数不区分顺序），记作 f(n,m)f(n, m)。
钦定 x1≥x2≥x3≥⋯≥xnx_1 \ge x_2 \ge x_3 \ge \cdots \ge x_n。基于构造，我们可以想到动态规划中，每一次操作要么在末尾加个 00，要么将前面所有数字增大 11，所以有：
f(n,m)=f(n,m−1)+f(n−m,m)f(n, m) = f(n, m-1) + f(n-m, m)
边界：f(0,m)=1f(0, m) = 1。

第八节 二项式反演

用于解决一类具有恰好二字的组合计数。
令 f(x)f(x) 表示恰好 xx 个满足条件的方案数，g(x)g(x) 表示指定 xx 个位置满足条件的方案数，即 g(t)=∑1≤i1≤i2≤⋯≤it≤n∣Ai1∩Ai2∩⋯Ait∣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)f(t) 表示出 g(t)g(t)，然后通过二项式反演由 g(t)g(t) 表示出 f(t)f(t)。

第九节 倍数容斥

倍数容斥用于解决与最大公约数，约数倍数有关的问题。
令 f(x)f(x) 表示该数值（指最大公约数，约数或倍数其一）为 xx 的方案数，g(x)g(x) 表示该数值为 xx 的倍数的方案数，还是利用二项式反演解答。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...