学习笔记 - 二项式反演

二项式反演

二项式反演的常见形式有如下两种：
\[ f(n) = \sum_{i=m}^n \binom ni g(i) \Longleftrightarrow g(n) = \sum_{i=m}^n (-1)^{n-i} \binom ni f(i) \]

\[ f(n) = \sum_{i=n}^m \binom in g(i) \Longleftrightarrow g(n) = \sum_{i=n}^m (-1)^{i-n} \binom in f(i) \]

我这里简要讲一下第一个式子的证明。只讲证明，不讲推导。
\[ \begin{align*} g(n) &= \sum_{i=m}^n(-1)^{n-i}\binom ni f(i)\ &= \sum_{i=m}^n(-1)^{n-i}\binom ni \sum_{j=m}^i \binom ijg(j)\ &= \sum_{j=m}^ng(j)\sum_{i=j}^n(-1)^{n-i}\binom ni\binom ij\ &= \sum_{j=m}^ng(j)\sum_{i=j}^n(-1)^{n-i}\binom nj\binom{n-j}{i-j}\ &= \sum_{j=m}^n\binom njg(j)\sum_{i=j}^n(-1)^{n-i}\binom{n-j}{i-j}\ &= \sum_{j=m}^n\binom njg(j)\sum_{t=0}^{n-j}(-1)^{n-j-t}\binom{n-j}t\ &= \sum_{j=m}^n\binom njg(j)(-1)^{n-j}\sum_{t=0}^{n-j}(-1)^{t}\binom{n-j}t\\end{align*} \]
可以发现，如果 \(n-j \neq 0\)，那么，\(\sum\limits_{t=0}^{n-j}(-1)^{t}\binom{n-j}t = 0\)。但是如果 \(n-j = 0\)，那么就只会算一个 \(\binom 00 = 1\)。也就是说，只有在 \(j=n\) 的时候，后面才会有用， 这个时候 \(\binom nn g(n)(-1)^0 = g(n)\)，因此 \(g(n) = g(n)\)。

证毕。

至于第二个式子，可以把第一个式子改造改造，或者用类似第一个式子的证法就可以证明了。

参考资料

https://www.cnblogs.com/GXZlegend/p/11407185.html

http://blog.miskcoo.com/2015/12/inversion-magic-binomial-inversion

---恢复内容结束---

学习笔记 - 二项式反演

原文：https://www.cnblogs.com/hankeke/p/binomial-inversion.html