$反演定义$

若 $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$$