1. 从“容斥原理”到“反演公式”的思维跃迁很多人第一次接触二项式反演和斯特林反演是在组合数学的课堂上。老师写下一串公式然后说“这个很重要考试会考”底下一片抄笔记的声音。但真正到了做题或者做项目的时候你会发现一个尴尬的事实公式背得滚瓜烂熟却不知道什么时候该用哪一个更不知道这些反演到底在“反”什么。我当初也是这样。直到后来做算法竞赛和概率建模的时候被几个计数问题反复折磨才逼着自己把这两个反演从根上捋了一遍。这篇文章就是那次梳理的产物我会尽量用“人话”把这两个反演讲清楚包括它们各自解决什么问题、公式怎么来的、什么时候用哪个、以及实际做题时有哪些容易踩的坑。先说结论二项式反演和斯特林反演本质上都是容斥原理的代数化表达。它们做的事情是同一件——在“恰好”和“至少/至多”之间建立桥梁。区别在于二项式反演处理的是普通集合的计数问题而斯特林反演处理的是“划分”结构的计数问题。理解了这一点你就不会再把它们当成两个孤立的公式来背了。这篇文章适合谁如果你正在学组合数学、准备算法竞赛、或者在做概率统计相关的建模工作需要频繁处理“恰好k个满足条件”这类计数问题那这篇内容应该能帮你省下不少翻书和推导的时间。如果你只是好奇这两个名词是什么意思也能看懂我会尽量把前置知识补全。2. 二项式反演在“恰好”与“至少”之间自由切换2.1 一个让人头疼的经典问题先看一个具体的问题这样后面的公式才有落脚点。假设有n个元素其中有m个是“特殊元素”。现在要从这n个元素中选出k个要求恰好包含r个特殊元素。问有多少种选法这个问题的答案很直接从m个特殊元素中选r个再从n-m个普通元素中选k-r个所以答案是C(m,r)·C(n-m,k-r)。这是“恰好”的计数很好算。但如果问题反过来呢已知对于所有的i从n个元素中选k个、至少包含i个特殊元素的方案数是已知的能不能反推出“恰好”包含r个特殊元素的方案数这就是二项式反演要解决的问题。在实际应用中“至少”往往比“恰好”更容易算因为“至少”允许我们把约束放宽用更简单的组合数表达。而“恰好”往往是我们最终需要的答案。二项式反演就是这两者之间的桥梁。2.2 公式的两种等价形式二项式反演的标准形式是这样的如果对于所有的n有$$g(n) \sum_{i0}^{n} \binom{n}{i} f(i)$$那么$$f(n) \sum_{i0}^{n} (-1)^{n-i} \binom{n}{i} g(i)$$反过来也成立如果$$g(n) \sum_{i0}^{n} (-1)^i \binom{n}{i} f(i)$$那么$$f(n) \sum_{i0}^{n} (-1)^i \binom{n}{i} g(i)$$这两种形式看起来很像区别在于符号的位置。实际用的时候你只需要记住一个核心特征一个方向是“求和”另一个方向是“交错求和”。交错求和里的(-1)的幂次就是反演的灵魂。为什么会有(-1)的幂次这要从容斥原理说起。容斥原理的核心思想是要算“恰好满足所有条件”的数量需要从“至少满足一个条件”开始减去“至少满足两个条件”的加上“至少满足三个条件”的以此类推。这个加减交替的过程在代数上就表现为(-1)的幂次。2.3 从“至少”到“恰好”的推导过程我用一个具体的例子把推导过程走一遍这样你能看清楚(-1)是怎么冒出来的。假设我们有一个集合S|S|n。我们想算“恰好有0个元素满足性质P”的子集数量。设f(i)表示“恰好有i个元素满足性质P”的子集数量g(i)表示“至少有i个元素满足性质P”的子集数量。显然g(i)和f(j)的关系是$$g(i) \sum_{ji}^{n} \binom{j}{i} f(j)$$这个式子的意思是从“恰好有j个满足性质”的集合中选出i个满足性质的元素剩下的j-i个也满足性质但没被选中。所以“至少有i个”就是所有j≥i的“恰好有j个”的并集。现在我们要从这个关系里解出f(n)。这是一个上三角的线性方程组可以用递推的方式解也可以用生成函数的方法。但最直观的方法是容斥“恰好有0个满足性质” “至少有0个” - “至少有1个” “至少有2个” - ...写成公式就是$$f(0) \sum_{i0}^{n} (-1)^i \binom{n}{i} g(i)$$这就是二项式反演的一种特殊形式。更一般的形式可以通过类似的容斥推导得到。关键点在于反演公式中的组合数系数和(-1)的幂次都是容斥原理的直接产物。2.4 实际做题时怎么判断该用哪个方向这是很多人最困惑的地方。我的经验是看哪个量容易算。如果“至少”容易算那就设g为“至少”f为“恰好”用第一个方向的公式从g反推f。如果“恰好”容易算那就反过来。但大多数情况下“至少”比“恰好”好算因为“至少”允许你忽略一些约束。举个例子n对夫妻围成一圈要求每对夫妻相邻。问有多少种排列方式这个问题直接算“恰好每对夫妻相邻”比较麻烦因为要处理夫妻内部的顺序和夫妻之间的相对位置。但如果我们先算“至少有i对夫妻相邻”的方案数就会简单很多——把相邻的夫妻捆绑成一个整体然后做圆排列。算出g(i)之后再用二项式反演求出f(n)也就是恰好n对夫妻都相邻的方案数。注意用二项式反演的时候一定要确认g(i)的定义是“至少有i个满足”还是“恰好有i个满足”。定义搞错了反演出来的结果就是错的。我见过太多人在这里翻车。2.5 一个容易踩的坑组合数的边界条件二项式反演里有一个很容易被忽略的细节当in时C(n,i)0。这个看起来是废话但在实际计算中很多人会忘记处理边界导致求和范围写错。比如如果f(i)只在i≤m时有定义mn那么g(n)的求和实际上只到m而不是到n。这时候反演公式的求和上限也要相应调整。如果你直接套公式写到n虽然数学上没错因为后面的项都是0但计算上会多算很多无用的项在编程实现时可能导致效率问题。另外当n比较大时组合数的计算需要用模运算和逆元这时候(-1)的幂次处理也要小心。我的习惯是先把(-1)的幂次单独拿出来根据n-i的奇偶性决定符号然后再乘组合数。这样不容易出错。3. 斯特林反演当“划分”成为计数对象3.1 从“集合划分”说起二项式反演处理的是“选元素”的问题而斯特林反演处理的是“划分”的问题。什么是划分把一个集合分成若干个非空的子集每个子集内部元素无序子集之间也无序这就是一个划分。比如集合{1,2,3}的划分有{{1},{2},{3}}3个块{{1,2},{3}}2个块{{1,3},{2}}2个块{{2,3},{1}}2个块{{1,2,3}}1个块所以3个元素的集合共有5种划分其中1个块的1种2个块的3种3个块的1种。第二类斯特林数S(n,k)就是用来表示“n个元素的集合恰好分成k个非空子集”的方案数。上面的例子中S(3,1)1S(3,2)3S(3,3)1。斯特林反演要解决的问题是已知“至多分成k个块”或者“至少分成k个块”的方案数如何反推出“恰好分成k个块”的方案数。3.2 斯特林数的两种形式和递推关系在讲反演之前先把斯特林数的基本性质理清楚。第二类斯特林数S(n,k)有一个很重要的递推关系$$S(n,k) S(n-1,k-1) k \cdot S(n-1,k)$$这个递推的意思是考虑第n个元素它有两种归宿。第一种它自己单独成一个块那么剩下的n-1个元素分成k-1个块方案数是S(n-1,k-1)。第二种它加入已有的某个块那么剩下的n-1个元素先分成k个块有S(n-1,k)种分法然后第n个元素可以加入这k个块中的任意一个所以乘k。这个递推是计算斯特林数的基础也是理解斯特林反演的钥匙。因为反演公式里的系数本质上就是从这个递推关系里来的。另外第二类斯特林数还有一个显式公式$$S(n,k) \frac{1}{k!} \sum_{i0}^{k} (-1)^i \binom{k}{i} (k-i)^n$$这个公式本身就是一个小型的容斥把n个元素分配到k个有标号的盒子中允许空盒方案数是k^n。然后容斥掉有空盒的情况再除以k!去掉盒子的标号就得到了S(n,k)。3.3 斯特林反演的公式长什么样斯特林反演有两种分别对应第一类斯特林数和第二类斯特林数。这里主要讲第二类因为它在组合计数中更常用。如果$$g(n) \sum_{i0}^{n} S(n,i) f(i)$$那么$$f(n) \sum_{i0}^{n} s(n,i) g(i)$$其中s(n,i)是第一类斯特林数带符号的。反过来如果$$g(n) \sum_{i0}^{n} s(n,i) f(i)$$那么$$f(n) \sum_{i0}^{n} S(n,i) g(i)$$这里的第一类斯特林数s(n,i)满足递推$$s(n,k) s(n-1,k-1) - (n-1) \cdot s(n-1,k)$$注意这里的负号它和容斥里的(-1)是同一个来源。3.4 和二项式反演的本质联系看到这里你可能会觉得斯特林反演和二项式反演长得挺像的都是“一个求和对应一个反演求和”。没错它们确实是同一套代数结构在不同基下的表现。具体来说二项式反演对应的是“二项式基”也就是C(n,k)这个基。而斯特林反演对应的是“斯特林基”也就是S(n,k)和s(n,k)。在组合数学里这两组基可以互相转换转换矩阵就是斯特林数矩阵。从更高的视角看这两个反演都是“Möbius反演”在特定偏序集上的实例。二项式反演对应的是布尔格子集格上的Möbius函数而斯特林反演对应的是划分格上的Möbius函数。如果你学过偏序集理论这个联系会让你对整个反演体系有更清晰的认识。但如果你没学过也没关系。你只需要记住二项式反演管“选”斯特林反演管“分”。选元素的问题用二项式分块的问题用斯特林。这个直觉在大多数情况下都是对的。3.5 什么时候该用斯特林反演判断标准很简单如果问题里出现了“划分”“分组”“分堆”“非空子集”这些词而且你需要从“至多/至少分成k组”反推“恰好分成k组”那就用斯特林反演。举个例子n个不同的球放入m个相同的盒子要求每个盒子非空。问有多少种放法这个问题的答案直接就是S(n,m)。但如果问题变成n个不同的球放入m个相同的盒子允许空盒问有多少种放法这时候答案就是$\sum_{k1}^{m} S(n,k)$。如果你已知的是“允许空盒”的方案数想反推“恰好用k个盒子”的方案数那就需要斯特林反演。再比如在概率论中计算“恰好有k个事件发生”的概率时如果已知“至少有k个事件发生”的概率也可以用斯特林反演来转换。不过这种情况下二项式反演可能更直接因为事件的发生与否是“选”的问题不是“分”的问题。我的经验是先判断问题的结构是“选择”还是“划分”。如果是选择优先考虑二项式反演如果是划分优先考虑斯特林反演。如果两者都不像那可能根本不需要反演直接算就行了。4. 两个反演的实战对比同一道题的不同解法4.1 问题设定为了让你更清楚地看到两个反演的区别和联系我用一道题来演示。这道题是我在准备算法竞赛时遇到的当时用了两种方法做结果一样但过程完全不同。题目有n个不同的元素现在要给它们染上k种颜色中的一种要求每种颜色至少出现一次。问有多少种染色方案这个问题看起来很简单但它是理解两个反演的好例子。因为“每种颜色至少出现一次”这个约束既可以从“选择”的角度理解选哪些元素染某种颜色也可以从“划分”的角度理解把元素分成k组每组对应一种颜色。4.2 用二项式反演求解设f(i)表示“恰好使用i种颜色”的方案数g(i)表示“至多使用i种颜色”的方案数。g(i)很容易算每个元素有i种选择所以g(i)i^n。而g(i)和f(j)的关系是$$g(i) \sum_{j0}^{i} \binom{i}{j} f(j)$$这个式子的意思是至多使用i种颜色等价于从i种颜色中选出j种来实际使用然后这j种颜色恰好都被用到。所以g(i)是f(j)的二项式变换。现在我们要的是f(k)。根据二项式反演$$f(k) \sum_{i0}^{k} (-1)^{k-i} \binom{k}{i} g(i) \sum_{i0}^{k} (-1)^{k-i} \binom{k}{i} i^n$$这就是答案。你可以验证一下当nk时这个式子给出k!也就是k种颜色全排列的方案数符合直觉。4.3 用斯特林反演求解换一个角度。把n个元素分成k个非空子集每个子集染一种颜色然后给这k个子集分配k种颜色。方案数是$$S(n,k) \cdot k!$$而S(n,k)可以用显式公式算$$S(n,k) \frac{1}{k!} \sum_{i0}^{k} (-1)^i \binom{k}{i} (k-i)^n$$所以总方案数是$$k! \cdot S(n,k) \sum_{i0}^{k} (-1)^i \binom{k}{i} (k-i)^n$$令jk-i这个式子就变成了$$\sum_{j0}^{k} (-1)^{k-j} \binom{k}{j} j^n$$和二项式反演的结果完全一样。4.4 两种解法的对比分析从计算量上看两种方法最终都归结为同一个求和式所以复杂度是一样的。但从思维过程上看二项式反演更直接你只需要定义“至多”和“恰好”然后套公式。而斯特林反演需要你先想到“划分”这个结构再引入斯特林数最后还要用显式公式展开。所以在这个问题里二项式反演是更自然的选择。但这并不意味着斯特林反演没用。如果问题变成“把n个元素分成k组每组至少两个元素”那二项式反演就不太好用了因为“至多分成k组”这个量不好算。而斯特林反演可以通过调整斯特林数的定义来处理这种约束。我的建议是先尝试用二项式反演如果发现“至多/至少”的量不好算再考虑斯特林反演。大多数组合计数问题二项式反演都能搞定。斯特林反演是备选方案但在处理划分结构时更强大。5. 编程实现中的细节与优化5.1 预处理组合数和斯特林数在实际编程中二项式反演和斯特林反演都需要频繁计算组合数或斯特林数。如果每次都用公式现算时间复杂度会很高。所以通常的做法是预处理。对于组合数用杨辉三角或者阶乘加逆元都可以。如果n比较小比如n≤2000杨辉三角最简单MAXN 2005 C [[0]*MAXN for _ in range(MAXN)] for i in range(MAXN): C[i][0] C[i][i] 1 for j in range(1, i): C[i][j] (C[i-1][j-1] C[i-1][j]) % MOD如果n比较大比如n≤10^6就需要用阶乘和逆元fact [1] * (MAXN) inv_fact [1] * (MAXN) for i in range(1, MAXN): fact[i] fact[i-1] * i % MOD inv_fact[MAXN-1] pow(fact[MAXN-1], MOD-2, MOD) for i in range(MAXN-2, -1, -1): inv_fact[i] inv_fact[i1] * (i1) % MOD def comb(n, k): if k 0 or k n: return 0 return fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD对于第二类斯特林数如果只需要一行固定n所有k可以用容斥公式直接算def stirling_second_row(n): S [0] * (n1) for k in range(n1): for i in range(k1): term comb(k, i) * pow(k-i, n, MOD) % MOD if i % 2 0: S[k] (S[k] term) % MOD else: S[k] (S[k] - term) % MOD S[k] S[k] * inv_fact[k] % MOD return S如果需要整个表所有n和k用递推更合适S [[0]*(MAXN) for _ in range(MAXN)] S[0][0] 1 for i in range(1, MAXN): for j in range(1, i1): S[i][j] (S[i-1][j-1] j * S[i-1][j]) % MOD5.2 反演求和的实现技巧二项式反演的求和式是$$f(n) \sum_{i0}^{n} (-1)^{n-i} \binom{n}{i} g(i)$$在代码里这个求和可以直接翻译成循环。但有一个小技巧把(-1)的幂次和组合数合并处理避免重复计算。def binomial_inversion(g, n): f 0 for i in range(n1): term comb(n, i) * g[i] % MOD if (n - i) % 2 1: f (f - term) % MOD else: f (f term) % MOD return f % MOD斯特林反演的求和式类似只是把组合数换成斯特林数。如果已经预处理了斯特林数表直接查表就行。5.3 常见错误与调试方法我在实现这两个反演时踩过几个典型的坑这里列出来帮你避雷。第一个坑符号搞反。(-1)的幂次到底是n-i还是i取决于你用的是哪个方向的公式。我的建议是先用小数据验证。比如n2手动算一遍看看代码输出对不对。如果不对把符号反过来再试。第二个坑边界条件。当i0时g(0)是否有定义在很多问题里g(0)表示“至多0个”或者“恰好0个”这个值可能是0也可能是1取决于具体问题。如果搞错了整个反演结果都会偏。第三个坑模运算下的负数。在Python里负数取模会自动变成正数但在C里不会。如果你用C写记得在每次减法后加MOD再取模。第四个坑组合数溢出。如果不用模运算组合数会非常大超出整数范围。即使是用Python的大整数计算速度也会很慢。所以只要题目要求取模就一定要用模运算。调试的时候我习惯先用暴力枚举写一个小规模的版本然后用反演公式写一个版本对比两者的输出。如果一致再放大规模。这个方法虽然笨但很有效。6. 从公式到直觉建立自己的理解框架6.1 反演的本质是“换基”如果你学过线性代数可以把反演理解成“换基”。在组合数学里我们有两组基一组是“恰好”基一组是“至多/至少”基。反演公式就是这两组基之间的转换矩阵。二项式反演的转换矩阵是二项式系数矩阵斯特林反演的转换矩阵是斯特林数矩阵。这两个矩阵都是三角矩阵所以转换是可逆的。反演公式就是求逆矩阵的结果。这个视角的好处是你不需要死记公式只需要记住“我在哪组基下要换到哪组基”。转换的方向决定了你用哪个公式。6.2 容斥原理是共同的根不管是二项式反演还是斯特林反演它们的根都是容斥原理。容斥原理说要算“恰好满足所有条件”的数量就从“至少满足一个”开始交替加减。这个交替加减的过程在代数上就是(-1)的幂次。所以你在反演公式里看到的(-1)不是凭空冒出来的而是容斥的直接体现。理解了这一点你就不会觉得反演公式是“天上掉下来的”了。它只是容斥原理的一种紧凑写法。6.3 什么时候不需要反演最后说一个反直觉的观点大多数时候你不需要反演。如果你要算“恰好k个满足条件”的方案数而“恰好”本身就好算那就直接算不用反演。反演只在“恰好”不好算、但“至多/至少”好算的时候才有用。我见过很多人一看到“恰好”两个字就条件反射地套反演公式结果把简单问题复杂化了。比如“从n个元素中选k个恰好包含r个特殊元素”这个“恰好”直接就算出来了根本不需要反演。所以在用反演之前先问自己“恰好”真的不好算吗如果好算就别折腾了。6.4 个人经验从“背公式”到“用公式”我学这两个反演的经历大概经历了三个阶段。第一个阶段是“背公式”。考试前把公式抄在手上做题的时候对照着套。这个阶段能做对题但心里没底换个问法就懵了。第二个阶段是“推公式”。每次做题都从头推一遍容斥虽然慢但理解深了。这个阶段的缺点是效率低考试时间不够用。第三个阶段是“用直觉”。看到一个问题先判断它是“选”还是“分”然后直接写反演公式不用再推了。这个阶段的前提是你已经把前两个阶段走完了。如果你现在还在第一个阶段别着急多推几遍自然就过渡到第三个阶段了。这两个反演不难难的是建立正确的直觉。一旦直觉建立了公式就是顺手拈来的工具。
