浅谈进阶组合计数

zt17 · 2026-05-12 22:03:35 · 算法·理论

笔者每次一堆组合数求和就是推不出来式子，题解里面说到的各种反演全部都不会，容斥永远只会最基本的式子，sale 场上拿 28 分。

所以笔者写了一篇本质为学习笔记的文章。

可能对初学者不太友好，你应该保证你会做绿左右的计数！

有些东西不太全，非常欢迎提一些建议我去学的东西，你也可以评论私信我没看懂的地方。

有些想写但还没来得及写的东西，下面是一个 Todo list：

双线反射容斥
容斥相关
例题

一些前置知识

组合数

组合数，别名二项式系数，通常写为 \dbinom{n}{m}，也可以写成 C_n^m~~，但是我已经改过来了~~。

\dbinom{n}{m} = \frac{n!}{m!(n-m)!}

有组合意义：从 n 个不区分的物品中选 m 个出来的方案数。

在很多的 dp 题和数数题中出现，由于其独特的组合意义使得它在 OI 中有着极为广泛的运用。

有几个简单的常用式子：

\dbinom{n}{m} = \dbinom{n}{n-m} \\ \dbinom{n}{m} = \dbinom{n-1}{m-1} + \dbinom{n-1}{m} \\ \dbinom{n}{0} = \dbinom{n}{n} = 1 \\ k\dbinom{n}{k} = n\dbinom{n-1}{k-1}

下降幂 / 上升幂

我们定义：

x^{\underline{n}} = x(x-1)(x-2)\dots(x-n+1) \\ x^{\overline{n}} = x(x+1)(x+2)\dots(x+n-1)

其中 x \in \R,n \in \Z。

如果 n < 0，那么：

x^{\underline{-n}} = \frac{1}{(x+1)(x+2)\dots(x+n)} \\ x^{\overline{-n}} = \frac{1}{(x-1)(x-2)\dots(x-n)}

不要问我分母为零时怎么办这种鬼畜问题。

如果分母为零，那么一般把它看作一个形式幂级数。你可以理解为这个式子没有定义，但是可以被当作一个下降幂和上升幂去和别的式子一起算，方便推式子化简。

广义二项式系数

我们定义：

\dbinom{n}{m} = \frac{n^{\underline{m}}}{m!}

其中 n \in \R，m \in \Z。

特别的，当 m < 0 时，\dbinom{n}{m} = 0。

什么你问我这玩意有什么用？在后面的生成函数和幂级数中有着一些运用，也是给我们下面讲的一个东西做一些概念上的定义。

推式子常用公式

很多题如果你直接按照题意去模拟求和，可能外围的 \sum 套了多层导致枚举复杂度爆了，而有些对于组合数求和的式子可以化简从而优化复杂度。

由于组合数的组合意义性质非常强大，所以对着式子想组合意义是一个不错的推式子方法。

二项式定理

有式子：

(a+b)^n = \sum_{i=0}^n a^i b^{n-i} \dbinom{n}{i}

a当然你想把这个东西拆开证明当然可以，我们这里考虑左式的组合意义。我们可以看作有 n 个盒子，每个盒子里面都有红球和蓝球各一个。现在从每个盒子里面选一个球出来，那么 a^i b^{n-i} 的系数则是选了 i 个红球的方案数，当然你也可以看作选了 n-i 个蓝球，因为 \dbinom{n}{i} = \dbinom{n}{n-i}。

平行求和

有式子：

\sum_{i=0}^{m} \dbinom{n+i}{i} = \dbinom{n+m+1}{m}

有一个证明是

\begin{aligned} \sum_{i=0}^m \dbinom{n+i}{i} &= \dbinom{n}{0} + \dbinom{n+1}{1} + \dots + \dbinom{n+m}{m} \\ &= (\dbinom{n+1}{0} + \dbinom{n+1}{1}) + \dbinom{n+2}{2} + \dots + \dbinom{n+m}{m} \\ &= \dbinom{n+2}{1} + \dbinom{n+2}{2} + \dots + \dbinom{n+m}{m} \\ &= (\dbinom{n+2}{1} + \dbinom{n+2}{2}) + \dbinom{n+3}{3} + \dots + \dbinom{n+m}{m} \\ &= \dbinom{n+3}{2} + \dbinom{n+3}{3} + \dots + \dbinom{n+m}{m} \\ &= \dots \\ &= \dbinom{n+m}{m-1} + \dbinom{n+m}{m} \\ &= \dbinom{n+m+1}{m} \end{aligned}

太暴力了！有没有什么更优美的证明呢？

