前置知识
二项式定理：\((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\)，所以反演一下就能得到答案。
标签：aligned,sum,笔记,ng,反演,binom,二项式 From： https://www.cnblogs.com/rlc202204/p/17976385