反演（莫比乌斯反演、二项式反演）原理及应用
莫比乌斯函数（Möbius function）
定义
莫比乌斯函数[latex]\mu(n)[/latex]定义为：
[latex display=”true”]\mu(n) = \begin{cases} 1 & (n=1) \\ (-1)^k & (n = p_1p_2 \cdots p_k) \\ 0 & (p^k|n, k > 1) \end{cases}[/latex]
文字描述是这样的。定义[latex]\mu(1)=1[/latex]；如果n是k个互异的质因数的乘积，则[latex]\mu(n)=(-1)^k[/latex]；如果n中含有一个质因数的次数超过1，则[latex]\mu(n)=0[/latex]。
这是一个积性函数。
性质
- [latex]\sum_{d|n} \mu(d) = \begin{cases} 1 & (n=1) \\ 0 & (n \neq 1) \end{cases}[/latex]
- [latex]\sum_{d|n} \frac{\mu(d)}{d} = \frac{\varphi(n)}{n}[/latex]
狄利克雷卷积（Dirichlet convolution）
定义
对于数论函数f(n)和g(n)，定义其狄利克雷卷积为
[latex display=”true”] (f * g)(n) = \sum_{d|n} f(d)g(\frac{n}{d}) [/latex]
性质
- 交换律：[latex]f * g = g * f[/latex]
- 结合律：[latex]f * (g * h) = (f * g) * h[/latex]
- 对加法的分配律：[latex]f * (g + h) = f * g + f * h[/latex]
- 积性函数的点积和狄利克雷卷积也是积性函数
莫比乌斯反演（Möbius inversion）
假设数论函数f(n)与F(n)满足：[latex]F(n) = \sum_{d|n} f(d)[/latex]，则
[latex display=”true”] f(n) = \sum_{d|n} \mu(d) F(\frac{n}{d}) [/latex]
另外一种形式：
假设数论函数f(n)与F(n)满足：[latex]F(n) = \sum_{n|d} f(d)[/latex]，则
[latex display=”true”] f(n) = \sum_{n|d} \mu(\frac{d}{n}) F(d) [/latex]
二项式反演
[latex display=”true”] f(n) = \sum_{i=0}^n \mathrm{C}_n^i g(i) \Rightarrow g(n) = \sum_{i=0}^n (-1)^{n-i} \mathrm{C}_n^i f(i)[/latex]