有的兄弟，有的。考虑组合意义，\dbinom{n+m+1}{m} 可以看作在 n+m+1 个球中选出 m 个。我们把 n+m+1 个球排成一排，令最靠右的没被选的是倒数第 j+1 个，那么最后的 j 个球肯定全部都被选了，也就是要在前面的 (n+m+1)-(j+1) 个球中再选出 m-j 个，方案数为 \dbinom{n+m-j}{m-j}。

那么总方案数为 \sum_{j=0}^m \dbinom{n+m-j}{m-j}，令 i = m-j，式子可以改写为 \sum_{i=0}^m \dbinom{n+i}{i}，原式得证。

三项式系数恒等式

有式子：

\dbinom{n}{m}\dbinom{m}{k} = \dbinom{n}{k}\dbinom{n-k}{m-k}

这个证明很简单，左式右式拆开为阶乘形式就可以了：

\begin{aligned} \dbinom{n}{m}\dbinom{m}{k} &= \frac{n!m!}{m!(n-m)! \times k!(m-k)!} \\ &= \frac{n!}{(n-m)!k!(m-k)!} \\ &= \frac{n!(n-k)!}{k!(n-k)! \times (m-k)!(n-m)!} \\ &= \dbinom{n}{k} \dbinom{n-k}{m-k} \end{aligned}

也可以看作从 n 个球里面选出来 m 个，然后再从选出来的 m 个里面选出来 k 个球的方案数，等价于从 n 个里面直接选出来 k 个，再从剩下的 n-k 个里面选出来第一轮选中了但是第二轮没选中的 m-k 个球的方案数。

上指标求和（朱世杰恒等式）

有式子：

\sum_{i\le n} \dbinom{i}{m} = \dbinom{n+1}{m}

令 n' = n - m，式子可以写成：

\sum_{i\le n'+m} \dbinom{i}{m} = \dbinom{n'+m+1}{m}

转换一下，得：

\sum_{i=m}^{n'+m} \dbinom{i}{m} = \dbinom{n'+m+1}{m}

令 i' = i-m，即为：

\sum_{i'=0}^{n'} \dbinom{i'+m}{m} = \dbinom{n'+m+1}{m}

