二项式反演

· · 算法·理论

简介：

有 g_i=\sum\limits_{j\le i} \binom{i}{j}f_j，求 f。

推导：

结论：f_i=\sum\limits_{j\le i}(-1)^{i-j}\binom{i}{j}g_j
证明：展开右边的式子。

\begin{aligned}f_i&=\sum\limits_{j\le i}(-1)^{i-j}\binom{i}{j}g_j\\&=\sum\limits_{j\le i}(-1)^{i-j}\binom{i}{j}\sum\limits_{k\le j}\binom{j}{k}f_k\\&=\sum\limits_{k\le i}f_k\sum\limits_{k\le j\le i}(-1)^{i-j}\binom{i}{j}\binom{j}{k}\\&=\sum\limits_{k\le i}f_k\sum\limits_{k\le j\le i}(-1)^{i-j}\binom{i}{k}\binom{i-k}{j-k}\\&=\sum\limits_{k\le i}f_k\binom{i}{k}\sum\limits_{k\le j\le i}(-1)^{i-j}\binom{i-k}{j-k}\end{aligned}

令 t=i-j，则 j-k=i-k-t,0\le t\le i-k。
继续推导：

\begin{aligned}f_i&=\sum\limits_{k\le i}f_k\binom{i}{k}\sum\limits_{0\le t\le i-k}(-1)^{t}\binom{i-k}{i-k-t}\\&=\sum\limits_{k\le i}f_k\binom{i}{k}\sum\limits_{0\le t\le i-k}(-1)^{t}1^{i-k-t}\binom{i-k}{t}\\&=\sum\limits_{k\le i}f_k\binom{i}{k}(-1+1)^{i-k}\end{aligned}

只有 k=i 时 (-1+1)^{i-k}\ne 0，且 \binom{i}{i}=1，因此等式正确，证毕。

推广：

反向：

当 g 的定义式不等号方向相反时，推出的关于 f 的式子的不等号也变向。
具体地，若有 g_i=\sum\limits_{j\ge i} \binom{j}{i}f_j，则 f_i=\sum\limits_{j\ge i} \binom{j}{i}(-1)^{j-i}g_j。
证明与上文类似，不做赘述。

多维：

若有 g_{a,b}=\sum\limits_{c\le a}\sum\limits_{d\le b}\binom{a}{c}\binom{b}{d}f_{c,d}，则有 f_{a,b}=\sum\limits_{c\le a}\sum\limits_{d\le b}\binom{a}{c}\binom{b}{d}(-1)^{a+b-c-d}g_{c,d}。
实际上 f,g 的每一维都是相互独立的，因此证明时将每一维都按上文方法展开即可。