生成函数与反演

· · 个人记录

本人水平较低，简单介绍反演，并用尝试用生成函数证明。
简单来说，反演就是已知 f_1,f_2,\dots,f_n 与 g_n 的关系，就能用 g_1,g_2,\dots g_n 求出 f_n。

那么首先说一个比较易证的，二项式反演：

g_n=\sum\limits_{i=0}^n\binom{n}{i}f_i \Leftrightarrow f_n=\sum\limits_{i=0}^n\binom{n}{i}(-1)^{n-i}g_i

设 \{f_n\}_{n=0}^\infty,\{g_n\}_{n=0}^\infty 的指数型生成函数分别为 f(x),g(x)。
如果对生成函数那一套比较熟悉，可以发现左边的式子是 f(x) 和 \text e^x 的卷积：

g(x)=f(x)\text e^x f(x)=g(x)\text e^{-x}

展开提取系数就得到

f_n=\sum\limits_{i=0}^n\binom{n}{i}(-1)^{n-i}g_i

二项式反演还有另一种形式：

g_k=\sum_{i=k}^n \binom ik f_i \Leftrightarrow f_k=\sum_{i=k}^n \binom ik (-1)^{i-k}g_i

这个暂时没有找到比较好的生成函数证法（用矩阵来看，实际就是上面的转置矩阵；而两个互逆的矩阵，转置后依然互逆，就能证明）。

Stirling 反演的证法是从 EI 那里看到的，感觉比较简洁（

g_n=\sum\limits_{i=0}^n\begin{Bmatrix} n \\ i \end{Bmatrix}f_i \Leftrightarrow f_n=\sum\limits_{i=0}^n(-1)^{n-i}\begin{bmatrix} n \\ i \end{bmatrix}g_i

还是设 \{f_n\}_{n=0}^\infty,\{g_n\}_{n=0}^\infty 的 EGF 为 f(x),g(x) 。

f(\text e^x-1)=\sum\limits_{k=0}^\infty\frac{(\text e^x-1)^k}{k!}f_k

根据第二类 Stirling 数的组合意义，不难发现上式为

\sum_{k=0}^\infty\left( \sum\limits_{n=0}^\infty \begin{Bmatrix} n \\k \end{Bmatrix}\frac{x^n}{n!}\right)f_k =\sum\limits_{n=0}^\infty \left(\sum\limits_{k=0}^\infty\begin{Bmatrix} n \\k \end{Bmatrix}f_k\right)\frac{x^n}{n!}=g(x)

设 z=\text e^x-1，换元得到

f(z)=g(\ln (1+z)) =\sum\limits_{k=0}^\infty\frac{\ln(1+z)^k}{k!}g_k =\sum\limits_{k=0}^\infty\left( \sum\limits_{n=0}^\infty (-1)^{n-k}\begin{bmatrix} n \\ k \end{bmatrix}\frac{z^n}{n!}\right)g_k =\sum\limits_{n=0}^\infty \left(\sum_{k=0}^\infty (-1)^{n-k} \begin{bmatrix} n \\ k \end{bmatrix}g_k\right) \frac{z^n}{n!}

于是得证。

然后就是 Mobius 反演，先来介绍一下 Dirichlet 生成函数。
对于数列 f， \{ f_n\}_{n=1}^\infty 的 Dirichlet 生成函数为：

f(s)=\sum\limits_{n=1}^\infty\frac{f_n}{n^s}

那么显然 \{1\}_{n=1}^\infty 的 Dirichlet 生成函数为

\zeta(s)=\sum\limits_{n=1}^\infty\frac{1}{n^s}

这也就是著名的 Riemann-Zeta 函数。

根据 Dirichlet 生成函数的定义，不难得到一个性质：
设 f(s),g(s) 分别是 \{ a_n \}_{n=1}^\infty 和 \{ b_n \}_{n=1}^\infty 的 Dirichlet 生成函数，那么 f(s)g(s) 为

