生成函数 学习笔记
这里涉及的记号比较多，建议查阅 博客符号&记号参照表
这篇文章最早写于 2022年9月25日，但是当时基本没怎么理解生成函数。
本文的内容会不断添加更多东西，因为生成函数涉及的内容还是挺多的。
upd. 另外，可以参考 《组合数学》 §2.3 学习笔记（上） 。
生成函数简介
相信有很多初学者都很好奇，这个生成函数到底在干什么，为什么要搞这些东西。
至少我当时也没搞明白，特别是为什么它可以在式子没有意义的情况下还能算出正确答案。
因此本文会从生成函数最基础的部分出发，较为详细的解释什么是生成函数。
例1：有 \(1\) 克、\(2\) 克、\(3\) 克、\(4\) 克的砝码各一枚，能称出哪几种重量？每种重量各有几种可能方案？
我不打算讲传统解法，直接讲生成函数的解法
我们可以把 \(1\) 克砝码看作 \((1 + x^1)\) ，前者表示不取，后者表示取一个 \(1\) 克砝码
同理，我们可以用 \((1 + x^2)\) 表示不取或取一个 \(2\) 克砝码，用 \((1 + x^3)\) 表示不取或取一个 \(3\) 克砝码等
那么生成函数（实际上是普通生成函数）就是 \[ \begin{aligned} F(x) &= \left(1+x^1\right)\left(1+x^2\right)\left(1+x^3\right)\left(1+x^4\right) \\[6pt]&= 1+x+x^2+2 x^3+2 x^4+2 x^5+2 x^6+2 x^7+x^8+x^9+x^{10} \end{aligned} \] 可以发现，如果记次数为 \(n\) ，系数为 \(a_n\) ，则重量为 \(n\) 的情况有 \(a_n\) 种方案。
相信各位已经发现了，生成函数实际上利用了多项式相乘中的组合意义，利用多项式的形式来计算组合问题。
不过先不急着下太多结论，我们再看个例子。
例2：求用\(1\)分、\(2\)分、\(3\)分的邮票贴出不同数值的方案数，每种邮票的数量是无限多的。
直接给出生成函数 \[ F(x) = \left(1+x+x^2+x^3+\ldots\right)\left(1+x^2+x^4+x^6+\ldots\right)\left(1+x^3+x^6+x^9+\ldots\right) \] 相信熟悉麦克劳林级数的同学已经想到了这个公式 \[ \frac{1}{1-x}=\sum_{n=0}^{\infty} x^n=1+x+x^2+\cdots+x^n+\cdots \quad(|x| < 1) \] 如果代入符合条件的 \(x^k\) 则有 \[ \frac{1}{1-x^k} =\sum_{n=0}^{\infty} x^{kn}=1+x^k+x^{2k}+\cdots+x^{kn}+\cdots \] 那么因为生成函数只是一个「形式幂级数」（定义在后面讲）
我们可以理解为，这里的形式参数 \(x\) 取什么值我们不关心，只要它不影响我们计算答案就可以
进一步地讲，即使这个形式幂级数所对应的幂级数是不收敛的，我们依然可以进行运算
好那么我们直接将 \(F(x)\) 化简即可得到 \[ F(x) = \frac{1}{(1-x)(1-x^2)(1-x^3)} \] 这个东西疑似有点过于复杂了（确信），但是我们可以通过广义二项式定理求出它的任意一项的系数。
不过这不是本题的目的，这里主要想告诉大家生成函数的“形式”究竟体现在哪里。
普通生成函数 OGF
普通生成函数（Ordinary Generating Function,OGF）
到这里我们就可以给出普通生成函数的定义了。
对于一个数列 \(\{f_n\}\) ，定义它的普通生成函数 \(F(x)\) 为以 \(x\) 为未定元的一个形式幂级数，则 \[ F(x) = \sum_{n \ge 0} f_nx^n \\f_n = [x^n]F(x) \] 另一种易于理解的写法是这样的（数列为 \(\{a_n\}\) ） \[ F(x) = \sum_{i=0}^{\infty}a_ix^i = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n + \cdots \]
基本运算
OGF 的运算很多都和多项式类似。 \[ \begin{aligned} &F(x) \pm G(x)&&=\left(\sum_{n \geq 0} f_n x^n\right) \pm\left(\sum_{n \geq 0} g_n x^n\right)&&=\sum_{n \geq 0}\left(f_n \pm g_n\right) x^n \\[8pt]&F(x)\times G(x) &&= \left(\sum_{n \geq 0} f_n x^n\right) \times \left(\sum_{n \geq 0} g_n x^n\right)&&=\sum_{n \geq 0}x^n\sum_{k=0}^{n}f_kg_{n-k} \\[8pt]&c \times F(x) &&= c \times\left(\sum_{n \geq 0} f_n x^n\right)&&=\sum_{n \geq 0}\left(c f_n\right) x^n \\[8pt]&x^{m}F(x) &&= \sum_{n \geq 0} f_{n+m} x^n &&=\frac{\sum_{n \geq 0} f_n x^n-\sum_{i=0}^{m-1} f_i x^i}{x^m} \\[8pt]&x^{-m}F(x) &&= \sum_{n \ge m}f_{n-m}x^n &&= \sum_{n \ge 0}f_nx^{n+m} \\[8pt]&F^{\prime}(x) &&= \left(\sum_{n \geq 0} f_n x^n\right)^{\prime} &&=\sum_{n \geq 0}\left((n+1) f_{n+1}\right) x^n \\[8pt]&\int F(x)dx &&= \int\left(\sum_{n \geq 0} f_n x^n\right) dx &&=\sum_{n>0} \frac{f_{n-1}}{n} x^n+C \\[8pt]&F(kx) &&= \sum_{n \ge 0}f_n (kx)^n &&= \sum_{n\ge 0}k^nf_nx^n \\[8pt]&-\ln (1-F(x)) &&=1+\frac{F(x)}{1}+\frac{F^2(x)}{2}+\ldots \frac{F^n(x)}{n}+\cdots&&=\sum_{n=0}^{\infty} \frac{F^n(x)}{n} \\[8pt]&\exp (F(x)) &&=1+\frac{F(x)}{1 !}+\frac{A^2(x)}{2 !}+\ldots \frac{A^n(x)}{n !}+\cdots &&=\sum_{n=0}^{\infty} \frac{A^n(x)}{n !} \end{aligned} \]
常见的OGF
下面这些常见的OGF通常可以用封闭形式代替级数形式。 \[ \begin{aligned} &\sum_{n \ge 0}[n=0] x^n &&= 1 \\[3pt]&\sum_{n\ge 0}[n=m] x^n &&= x^m \\[3pt]&\sum_{n \geq 0} x^n &&=\frac{1}{1-x} \\[3pt]&\sum_{n \geq 0}(n+1) x^n &&=\frac{1}{(1-x)^2} \\[3pt]&\sum_{n \geq 0}(-1)^n x^n &&=\frac{1}{1+x} \\[3pt]&\sum_{n \geq 0}\dbinom{m}{n}x^n &&=(1+x)^m \\[3pt]&\sum_{n \geq 0}\dbinom{n+m-1}{n}x^n &&=(1-x)^{-m} \\[3pt]&\sum_{n>0} \frac{1}{n} x^n &&=\ln \frac{1}{1-x} \\[3pt]&\sum_{n>0} \frac{-(-1)^n}{n} x^n &&=\ln (1+x) \\[3pt]&\sum_{n \geq 0} \frac{1}{n !} x^n &&=e^x \end{aligned} \]
例题
洛谷P2000 拯救世界 一道比较基础的生成函数的题
指数生成函数 EGF
指数生成函数（exponential generating function，EGF）
有时我们发现 \(\{a_n\}\) 的性质并不好，而 \(\{\frac{a_n}{n!}\}\) 的生成函数性质很好。
那么我们不妨定义一种新的生成函数来解决这个问题。
定义 \(A(x)\) 为数列 \(\{a_0,a_1,\cdots,a_n\}\) 的指数函数，则 \[ A(x) = a_0 + a_1x + \frac{a_2}{2!}x^2 + \cdots + \frac{a_n}{n!}x^n = \sum_{i=0}^{\infty}\frac{a_i}{i!}x^i \]
在一些资料上用 \(A(x)\) 表示普通生成函数，并用 \(\hat A(x)\) 表示指数生成函数。
EGF 的运算和 OGF 是相似的，我们只要把 \(\frac{1}{i!}\) 看成系数的一部分，再按照 OGF 的运算法则做即可。
但是毕竟引入了阶乘，在一些运算上会显得更为独特和巧妙。
乘法（二项卷积）
设 \(F(x),G(x)\) 为数列 \(\{f_i\},\{g_i\}\) 的指数生成函数，则 \[ h_n = [x^n](F(x)G(x)) = n ! \sum_{k \geq 0}\binom{n}{k}f_k g_{n-k} \] 数列 \(\{h_n\}\) 称为 \(\{f_n\}\) 和 \(\{g_n\}\) 的二项卷积(Binomial Convolution)。
也就是说，\(\{f_n\}\) 和 \(\{g_n\}\) 的二项卷积等价于 \(\{\frac{f_n}{n!}\}\) 和 \(\{\frac{g_n}{n!}\}\) 的普通卷积
导数与积分
\[ A^{\prime}(x) = \sum_{n \geq 0} n \frac{a_n}{n !} x^{n-1}=\sum_{n \geq 0} \frac{a_n}{(n-1) !} x^{n-1} \]
\(A^{\prime}(x)\) 对应的数列为 \(\{a_1,a_2,\cdots,a_n\}\) 。
也就是说，指数生成函数上的求导相当于普通生成函数的左移。同理，积分相当于右移。
例题
洛谷P2012 拯救世界2 一道比较基础的指数生成函数题
狄利克雷生成函数 DGF
狄利克雷生成函数（Dirichlet series generating function，DGF）
对于无穷序列 \(f_1,f_2,\cdots\) 定义其狄利克雷生成函数为 \[ \tilde{F}(x)=\sum_{i \geq 1} \frac{f_i}{i^x} \] 如果序列 \(f\) 满足积性，即 \(\forall i,j,\gcd(i,j),f_{i\cdot j}=f_if_j\) ，那么其 DGF 可以由质数幂处的取值表示 \[ \tilde{F}(x)=\prod_{p \in \mathcal{P}}\left(1+\frac{f_p}{p^x}+\frac{f_{p^2}}{p^{2 x}}+\frac{f_{p^3}}{p^{3 x}}+\cdots\right) \] 对于两个序列 \(f,g\) ，其 DGF 之积对应的是两者的狄利克雷卷积序列的 DGF： \[ \tilde F(x) \cdot \tilde G(x) = \sum_{i \ge 1}\sum_{j\ge 1} \frac{f_ig_j}{(ij)^x} = \sum_{i \ge 1}\frac{1}{i^x}\sum_{d \mid i}f_dg_{\frac{i}{d}} \]
常见积性函数的 DGF
DGF 最适合用于研究与积性函数的狄利克雷卷积相关的问题。因此首先我们要了解常见积性函数的 DGF。
1. 黎曼函数
序列 \([1,1,1,\cdots]\) 的 DGF 是 \(\sum_{i\ge 1}\frac{1}{i^x} = \zeta(x)\) ，其中 \(\zeta\) 即为黎曼函数。
由于其满足积性，因此我们可以得到 \([1,1,1,\cdots]\) 的 DGF 的另一种形式 \[ \zeta(x)=\prod_{p \in \mathcal{P}}\left(1+\frac{1}{p^x}+\frac{1}{p^{2 x}}+\ldots\right)=\prod_{p \in \mathcal{P}} \frac{1}{1-p^{-x}} \]
2. 莫比乌斯函数
对于莫比乌斯函数 \(\mu\) ，它的 DGF 定义为 \[ \tilde{M}(x)=\prod_{p \in \mathcal{P}}\left(1-\frac{1}{p^x}\right)=\prod_{p \in \mathcal{P}}\left(1-p^{-x}\right) \] 容易发现 \(\zeta(x) \tilde{M}(x)=1\) ，也就是说 \(\tilde{M}(x)=\sum_{n \ge 1}\frac{\mu(n)}{i^x}=\frac{1}{\zeta(x)}\) ，这个公式很重要。
3. 欧拉函数
对于欧拉函数 \(\varphi\) ，它的 DGF 定义为 \[ \tilde{\Phi}(x)=\prod_{p \in \mathcal{P}}\left(1+\frac{p-1}{p^x}+\frac{p(p-1)}{p^{2 x}}+\frac{p^2(p-1)}{p^{3 x}}+\ldots\right)=\prod_{p \in \mathcal{P}} \frac{1-p^{-x}}{1-p^{1-x}} \] 因此有 \(\tilde{\Phi}(x)=\frac{\zeta(x-1)}{\zeta(x)}\)
4. 幂函数
对于函数 \(I_k(n)=n^k\) ，它的 DGF 定义为 \[ \tilde{I}_k(x)=\prod_{p \in \mathcal{P}}\left(1+\frac{p^k}{p^x}+\frac{p^{2 k}}{p^{2 x}}+\ldots\right)=\prod_{p \in \mathcal{P}} \frac{1}{1-p^{k-x}}=\zeta(x-k) \] 根据这些定义，容易推导出 \(\varphi * 1 = I\) （\(*\) 表示狄利克雷卷积），因为 \(\tilde{\Phi}(x) \zeta(x)=\zeta(x-1)\) 。
5. 其他函数
对于约数幂函数 \(\sigma_k(n)=\sum_{d \mid n} d^k\) ，它的 DGF 可以表示为狄利克雷卷积的形式
狄利克雷卷积（Dirichlet 卷积）
定义
对于两个数论函数 \(f(x)\) 和 \(g(x)\) ，它们的狄利克雷卷积定义为 \[ h(x)=\sum_{d \mid x} f(d) g\left(\frac{x}{d}\right)=\sum_{a b=x} f(a) g(b) \] 上式可以简记为 \[ h = f*g \] 狄利克雷卷积是数论函数的重要运算，数论函数的许多性质都是通过这个运算挖掘出来的。
上面我们提到了，狄利克雷卷积与狄利克雷生成函数 DGF 事实上密切相关 \[ \tilde F(x) \cdot \tilde G(x) = \sum_{i \ge 1}\sum_{j\ge 1} \frac{f_ig_j}{(ij)^x} = \sum_{i \ge 1}\frac{1}{i^x}\sum_{d \mid i}f_dg_{\frac{i}{d}} \] 即对于两个序列 \(f,g\) ，其狄利克雷生成函数之积，对应的是两者的狄利克雷卷积序列的狄利克雷生成函数
性质
交换律：\(f * g=g * f\)
结合律：\((f*g)*h=f*(g*h)\)
分配律： \((f+g)*h = f * h + g * h\)
等式的性质：\(f=g\) 的重要条件是 \(f*h = g*h\) ，其中数论函数 \(h(x)\) 要满足 \(h(1) \ne 0\) 。
单位元：单位函数 \(\epsilon\) 是狄利克雷卷积运算中的单位元，即对于任何数论函数 \(f\) 都有 \(f * \epsilon = f\) 。
具体地，单位函数 \(\epsilon(n) := [n=1]\) ，即 \(n=1\) 时为 \(1\) ，否则为 \(0\) 。
狄利克雷卷积运算中的单位元不是常函数，但是在狄利克雷生成函数中等价于常数 \(1\) 。
狄利克雷卷积运算中的数论函数常函数 \(1\)，在狄利克雷生成函数中等价于黎曼函数 \(\zeta\) 。
逆元：对于任何一个满足 \(f(x) \ne 0\) 的数论函数，如果有另一个数论函数 \(g(x)\) 满足 \(f*g = \epsilon\) ，
则称 \(g(x)\) 为 \(f(x)\) 的逆元。由等式的性质可知，逆元是唯一的。
狄利克雷卷积运算中的逆元，在狄利克雷生成函数中相当于倒数运算。
容易构造出 \(g(x)\) 的表达式 \[ g(x)=\frac{\epsilon(x)-\sum_{d \mid x, d \neq 1} f(d) g\left(\frac{x}{d}\right)}{f(1)} \]
重要结论
结论1：两个积性函数的狄利克雷卷积也是积性函数。
证明：设两个积性函数为 $f(x) $和 \(g(x)\) ，再记 \(h = f*g\) 。
设 \(\gcd(a,b) = 1\) ，则 \[ h(a)=\sum_{d_1 \mid a} f\left(d_1\right) g\left(\frac{a}{d_1}\right), h(b)=\sum_{d_2 \mid b} f\left(d_2\right) g\left(\frac{b}{d_2}\right) \] 所以 \[ \begin{aligned} h(a) h(b) & =\sum_{d_1 \mid a} f\left(d_1\right) g\left(\frac{a}{d_1}\right) \sum_{d_2 \mid b} f\left(d_2\right) g\left(\frac{b}{d_2}\right) \\ & =\sum_{d \mid a b} f(d) g\left(\frac{a b}{d}\right) \\ & =h(a b) \end{aligned} \] 证毕。
结论2：积性函数的逆元也是积性函数
证明：设 \(f*g = \epsilon\) ，并且不妨设 \(f(1)=1\) 。考虑归纳法证明：
若 \(nm=1\) ，则 \(g(nm)=g(1) = 1\) ，显然成立
若 \(nm > 1(\gcd(n,m) = 1)\) ，设现在对于所有的 \(xy < nm(\gcd(x,y) = 1)\) 结论成立，则 \[ g(n m)=-\sum_{d \mid n m, d \neq 1} f(d) g\left(\frac{n m}{d}\right)=-\sum_{a|n, b| m, a b \neq 1} f(a b) g\left(\frac{n m}{a b}\right) \] 又因为 \(\frac{n m}{a b}<n m\) ，所以有 \[ \begin{aligned} g(n m) & =-\sum_{a|n, b| m, a b \neq 1} f(a b) g\left(\frac{n m}{a b}\right) \\[8pt]& =-\sum_{a|n, b| m, a b \neq 1} f(a) f(b) g\left(\frac{n}{a}\right) g\left(\frac{m}{b}\right) \\[8pt]& =f(1) f(1) g(n) g(m)-\sum_{a|n, b| m} f(a) f(b) g\left(\frac{n}{a}\right) g\left(\frac{m}{b}\right) \\[8pt]& =g(n) g(m)-\sum_{a \mid n} f(a) g\left(\frac{n}{a}\right) \sum_{b \mid m} f(b) g\left(\frac{m}{b}\right) \\[8pt]& =g(n) g(m)-\epsilon(n)-\epsilon(m) \\[8pt]& =g(n) g(m) \end{aligned} \]
综上可知，结论成立。\(\square\)
同时这也说明，数论函数的积性，在狄利克雷生成函数中的对应具有封闭性。
例子
\[ \begin{aligned} & \epsilon=\mu * \mathbf{1} \Longleftrightarrow \epsilon(n)=\sum_{d \mid n} \mu(d) \\[6pt]& d=\mathbf{1} * \mathbf{1} \Longleftrightarrow d(n)=\sum_{d \mid n} 1 \\[6pt]& \sigma=\mathrm{id} * \mathbf{1} \Longleftrightarrow \sigma(n)=\sum_{d \mid n} d \\[6pt]& \varphi=\mu * \mathrm{id} \Longleftrightarrow \varphi(n)=\sum_{d \mid n} d \cdot \mu\left(\frac{n}{d}\right) \\[6pt]& \mathrm{id}=\varphi * \mathbf{1}\Longleftrightarrow n=\sum_{d \mid n} \varphi(d) \end{aligned} \]
最后一个就是 欧拉反演
参考文献&鸣谢：
[0] 感谢 Roundgod 对我无数的帮助 Orz （upd.
尤其是提醒我不要超前点科技）
[1] https://www.cnblogs.com/birchtree/p/11575252.html
[2] https://zhuanlan.zhihu.com/p/52817010
[3] https://blog.csdn.net/qq_41357771/article/details/83449481
