反演

本页面大量引用 OI Wiki

组合数 [math]\displaystyle{ C_n^m }[/math] 常用符号 [math]\displaystyle{ \dbinom{n}{m} }[/math] 来表示，读作“[math]\displaystyle{ n }[/math] 选 [math]\displaystyle{ m }[/math]”。

组合数经典性质

选出 [math]\displaystyle{ m }[/math] 相当于选出 [math]\displaystyle{ n-m }[/math] 个排除。

[math]\displaystyle{ \dbinom{n}{m}=\dbinom{n}{n-m} }[/math]

组合数的递推式（杨辉三角）

[math]\displaystyle{ \dbinom{n}{m}=\dbinom{n-1}{m}+\dbinom{n-1}{m-1} }[/math]

基础性质（杨辉三角的一行、[math]\displaystyle{ (1+1)^n }[/math]）

[math]\displaystyle{ \dbinom{n}{0}+\dbinom{n}{1}+\dots+\dbinom{n}{n}=\sum_{i=0}^n\dbinom{n}{i}=2^n }[/math]

范德蒙德恒等式

[math]\displaystyle{ \sum_{i=0}^k\dbinom{n}{i}\dbinom{m}{k-i}=\dbinom{m+n}{k} }[/math]

二项式定理

[math]\displaystyle{ (a+b)^n=\sum_{i=0}^n\dbinom{n}{i}a^{n-i}b^i }[/math]

二项式反演

记 [math]\displaystyle{ f_n }[/math] 表示恰好使用 [math]\displaystyle{ n }[/math] 个不同元素形成特定结构的方案数，[math]\displaystyle{ g_n }[/math] 表示从 [math]\displaystyle{ n }[/math] 个不同元素中选出 [math]\displaystyle{ i \geq 0 }[/math] 个元素形成特定结构的总方案数．

若已知 [math]\displaystyle{ f_n }[/math] 求 [math]\displaystyle{ g_n }[/math]，那么显然有：

[math]\displaystyle{ g_n = \sum_{i = 0}^{n} \binom{n}{i} f_i }[/math]

若已知 [math]\displaystyle{ g_n }[/math] 求 [math]\displaystyle{ f_n }[/math]，那么：

[math]\displaystyle{ f_n = \sum_{i = 0}^{n} \binom{n}{i} (-1)^{n-i} g_i }[/math]

上述已知 [math]\displaystyle{ g_n }[/math] 求 [math]\displaystyle{ f_n }[/math] 的过程，就称为“二项式反演”．

莫比乌斯反演

莫比乌斯函数

莫比乌斯函数（Möbius 函数）定义为

[math]\displaystyle{ \mu(n)= \begin{cases} 1,&n=1,\\ 0,&n\text{是某个质数平方的倍数},\\ (-1)^k,&n \text{是} k \text{个不同质数的乘积}.\\ \end{cases} }[/math]

具体地，假设正整数 [math]\displaystyle{ n }[/math] 有素因数分解 [math]\displaystyle{ n=\prod_{i=1}^kp_i^{e_i} }[/math]，其中，[math]\displaystyle{ p_i }[/math] 是素数，[math]\displaystyle{ e_i }[/math] 是正整数．那么，三种情形分别对应：

1. [math]\displaystyle{ \mu(1) = 1 }[/math]；
2. 当存在 [math]\displaystyle{ i }[/math] 使得 [math]\displaystyle{ e_i>1 }[/math]，即存在任何素因数出现超过一次时，[math]\displaystyle{ \mu(n)=0 }[/math]；
3. 否则，对于所有 [math]\displaystyle{ i }[/math] 都有 [math]\displaystyle{ e_i = 1 }[/math]，即任何素因数都只出现一次时，[math]\displaystyle{ \mu(n)=(-1)^k }[/math]，其中，$k$ 就是互异素因子的个数．

莫比乌斯反演

设 [math]\displaystyle{ f(n),g(n) }[/math] 是两个数论函数．那么，有

[math]\displaystyle{ f(n) = \sum_{d\mid n}g(d) \iff g(n) = \sum_{d\mid n}\mu\left(\dfrac{n}{d}\right)f(d). }[/math]

扩展

[math]\displaystyle{ f(n) = \sum_{n\mid d}g(d) \iff g(n) = \sum_{n\mid d}\mu\left(\dfrac{d}{n}\right)f(d). }[/math]