\left \{ \sum\limits_{d|n}a_db_{\frac{n}{d}}\right \}_{n=1}^\infty

的 Dirichlet 生成函数。

接下来是重点，设 f(n) 为积性函数，那么 \{ f(n) \}_{n=1}^\infty 的 Dirichlet 生成函数可以写为乘积形式：
（以下 p 均表示质数）

\sum\limits_{n=1}^\infty \frac{f(n)}{n^s}=\prod_p\left( \sum\limits_{k=0}^\infty f(p^k)p^{-ks}\right)

证明：
设 n 的质因数分解为 p_1,p_2,\dots,p_m，质数幂为 a_1,a_2,\dots ,a_m，那么从右式可以推出

[n^{-s}]\prod_p\left( \sum\limits_{k=0}^\infty f(p^k)p^{-ks}\right) =\prod_p\left( [n^{-s}] \sum_{k=0}^\infty f(p^k)p^{-ks}\right) =\prod\limits_{i=1}^m[n^{-s}]f(p_i^{a_i})p_i^{-a_i s}

把乘积的右半部分拎出来，发现它就是 n^{-s}，所以原式变为

\prod_{i=1}^mf(p_i^{a_i})

又因为 f(n) 为积性函数，上式显然为 f(n)，于是得证。

然后你问扯了这么多，有什么用？
别急，先把 \zeta(s) 化为上面的乘积形式：

\zeta(s)=\prod_p\left( \sum\limits_{k=0}^\infty p^{-ks}\right) =\prod_p\frac{1}{1-p^{-s}}

Mobius 函数也是一个积性函数，它可以这样定义：

\mu(p^k)=\begin{cases} 1 &(k=0) \\ -1 &(k=1)\\ 0 & (k \ge 2)\end{cases}

由此也可以得到其 Dirichlet 生成函数：

\tilde{\mu}(s)=\prod_p(1-p^{-s})=\frac{1}{\zeta(s)}

最后就是证明 Mobius 反演：
设 f(s),g(s) 分别是 \{ a_n \}_{n=1}^\infty 和 \{ b_n \}_{n=1}^\infty 的 Dirichlet 生成函数，且

a_n=\sum_{d|n}b_d

那么

f(s)=\zeta(s)g(s) g(s)=f(s)\tilde{\mu}(s)

提取系数有

b_n=\sum_{d|n}\mu\left(\frac{n}{d} \right)a_d

Lagrange 反演可以已知 f(x)，且 g(f(x)) = x 的情况下，求出 g(x)^k 的系数（当然这里要求 f(x) 常数项为零，一次项非零）：

[x^n]g(x)^k = \frac kn [x^{n-k}] \left( \frac{x}{f(x)}\right)^n

它还有一个更加对称的形式，也是我们将要证明的：

n[x^n]g(x)^k=k[x^{-k}]f(x)^{-n}

首先需要证明一个引理，对于满足上述条件的 f(x)：

[x^{-1}]f'(x)f(x)^k=[k=-1] \ , \ k\in \mathbb Z

对于 k=-1 是显然成立的，其它情况只需发现 f(x)^{k+1} 求导后必然没有 x^{-1} 项（想想看，x^n 求导变成 nx^{n-1} 对于 n=0 是不成立的，没有哪个单项求导后是 x^{-1}）。

现在考虑 g^k\circ f=x^k，等式两边对 x 求导得到（注意这里没有把 (g^k)' 展开写为 kg^{k-1}g'）

((g^k)'\circ f)f'=kx^{k-1}

将左边展开，两边再同乘 f^{-n}：

\sum_{i=0}^\infty([x^i](g^k)')f^i f' = kx^{k-1} \sum_{i=0}^\infty([x^i](g^k)')f^{i-n} f' = kx^{k-1}f^{-n}

现在就可以利用引理，两边提取 x^{-1} 项系数，等式左边就只剩下 i=n-1 项非零，于是

[x^{n-1}](g^k)'=k[x^{-k}]f^{-n} n[x^n]g^k=k[x^{-k}]f^{-n}