$反演定义$
若 $A$ 能用 $B$ 表示出来，那么如何用 $B$ 表示 $A$ 的过程被称作反演。
$二项式反演$
首先有二项式定理
$$
(a+b)^n =\sum_{i=0}^n \binom{n}{i} a^i b^{n-i}
$$
以下是三个常用二项式定理及其证明：
- 若有 $f_n = \sum_{i=0}^n \binom{n}{i} g_i$，则有 $g_n = \sum_{i=0}^n (-1)^{n-i} \binom{n}{i} f_i$
证明：
$$ g_n = \sum_{i=0}^n (-1)^i \binom{n}{i} f_i = \sum_{i=0}^n (-1)^{n-i} \binom{n}{i} \sum_{j=0}^i \binom{i}{j} g_j = \sum_{i=0}^n \sum_{j=0}^i (-1)^{n-i} \binom{n}{i} \binom{i}{j} g_j = \sum_{j=0}^n\binom{n}{j} g_j \sum_{i=j}^n (-1)^{n-i} \binom{n-j}{i - j} = \sum_{j=0}^n\binom{n}{j} g_j (1+(-1))^{n-j} = \sum_{j=0}^n [j=n]\binom{n}{j} g_j=g_n $$
- 若有 $f_k=\sum_{i=k}^n \binom{n}{i} g_i$，则有 $g_k = \sum_{i=k}^n (-1)^{i-k} \binom{n}{i} f_i$
证明：
$$ f_k=\sum_{i=k}^n \binom{n}{i} g_i\\\ f_k=\sum_{i=0}^k \binom{n}{i} g_{n-i}\\\ g_k = \sum_{i=k}^n (-1)^{i-k} \binom{n}{i} f_i \\\ g_k = \sum_{i=0}^k (-1)^{k-i} \binom{n}{i} f_{n-i} $$
尝试把 $g$ 翻转：
$$ f_k=\sum_{i=0}^k \binom{n}{i} g_{i}\\\ g_k = \sum_{i=0}^k (-1)^{k-i} \binom{n}{i} f_i $$
于是转化成了第一个式子，证毕。
- 若有 $f_n = \sum_{i=0}^n (-1)^i \binom{n}{i} g_i$，则有 $g_n = \sum_{i=0}^n (-1)^i \binom{n}{i} f_i$
证明：
$$ g_n = \sum_{i=0}^n (-1)^i \binom{n}{i} \sum_{j=0}^i (-1)^j \binom{i}{j} g_j=\sum_{j=0}^n (-1)^{j} \binom{n}{j} \sum_{i=j}^n (-1)^i \binom{n-j}{i-j} g_j=\sum_{j=0}^n (-1)^{j} \binom{n}{j} \sum_{i=0}^{n-j} (-1)^{i-j} \binom{n-j}{i} g_j=\sum_{j=0}^n \binom{n}{j} g_j \sum_{i=0}^{n-j} (-1)^{i} \binom{n-j}{i}= \sum_{j=0}^n \binom{n}{j} g_j (1+(-1))^{n-j} = g_n $$
$子集反演$
$$ f_S=\sum_{T\subseteq S} g_T \Leftrightarrow g_S = \sum_{T\subseteq S} (-1)^{|S|-|T|} f_T $$
证明用容斥原理。
$莫比乌斯反演$
它的狄利克雷卷积形式为：
$$
f = g *I \Leftrightarrow g = f * \mu
$$
它还有另一个式子：
$$
f_n = \sum_{n|d} g_d \Leftrightarrow g_n = \sum_{n|d} \mu(\frac{d}{n}) f_d
$$
