摘自学长zsy的PPT。虽然没有原文链接，但为了表示对学长劳动成果的尊重，这里粘贴一个友情链接。zsy学长平时为人大方，上课生动有趣，并且对自己所讲的每个知识点都非常认真。推荐前往他的博客观摩学习。
我们都知道二项式的生成函数：
\[
f(x) = (1+x)^n = \sum_{k = 0}^{n}\dbinom{n}{k}x^k
\]
当我们带入\(x=-1\)时，会得到这样的式子：
\[
f(-1) = (1 - 1)^n = \sum_{k=0}^{n}\dbinom{n}{k}(-1)^k
\]
当\(n=0\)时，左边的部分没有意义。但右边算出来恰好为\(\binom{0}{0}=1\)。因此我们得到了一个恒等式：
\[
\sum_{k=0}^{n}\dbinom{n}{k}(-1)^{k} = [n = 0] = \epsilon(n + 1)
\]
假设我们知道\(f(n) = \sum_{k=0}^{n}\binom{n}{k}g(k)\)，那么我们如何用\(f(k)\)来表示\(g(n)\)呢？
我们首先拼凑出一个二项式的形式：
\[
g(n) = \sum_{m=0}^{n}[n = m]g(m) = \sum_{m=0}^{n}\epsilon(n - m + 1)g(m)
\]
然后代入上面那个恒等式：
\[
g(n) = \sum_{m=0}^{n}\sum_{k=0}^{n-m}(-1)^{k}\dbinom{n}{m}\dbinom{n-m}{k}g(m)
\]
根据组合的意义，不难得到：
\[
g(n) = \sum_{m=0}^{n}\sum_{k=0}^{n-m}(-1)^{k}\dbinom{n}{k}\dbinom{n-k}{m}g(m)
\]
接下来需要交换求和号。为了方便理解，我这里令\(S_{mk} = (-1)^{k}\dbinom{n}{k}\dbinom{n-k}{m}g(m)\)，那么原式就变成了\(\sum_{m=0}^{n}\sum_{k=0}^{n-m}S_{mk}\)。
\[
\begin{bmatrix}
S_{0,0} & S_{0,1} & \cdots & S_{0,n-1} & S_{0,n}\S_{1,0} & S_{1,1} & \cdots & S_{1,n-1}\\vdots & \cdots & \vdots\S_{n -1 , 0} & S_{n-1, 1}\S_{n,0}
\end{bmatrix}
\]
显然，之前的求法是一行一行，从左往右求和。我们同样以一列一列，从上往下求和。因此：
\[
g(n) = \sum_{k=0}^{n}\sum_{m=0}^{n-k}(-1)^{k}\dbinom{n}{k}\dbinom{n-k}{m}g(m)
\]
提出和\(m\)无关的系数：
\[
g(n) = \sum_{k=0}^{n}(-1)^k \dbinom{n}{k}\sum_{m=0}^{n-k}\dbinom{n-k}{m}g(m)
\]
注意到\(\sum_{m=0}^{n-k}\dbinom{n-k}{m}g(m)\)就是\(f(n-k)\)。因此：
\[
g(n) = \sum_{k=0}^{n}(-1)^k\dbinom{n}{k}f(n-k)
\]
这就是二项式反演了。通过它，我们可以利用二项式求和推出不好计算的答案。
说到底，反演还是和容斥脱不了干系。
原文：https://www.cnblogs.com/LinearODE/p/11574129.html