摘自学长 zsy 的 PPT. 虽然没有原文链接, 但为了表示对学长劳动成果的尊重, 这里粘贴一个友情链接 https://www.cnblogs.com/zhoushuyu .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) \]
这就是二项式反演了. 通过它, 我们可以利用二项式求和推出不好计算的答案.
说到底, 反演还是和容斥脱不了干系.
来源: http://www.bubuko.com/infodetail-3210156.html