把 \dbinom{i'+m}{m} = \dbinom{i'+m}{i'} 代进去就是平行求和的式子了。

上指标反转

有式子：

\dbinom{n}{m} = (-1)^m \dbinom{m-n-1}{m}

左式拆成下降幂，然后给下降幂的每个数乘上一个 -1，即 (-1)^m n^{\underline{m}} = (m-n-1)^{\underline{m}}。

可以在组合数不好进行推式子的时候稍微转化一下。

上指标卷积

有式子：

\sum_{p+q=t}\dbinom{p}{n}\dbinom{q}{m} = \dbinom{t+1}{n+m+1}

如果你是组合意义超级大神，你应该可以看着左边的式子写出右边的式子！

我们设有 t+1 个球排成一列，从中选出来 n+m+1 个球的方案数为右式。我们令第 n+1 个球的位置在 p+1，那么前面 p 个位置要选出来 n 个，后面 q 个位置要选出来 m 个的方案数乘起来，再关于 p 求和的结果为上面的左式。

下指标卷积（范德蒙德卷积）

有式子：

\sum_{n+m=t} \dbinom{p}{n} \dbinom{q}{m} = \dbinom{p+q}{t}

如果你是组合意义超级大神，你应该可以看着左边的式子写出右边的式子！

我们设有 p+q 个球排成一列，从中选出 t 个球的方案数为右式。那么令前 p 个球有 n 个被选中了，那么后面 q 个球就要选出 m 个，然后对 n 求和一遍为上面的左式。

笔者被一道著名题目送走无缘 NOI2026。

整行下指标求和

有式子：

\sum_{i=0}^n \dbinom{n}{i} = 2^n

设有 n 个球，随便选，那么可以选 0,1,2,\dots,n 个，总方案数为左式。每个球可以选或者不选，总方案数为 2^n。

也有二项式定理：(1+1)^n = \sum_{i=0}^n 1^i 1^{n-i} \dbinom{n}{i}。

带权下指标求和

有式子：

\sum_{i=0}^n \dbinom{n}{i} x^i = (1+x)^n

二项式定理。

哈哈还有更难的：

\sum_{i=0}^n \dbinom{n}{i} i^{\underline{m}} = n^{\underline{m}} \times 2^{n-m}

把里面的东西拆开，得到 \frac{n!i!}{i!(n-i)!(i-m)!}，这个东西即为 \dbinom{n-m}{n-i} \times n^{\underline{m}}，所以式子可以变成：

\begin{aligned} \sum_{i=0}^n \dbinom{n}{i} i^{\underline{m}} &= n^{\underline{m}} \sum_{i=0}^n \dbinom{n-m}{i-m} \\ &= n^{\underline{m}} \sum_{i'=0}^{n-m} \dbinom{n-m}{i'} \\ &= n^{\underline{m}} 2^{n-m} \end{aligned}

卡特兰数与格路计数

反射容斥

给出一个问题：有一个平面直角坐标系，从 (0,0) 出发，只能往右边走和上面走一单位长度，终点为 (n,n)，要求经过的所有点的横坐标不小于纵坐标，求路径数量。

发现从 (0,0) 到 (n,n) 的路径一定走了 2n 步，其中有 n 步向右走，有 n 步向上走。如果不考虑限制，那么就相当于从 2n 步的序列中选出 n 步向右走，那么方案数是 \dbinom{2n}{n}。好考虑加上限制怎么做。

发现限制相当于不能跨过但可以触碰直线 y = x，也就是不能触碰直线 y = x+1。正难则反，我们考虑如何计算违反了限制的路径，也就是触碰了直线 y = x+1 的路径数。我们设一条非法路径第一次触碰直线 y = x+1 的位置在 (k,k+1)，然后将这条路径后面的部分关于直线 y=x+1 对称，就变成了从 (0,0) 到 (n-1,n+1) 的一条路径。发现从 (0,0) 到 (n-1,m+1) 的一条路径必定会经过直线 y=x+1，那么我们可以将从 (0,0) 到 (n-1,n+1) 的每条路径与非法路径一一对应，也就是建立一个双射。那么非法路径的数量就等于从 (0,0) 到 (n-1,n+1) 的任意路径数了。

仿照上面的计算方式，从 (0,0) 到 (n-1,n+1) 的路径数量为 \dbinom{2n}{n+1}。那么开始的问题的答案就是 \dbinom{2n}{n} - \dbinom{2n}{n+1}。

我们把这样将带限制的格路计数转换为没有限制的格路数的差的方法称呼为反射容斥。

卡特兰数

本段大部分内容抄自 OI Wiki。

我们定义一个数列：

C_n = \begin{cases} 1 & n = 1 \\ \sum_{i=0}^{n-1} C_i C_{n-i-1} & n > 1 \end{cases}

将上面的问题转换一下可以得到这个数列：从 (0,0) 到 (n,n) 的路径换一种转换方式，发现路径的第一步一定往右，最后一步一定往上，那么考虑从 (0,1) 到 (n,n-1) 的路径，设第一次碰到直线 y = x 的位置在 (k,k)，那么可以看作从 (0,1) 到 (k,k-1) 的答案加上从 (k,k) 到 (n,n) 的答案，分成了两个子问题！于是有了上面的递推式。

卡特兰数有着非常丰富的组合意义，可以去看看 OI Wiki。

双线反射容斥

todo.

斯特林数

第一类斯特林数

记 {n \brack m} 为第一类斯特林数，定义为 n 个区分元素分成 m 个圆排列（环）的方案数。

有递推式：

{n \brack m} = {n-1 \brack m-1} + (n-1){n-1 \brack m}

可以分为新开一个环和成为原来的一个元素的后继。

一些式子：

n! = \sum_{i=1}^n {n \brack i}

把一个排列看成把 [1,n] 分成若干个置换环，左右两式相等。

x^{\overline{n}} = \sum_{i=0}^n {n \brack i} x^i \\ x^{\underline{n}} = \sum_{i=0}^n {n \brack i} (-1)^{n-i} x^i

第一个式子可以归纳法证 x^{\overline{n+1}} = (x+n) x^{\overline{n}}，第二个式子可以证 x^{\underline{n}} = (-1)^n(-x)^{\overline{n}}，具体式子咕了。

第二类斯特林数

记 {n \brace m} 为第二类斯特林数，定义为 n 个区分元素分成 m 个不区分集合的方案数。

有递推式：

{n \brace m} = {n-1 \brace m-1} + m{n-1 \brace m}

可以分为新开一个集合和塞进原来的一个集合。

一些式子：

m^n = \sum_{i=0}^m \dbinom{m}{i} i! {n \brace i}

左式为 n 个区分小球塞进 m 个区分盒子的方案数，可以为空。枚举有 i 个盒子非空，那么从 m 里面选出 i 个箱子并重新排列，再把 n 个小球依次加入排列后的盒子里，就是右式。

m!{n \brace m} = \sum_{i=0}^m (-1)^{m-i} \dbinom{m}{i} i^n

对上面的式子二项式反演，这个后文会提到。

Prufer 序列

直接照搬的这篇文章。

定义

我们引进一颗较为简单的树，如下图：

我们进行下列操作：

找到当前树中叶子节点中编号最小的，记为 u_i。
选定与 u_i 相连接的节点，记为 v_i。
将 v_i 加入一个用于记录的序列，然后删除节点 u_i 和 u_i - v_i 的连边，重复上述操作直到原图仅剩两个节点。

例如上图中给定的例子最终得到的序列为 {3,1,5,5,1}。

我们可以发现，由于一棵树每一次被选定的节点是固定的，所以对于每一棵不同的树都对应着一个上述中的序列，我们称这个序列为 Prüfer 序列。

可证明一个 Prüfer 序列是对应唯一一棵树且可以与其相互转化的。

一些证明

树对应的序列的唯一性

这个很好证明，因为对于一棵树经历过若干次操作后的状态，接下来操作的节点是可确定的。

序列转换成树

我们还是拿上图举例。

已知有一颗有标号的顶点的树，节点数量为 7，其的 Prüfer 序列为 {3,1,5,5,1}，需求出这棵树。

注意到在一棵树的 Prüfer 序列中未出现的节点一定为这棵树的叶子结点。

我们将所有叶子结点首先加入一个最小堆，容易发现第一次操作选中的是 Prüfer 序列的第一项与编号最小的一个叶子节点的连边，于是我们将此连边选中。

例如在序列 {3,1,5,5,1} 中，我们会将连边 {2-3} 选中。

由于 2 号节点已有连边，所以并不是叶子结点，将 2 号节点从存储叶子结点的堆中弹出。发现 3 号节点不再在 Prüfer 序列中存在连边，所以删去连边 {2-3} 后节点 3 成为了叶子结点。将节点 3 加入维护叶子结点的堆并重新维护最小值，原 Prüfer 序列也变为 1,5,5,1，发现可以递归求解。

容易发现递归边界为 Prüfer 序列中仅存在一个节点 1，而此时存储叶子结点的堆中仅有一个节点 7。所以此时我们将连边 1-7 加入，并结束递归，我们就完成了对树的转换。

我们可以把上面归成下面几个步骤：

  1. 将原 Prüfer 序列中未存在的点加入维护叶子结点编号最小值的堆，并记录所有节点在原 Prüfer 序列中出现的次数；
  2. 选中当前 Prüfer 序列第一个节点，将该节点与当前最小的叶子结点进行连边；
  3. 将选中的最小叶子结点从堆中删除，当前第一个节点减去 $1$，如果该节点次数减至 $0$，将其加入叶子结点的堆。
  4. 删去当前 Prüfer 序列第一个节点，并重新维护叶子结点最小值。回到第二步继续执行操作直到无法操作。

至此，我们完成了由 Prüfer 序列向树的转换，接下来要证明 Prüfer 序列对应的树的唯一性。

序列对应树的唯一性

发现我们将序列转换成树的操作每一步都是唯一的，所以一个 Prüfer 序列对应的树的每一条边都是唯一的，自然这棵树是唯一的。

由这个结论我们可以很轻松地证明 Cayley 定理。

Cayley 定理 : n 个有标号的顶点的树的数目为 n^{n-2}。

我们可以发现，n 个有标号的顶点的树的数目即为 n 个有标号的顶点的树可以组成的 Prüfer 序列个数。

可以发现 Prüfer 序列的 n-2 个节点都可以从 n 个节点中选择一个且互不干扰，总选择方案数为 n^{n-2}，原定理得证。

反演

反演概念

反演，就是指 : 两个函数(数列)之间的双向(求和)关系。

给出一个序列变换 A：F = A * G，那么相对应的，有 G = A^{-1} * F。我们把像这样相对应的两种变换之间的关系叫做反演。

可以把 A 看作一个矩阵，我们定义这样的一个矩阵 A 为关系矩阵，用来描述关系 F_n = \sum\limits_{i=0}G_i A_{n,i}。

发现上面变换的两个关系矩阵为 A 和 A^{-1}，有定理：两个互为反演的关系矩阵互逆。

基本反演推论

由于反演的核心在于关系矩阵，所以我们在调整反演系数的时候可以对着关系矩阵做。给一些结论：

一对互逆的矩阵转置之后仍然互逆。
- 一对互逆的矩阵分别数乘 c 和 \frac{1}{c} 后仍然互逆。（c \ne 0）
- 如果对于整数 i，A_{X,i} \leftarrow A_{X,i} \times c^i，那么 A^{-1}_{i,X} \leftarrow A^{-1}_{i,X} \times c^{-i}。

因为 \sum\limits_{i} A_{n,i} A^{-1}_{i,m} = [n=m]，所以 \sum\limits_{i} (c^i A_{n,i}) (c^{-i} A^{-1}_{i,m}) = [n=m]。

我们可以用这个去微调关系矩阵，从而调整反演的式子。

二项式反演

二项式系数在组合计数题目中非常常见，导致二项式反演是很多炫酷数数技巧的基础知识。

二项式反演有四种形式：

\begin{aligned} F(n) = \sum_{i=0}^n (-1)^i \dbinom{n}{i} G(i) \quad &\Longleftrightarrow \quad G(n) = \sum_{i=0}^n (-1)^i \dbinom{n}{i} F(i) & (1)\\ F(n) = \sum_{i=0}^n \dbinom{n}{i} G(i) \quad &\Longleftrightarrow \quad G(n) = \sum_{i=0}^n (-1)^{n-i} \dbinom{n}{i} F(i) & (2) \\ F(n) = \sum_{i=n}^m \dbinom{i}{n} G(i) \quad &\Longleftrightarrow \quad G(n) = \sum_{i=n}^m (-1)^{i-n} \dbinom{i}{n} F(i) & (3) \\ F(n) = \sum_{i=n}^m (-1)^i \dbinom{i}{n} G(i) \quad &\Longleftrightarrow \quad G(n) = \sum_{i=n}^m (-1)^i \dbinom{i}{n} F(i) & (4) \end{aligned}

我们先证明 (1)，也就是要证明对于矩阵 A_{i,j} = (-1)^j \dbinom{i}{j} 而言，A^2 = I。等价于要证明 \sum_i A_{n,i} A_{i,m} = [n=m]。

\begin{aligned} \sum_i A_{n,i} A_{i,m} &= [n=m] \\ \sum_{i=m}^n A_{n,i} A_{i,m} &= [n=m] \\ \sum_{i=m}^n ((-1)^i \dbinom{n}{i}) ((-1)^m \dbinom{i}{m}) &= [n=m] \\ (-1)^m \sum_{i=m}^n (-1)^i \dbinom{n}{i} \dbinom{i}{m} &= [n=m] \\ (-1)^m \sum_{i=m}^n (-1)^i \dbinom{n}{m} \dbinom{n-m}{i-m} &= [n=m] \\ (-1)^m \dbinom{n}{m} \sum_{i=m}^n (-1)^i \dbinom{n-m}{n-i} &= [n=m] \\ (-1)^m \dbinom{n}{m} \sum_{i=0}^{n-m} (-1)^{i+m} \dbinom{n-m}{n-i-m} &= [n=m] \\ (-1)^{2m} \dbinom{n}{m} \sum_{i=0}^{n-m} (-1)^{i} \dbinom{n-m}{i} &= [n=m] \\ (-1)^{2m} \dbinom{n}{m} (1-1)^{n-m} &= [n=m] \\ \end{aligned}

最后一行显然成立。好那我们把 (1) 证出来了。

我们调整一下 (1) 的关系矩阵系数：A_{i,j} \leftarrow A_{i,j} \times (-1)^j,A_{i,j}^{-1} \leftarrow A_{i,j}^{-1} \times (-1)^i，成为 A_{i,j} = \dbinom{i}{j},A_{i,j}^{-1} = (-1)^{i-j} \dbinom{i}{j}，那么就有了 (2)。

我们把 (2) 的关系矩阵转置一下，成为 A_{i,j} = \dbinom{j}{i},A_{i,j}^{-1} = (-1)^{j-i} \dbinom{j}{i}，那么就有了 (3)。

我们调整一下 (3) 的关系矩阵系数：A_{i,j} \leftarrow A_{i,j} \times (-1)^j,A_{i,j}^{-1} \leftarrow A_{i,j}^{-1} \times (-1)^i，成为 A_{i,j} = (-1)^j \dbinom{j}{i},A_{i,j}^{-1} = (-1)^{j} \dbinom{j}{i}，那么就有了 (4)。

为什么不能直接转置 (1)？因为 (1) 中的 A_{i,j} 有一个 (-1)^j 与列有关，转置后就和行有关了。而 (4) 中的系数是与列有关的，所以 (1),(4) 并不能通过转置互相得到。Fun fact：直接转置 (1) 能得到另外一个对的式子：

F(n) = \sum_{i=n} (-1)^n \dbinom{i}{n} G(i) \Longleftrightarrow G(n) = \sum_{i=n} (-1)^n \dbinom{i}{n} F(i)

但由于平常做题并不会时常碰到可以专门提出来一个 (-1)^n 的式子，所以这个式子相对而言没那么常用。

莫比乌斯反演

试着改一下变换的形式，改为狄利克雷卷积：

F(n) = \sum\limits_{i|n} G(i) A(\frac{n}{i})

相当于设置关系矩阵为 A_{i,j} = [j \mid i] A(\frac{i}{j})。

此时有

G(n) = \sum\limits_{i|n} F(i) A^{-1}(\frac{n}{i})

其中函数 A^{-1}(x) 满足 \sum\limits_{m|i|n} A(\frac{n}{i}) A^{-1} (\frac{i}{m}) = [n=m]。

我们把条件式改写一下：

\begin{aligned} \sum\limits_{m|i|n} A(\frac{n}{i}) A^{-1} (\frac{i}{m}) &= [n=m] \\ \sum\limits_{m|i|n} A(\frac{\frac{n}{m}}{\frac{i}{m}}) A^{-1} (\frac{i}{m}) &= [n=m] \\ \sum\limits_{i|\frac{n}{m}} A(\frac{\frac{n}{m}}{i}) A^{-1} (i) &= [n=m] \\ &= [\frac{n}{m} = 1] \\ \sum\limits_{i|k} A(\frac{k}{i}) A^{-1} (i) &= [k=1] & k = \frac{n}{m} \\ \end{aligned}

所以只要满足 \sum\limits_{i|n} A(i) A^{-1}(\frac{n}{i}) = [n=1] 就可以了。也可以说，A^{-1}(x) 和 A(x) 对于狄利克雷卷积互为逆。

当 A(x) = 1 时，我们有式子 \sum\limits_{i|n} A^{-1}(i) = [n=1]。我们定义这个 A^{-1}(x) 函数叫做莫比乌斯函数，符号表示为 \mu(x)。

$$ \mu(x) = \begin{cases} 1 & x = 1 \\ (-1)^t & k_i = 1,i \in [1,t] \\ 0 & \text{otherwise} \end{cases} $$ 可以证明这个函数满足 $\sum\limits_{i|n} \mu(i) = [n=1]$： $$ n = \prod\limits_{i=1}^t p_i^{k_i} \quad \longrightarrow \quad n' = \prod\limits_{i=1}^t p_i \\ \begin{aligned} \sum\limits_{i|n} \mu(i) &= \sum\limits_{i|n'} \mu(i) \\ &= \sum_{i=0}^t (-1)^i \dbinom{t}{i} \\ &= (1-1)^t \\ &= [t=0] \\ &= [n=1] \end{aligned} $$ 那么就说明了 $\mu(x)$ 与 $A(x) = 1$ 互为逆，也就满足了 $\sum\limits_{i|n} A(i) A^{-1}(\frac{n}{i}) = [n=1]$ 中的条件，就给出了莫比乌斯反演的核心公式之一： $$ F(n) = \sum_{d|n} G(d) \quad \Longleftrightarrow \quad G(n) = \sum_{d|n} \mu(\frac{n}{d}) F(d) $$ 上面的推导过程中也有一些实用式子，我在这里总结一下相关的较为常用的式子： $$ \begin{aligned} \sum_{d|n} \mu(d) &= [n = 1] \\ [m | n] \sum_{d|\frac{n}{m}} \mu(d) &= [n = m] \\ F(n) = \sum_{d|n} G(d) \quad &\Longleftrightarrow \quad G(n) = \sum_{d|n} \mu(\frac{n}{d}) F(d) \\ F(d) = \sum_{d|n} G(n) \quad &\Longleftrightarrow \quad G(d) = \sum_{d|n} \mu(\frac{n}{d}) F(n) \\ \sum_{d|n,d|m} \mu(d) &= [(n,m) = 1] \\ \sum_{kd|n,kd|m} \mu(d) &= [(n,m) = k] \end{aligned} $$ 关于莫比乌斯反演的东西大致就这么多，进一步了解莫反和莫比乌斯函数有关的东西可以去数论板块了解。 Fun Fact：其实这个东西组合计数中用处不多，主要是给下一个东西做铺垫。 ## 子集反演反演也可以在集合幂级数中间做！上面有一个很帅气的东西：$F(n) = \sum\limits_{i|n} G(i) A(\frac{n}{i})$。发现 $i$ 其实就是 $n$ 的因子集。那么，我们把这个东西扔到集合幂级数上面能干啥？我们搞出来一个式子： $$ F[S] = \sum_{T \subseteq S} G[T] A_{S,T} \\ G[S] = \sum_{T \subseteq S} F[T] A^{-1}_{S,T} $$ 这个的限制就和矩阵乘法的限制类似了。假如我们设 $A_{S,T} = 1$，那么有： $$ \begin{aligned} \sum_{Y \subseteq S \subseteq X} A_{X,S} A^{-1}_{S,Y} &= [X = Y] \\ \sum_{S \subseteq X-Y} A_{X+S,Y}^{-1} &= [X = Y] \\ \end{aligned} $$ 首先有 $A_{\varnothing,S}^{-1} = 1$，然后可以用数学归纳法得出一个系数 $A_{X,Y}^{-1} = [X \subseteq Y] (-1)^{|Y-X|}$。证明这个系数是很对的可以用二项式定理： $$ X \supseteq Y,|Y-X| = n \\ \\ \begin{aligned} \sum_{Y \subseteq S \subseteq X} A_{X,S} A^{-1}_{S,Y} &= \sum_{S \subseteq X-Y} A_{X+S,Y}^{-1} \\ &= \sum_{i=0}^n \dbinom{n}{i} (-1)^i \\ &= (1-1)^n \\ &= [n = 0] \\ &= [X = Y] \\ \end{aligned} $$ 所以有： $$ F[S] = \sum_{T \subseteq S} G[T] \quad \Longleftrightarrow \quad G[S] = \sum_{T \subseteq S} (-1)^{|S-T|} F[T] $$ 这个就是子集反演的最基本的一个形式。把矩阵转置一下，还有： $$ F[T] = \sum_{T \subseteq S} G[S] \quad \Longleftrightarrow \quad G[T] = \sum_{T \subseteq S} (-1)^{|S-T|} F[S] $$ 那么你现在就可以用高维前缀和之类的技巧快速算左式然后得右式了！莫比乌斯反演就是在因子多重集上的反演，子集反演就是在子集上的反演。某种意义上讲，这两个东西都是集合反演理论的分支。集合反演技巧还有 $[S \subseteq (X \cap Y)] = [S \subseteq X][S \subseteq Y]$，可以把交集拆开。更多的技巧可以学习集合幂级数。 ## min-max 反演其实更多人叫 min-max 容斥，但是其形式看上去更像反演所以被归到这里来了。我们直接给式子： $$ \max(S) = \sum_{T \subseteq S} (-1)^{|T|+1} \min(T) $$ 这个怎么证呢？设 $a_i$ 是集合 $S$ 中第 $i$ 大的元素，那么 $\min(T) = a_i$ 当且仅当 $T = {a_i} \cup (\{ a_1,a_2,\dots,a_{i-1} \} \text{的一个子集})$，也就是说，$\min(T) = a_i$ 对于右式的贡献为： $$ S = \{ a_1,a_2,\dots,a_{i-1} \} \\ \begin{aligned} a_i \times \sum_{T \subseteq S} (-1)^{|T|} &= a_i \times \sum_{i=0}^{|S|} (-1)^{i} \\ &= a_i \times (1-1)^{|S|} \\ &= [|S| = 1] a_i \\ &= [i = 1] a_i \end{aligned} $$ 所以原式成立。我们把上面的式子反演一下，就可以得到： $$ \min(S) = \sum_{T \subseteq S} (-1)^{|T|+1} \max(T) $$ 这个东西对于期望也是成立的，所以有： $$ E(\max(S)) = \sum_{T \subseteq S} (-1)^{|T|+1} E(\min(T)) \\ E(\min(S)) = \sum_{T \subseteq S} (-1)^{|T|+1} E(\max(T)) $$ ## kth min-max 反演我们能不能扩展到第 $k$ 大呢？可以！因为上面的式子让我们感觉 $A_{S,T}$ 只和 $|T|$ 有关，不妨设为函数 $F(|T|)$，那么有： $$ \text{kthmax}(S) = \sum_{T \subseteq S} F(|T|) \min(T) $$ 感受一下，设 $a_i$ 为集合 $S$ 中第 $i$ 大元素，那么右侧它的贡献就是： $$ \sum_{x=0}^{i-1} \dbinom{i-1}{x}F(x+1) $$ 这个式子应该等于 $[i=k]$，而且这个式子可以套二项式反演，所以有： $$ \begin{aligned} \\ [i=k] &= \sum_{x=0}^{i-1} \dbinom{i-1}{x}F(x+1) \\ [i=k-1] &= \sum_{x=0}^{i} \dbinom{i}{x}F(x+1) \\ \Rightarrow F(x+1) &= \sum_{i=1}^x (-1)^{x-i} \dbinom{x}{i} [i=k-1] \\ &= (-1)^{x-k+1} \dbinom{x}{k-1} \\ F(x) &= (-1)^{x-k} \dbinom{x-1}{k-1} \end{aligned} $$ 所以： $$ \text{kthmax}(S) = \sum_{T \subseteq S} (-1)^{|T|-k} \dbinom{|T|-1}{k-1} \min(T) \\ \text{kthmin}(S) = \sum_{T \subseteq S} (-1)^{|T|-k} \dbinom{|T|-1}{k-1} \max(T) \\ E(\text{kthmax}(S)) = \sum_{T \subseteq S} (-1)^{|T|-k} \dbinom{|T|-1}{k-1} E(\min(T)) \\ E(\text{kthmin}(S)) = \sum_{T \subseteq S} (-1)^{|T|-k} \dbinom{|T|-1}{k-1} E(\max(T)) $$ ## 斯特林反演第一类斯特林数和第二类斯特林数之间也可以反演！ $$ \begin{aligned} F(n) = \sum_{i=0}^n {n \brace i} G(i) \quad &\Longleftrightarrow \quad G(n) = \sum_{i=0}^n (-1)^{n-i} {n \brack i} F(i) \\ F(n) = \sum_{i=0}^n {n \brack i} G(i) \quad &\Longleftrightarrow \quad G(n) = \sum_{i=0}^n (-1)^{n-i} {n \brace i} F(i) \\ F(n) = \sum_{i=n} {i \brace n} G(i) \quad &\Longleftrightarrow \quad G(n) = \sum_{i=n} (-1)^{i-n} {i \brack n} F(i) \\ F(n) = \sum_{i=n} {i \brack n} G(i) \quad &\Longleftrightarrow \quad G(n) = \sum_{i=n} (-1)^{i-n} {i \brace n} F(i) \\ \end{aligned} $$ 证明要生成函数相关知识，咕了。第一个式子等价于下面这个： $$ (-1) ^ m \sum_{i=0} (-1)^i {n \brace i} {i \brack m} = [n = m] $$ 可以想一下这个的组合意义！ ## 单位根反演首先你要会虚数。直接扔式子： $$ [n \mid k] = \frac{1}{n} \sum_{i=0}^{n-1} w_n^{ik} $$ 发现 $[n\mid k] = 0$ 时，感性理解右式相当于从原点出发转了一圈，式子为 $0$，也可以使用等比数列求和： $$ \frac{1}{n} \sum_{i=0}^{n-1} w_n^{ik} = \frac{1}{n} \times \frac{w_n^{an} - 1}{w_n^a - 1} $$ $[n \mid k] = 1$ 时，右式等于 $\frac{1}{n}\sum_{i=0}^{n-1} w_n^{0}$，也就是 $1$。单位元在模的意义下可以换为原根，也就是 $w_n^1 = g^{\frac{mod-1}{n}}$，所以有的时候看到模数 $998244353$ 且有一个数是 $2^k$ 时可能就要用单位根反演。有没有感觉上面那个东西和 NTT 很像？其实 NTT 本质可以理解为 $n = 2^k$ 的单位根反演计算循环卷积！但由于这里不是多项式入门指南所以不多叙述。我们有的时候不是形如 $[p \mid n] = [n \bmod p = 0]$ 的式子，而是 $[n \bmod p = k]$，这个可以化为 $[p \mid (n-k)]$。我们还有式子 $[n = m \mod p] = [(n-m) \bmod p = 0]$，有式子： $$ \begin{aligned} \frac{1}{n} \sum_{i=0}^{n-1} w_n^{ai-bi} &= [n \mid (a-b)] \\ \frac{1}{n} \sum_{i=0}^{n-1} w_n^{ai} w_n^{-bi} &= [a = b] \\ F(n) = \sum_{k=0}^{n-1} w_n^{ak} G(k) \quad & \Longleftrightarrow \quad G(n) = \frac{1}{n} \sum_{k=0}^{n-1} w_n^{-ak} F(k) \end{aligned} $$ 上面那个式子在 FFT/NTT 中的 IDFT 中会用到，所以有种说法是 FFT 本质是单位根反演。 ## 欧拉反演你首先要知道[欧拉函数](https://oi.wiki/math/number-theory/euler-totient/)是什么！直接扔式子： $$ \sum_{d|n} \varphi(d) = n $$ 对于 $k \in [1,n]$，设 $\gcd(n,k) = d$，则 $\gcd(\frac nd,\frac kd) = 1$，而又有 $\frac{k}{d} \times d = k$，所以 $k$ 会在且仅在 $\varphi(d)$ 中通过 $\frac{k}{d}$记入一次。似乎数论里面用处更多？组合计数不怎么考这个，考了也应该是偏向于数论求和之类的题目。 # 参考资料 - [command_block - 炫酷反演技巧](https://www.luogu.com.cn/article/83ub0lvq) - [command_block - Min-Max容斥小记](https://www.luogu.com.cn/article/t2zqvdou) - [command_block - 单位根反演小记](https://www.luogu.com.cn/article/4l2bmvkz) - [command_block - 多项式计数杂谈](https://www.luogu.com.cn/article/oy8l7j3n) - [command_block - 莫比乌斯反演与数论函数](https://www.luogu.com.cn/article/elmcfhks) - [Pbri - 子集反演学习笔记](https://www.cnblogs.com/Pbriqwq/p/15429971.html) - [RandomShuffle - 二项式系数](https://www.cnblogs.com/EmilyDavid/p/18624815) - [StayAlone - 双射之美——卡特兰数/反射容斥/格路计数](https://www.luogu.com.cn/article/dlc151ri) - wrpwrp - 组合数学进阶 - wrpwrp - 容斥与反演 - [zhiyangfan - 二项式系数](https://www.cnblogs.com/zhiyangfan/p/16014605.html) - [zt17 - Prüfer 序列学习笔记](https://www.luogu.com.cn/article/7v7id3ug)