反演

发表于 2021-05-08 分类于 ACM ，学习笔记，数学阅读次数： 16 本文字数： 461 阅读时长 ≈ 1 分钟

莫比乌斯反演

$\begin{array}{r} f (n) \circ g (n) = \sum_{d | n} f (d) \cdot g (\frac{n}{d}) \end{array}$

$f (n) = {\begin{cases} 1 & n = 1 \\ (- 1)^{k} & n = p_{1} \cdot p_{2} \cdot \cdot \cdot p_{k} \\ 0 & p^{k} | n, k > 1 \end{cases}$

若 $F (n) = \sum_{d | n} f (d)$

则 $f (n) = \sum_{d | n} μ (d) F (\frac{n}{d})$

$f_{n} = \sum_{i = 0}^{n} (- 1)^{i} (\binom{n}{i}) g_{i} \Leftrightarrow g_{n} = \sum_{i = 0}^{n} (- 1)^{i} (\binom{n}{i}) f_{i}$