回来做个题发现二项式反演长什么样又忘记了。
记录一下在忘记二项式反演长什么样时如何推导（我怕是这辈子都想不到？）
二项式反演
有一个优(hao)美(bei)的公式：
[f_n = sum_{i = 0} ^ n (-1)^i dbinom{n}{i} g_i Leftrightarrow g_n = sum_{i = 0} ^ n (-1)^i dbinom{n}{i} f_i
]
还有一个实(nan)用(bei)的公式：
[f_n = sum_{i = 0} ^ n dbinom{n}{i} g_i Leftrightarrow g_n = sum_{i = 0} ^ n (-1) ^ {n - i} dbinom{n}{i} f_i
]
下面推导第一个：
因为忘了第一个长什么样，所有我们假设$$g_{n} = sum_{i = 0} ^ n t_{n,i} f_{i}$$
带入等式右边：
[egin{split} f_{n} &= sum_{i = 0} ^ n (-1) ^ i dbinom{n}{i} sum_{j = 0} ^ {i} t_{i,j} f_j \ &= sum_{i = 0} ^nf_i (sum_{j = i} ^ n (-1) ^j dbinom{n}{j} t_{j,i}) \ &= sum_{i = 0} ^ n f_i ( sum_{j = 0} ^ {n - i} (-1)^{j + i} dbinom{n}{j + i} t_{j + i, i} ) end{split}
]
我们要构造一个 $ t_{j,i} $ 满足 $$ [i = n] = sum_{j = 0} ^ {n - i} (-1)^{j + i} dbinom{n}{j + i} t_{j + i, i} $$
考虑用这个式子来代掉左边：$$ [n = 0] = sum_{i = 0} ^ n (-1) ^ i dbinom{n}{i} $$
因此$$ [i = n] = sum_{j = 0} ^ {n - i} (-1) ^ j dbinom{n - i}{j}$$
$ t_{j + i, i}$ 里面应该有一个组合数的形式，但是下面这个式子里面只有一个组合数，那么我们尝试配上一个。
[[i = n] = sum_{j = 0} ^ {n - i} (-1) ^ j dbinom{n - i}{j} dbinom{n}{i}
]
而这个可以处理成：
[[i = n] = sum_{j = 0} ^ {n - i} (-1) ^ j dbinom{j + i}{i} dbinom{n}{j + i}
]
比对一下就可以得到 $$ t_{i,j} = (-1)^j dbinom{i}{j} $$
其它的样子
有一个优(hao)美(bei)的公式：
[f_k = sum_{i = k} ^ n (-1) ^ i dbinom{i}{k} g_i Leftrightarrow g_k = sum_{i = k} ^ n (-1) ^ i dbinom{i}{k} f_i
]
还有一个实(nan)用(bei)的公式：
[f_{k} = sum_{i = k} ^ {n} dbinom{i}{k} g_{i} Leftrightarrow g_{k} = sum_{i = k} ^ n (-1) ^ {i - k} dbinom{i}{k} f_i
]
其它的理解
cly_none 告诉了一种奇妙的理解。
考虑 $$ f_{n} = sum_{i = 0} ^ n dbinom{n}{i} g_i$$ 这个式子，可以改写成：
[frac{f_{n}}{n!} = sum_{i=0} ^ n frac{g_i}{i!} frac{1}{(n-i)!}
]
在指数生成函数下就有 $$ f(x) = g(x) * e^x $$
那么$$ g(x) = f(x) * e^{-x} $$ ，直接展开回来就完成了二项式反演。