二项式反演学习笔记
rlc202204
·
·
个人记录
前置知识
二项式定理：(a+b)^n=\sum_{i=0}^n\binom{n}{i}a^ib^{n-i}。
二项式反演
反演公式1：
f(n) = \sum_{i=0}^n\binom{n}{i}g(i) \iff g(n)=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f(i)
证明：
\begin{aligned}
\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f(i)
&= \sum_{i=0}^n(-1)^{n-i}\binom{n}{i}\sum_{j=0}^i\binom{i}{j}g(j)\\
&= \sum_{j=0}^ng(j)\sum_{i=j}^n(-1)^{n-i}\binom{n}{i}\binom{i}{j}\\
\end{aligned}
然后我们需要应用到组合数的一个结论：
\binom{n}{i}\binom{i}{j}=\binom{n}{j}\binom{n - j}{i - j}
尝试用组合意义理解：我们要在 n 个数中选一个 i 元子集 A，再选一个属于 A 的 j 元子集 B，左边就是先选 A 再选 B，右边是先选 B 再选 A，所以两者相等。
所以：
\begin{aligned}
\sum_{j=0}^ng(j)\sum_{i=j}^n(-1)^{n-i}\binom{n}{i}\binom{i}{j}
&=\sum_{j=0}^ng(j)\sum_{i=j}^n(-1)^{n-i}\binom{n}{j}\binom{n-j}{i-j}\\
&=\sum_{j=0}^ng(j)\binom{n}{j}\sum_{i=j}^n(-1)^{n-i}\binom{n-j}{i-j}\\
&=\sum_{j=0}^ng(j)\binom{n}{j}\sum_{i=0}^{n-j}(-1)^{n-(i+j)}\binom{n-j}{(i+j)-j}\\
&=\sum_{j=0}^ng(j)\binom{n}{j}\sum_{i=0}^{n-j}(-1)^{(n-j)-i}\binom{n-j}{i}\\
&=\sum_{j=0}^ng(j)\binom{n}{j}(1-1)^{n-j}\\
&=g(n)
\end{aligned}
得证。
反演公式2：
f(n)=\sum_{i=0}^n\binom{n}{i}(-1)^{i}g(n)
\iff
g(n)=\sum_{i=0}^n\binom{n}{i}(-1)^{i}f(n)
反演公式3：
f(k)=\sum_{i=k}^n\binom{i}{k}g(i)
\iff
g(k)=\sum_{i=k}^n(-1)^{i - k}\binom{i}{k}f(i)
应用
关键：要求 g(n)，尝试找到 f(n) = \sum_{i=0}^n\binom{n}{i}g(i) 且 f(n) 便于计算，然后用反演求出 g(n)。
题目1： 求错排数。
思路：
这个经典问题可以用二项式反演来做。
我们让 f_n=n!，D_n 表示错排数。
则会有：
f_n=\sum_{i=0}^n\binom{n}{i}D_i
还是组合意义来理解，每个排列都有若干个位置满足 p_i=i，我们先枚举有多少个位置，再枚举哪些位置，剩下的必然是错排了。
于是我们可以直接二项式反演：
\begin{aligned}
D_n
&=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f_i\\
&=\sum_{i=0}^n(-1)^{n-i}\frac{n!}{i!(n-i)!}i!\\
&=\sum_{i=0}^n(-1)^{n-i}\frac{n!}{(n-i)!}\\
&=n!\sum_{i=0}^n\frac{(-1)^{n-i}}{(n-i)!}\\
&=n!\sum_{i=0}^n\frac{(-1)^{i}}{i!}\\
\end{aligned}
题目2： 有 n 个格子排成一行，需要用 k 种颜色染色，要求两两不同色且每种颜色至少出现一次。求方案数。
思路：
我们设 f_k 表示用 k 种颜色染色两两不同色，但是不要求每种颜色至少出现一次。
再设 g_k 表示表示用 k 种颜色染色两两不同色，要求每种颜色至少出现一次。
于是我们有：
f_k=\sum_{i=0}^k \binom{k}{i}g_i
如何理解？首先对于任何一种染色方案，我们必然是选取了 k 颜色的一个子集去染，枚举选了哪些子集即可。
至于 f_k，这其实是 HNOI越狱 这题，我们可以知道 f_k=k(k-1)^{n-1}，于是：
g_k=\sum_{i=0}^k(-1)^{k-i}\binom{k}{i}i(i-1)^{n-1}
然后就做完了。
题目3： 求第二类斯特林数。
思路：
首先假设盒子有区别。
同理，f_k 表示盒子可以为空，g_k 表示盒子不能为空，可以得到：
f_k = \sum_{i=0}^k\binom{k}{i}g_i
又由于 f_k = k^m，所以反演一下就能得到答案。