二項式反演的證明
摘自學長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)
\]
把它改寫成更加直觀的形式：
\[ g(n) = \sum_{k=0}^{n}(-1)^{n-k}\dbinom{n}{k}f(k)
\]
這就是二項式反演了。通過它，我們可以利用二項式求和推出不好計算的答案。
說到底，反演還是和容斥脫不了干系。
浙公網安備 33010602011771號