生成函数 学习笔记

这里涉及的记号比较多，建议查阅 博客符号&记号参照表

这篇文章最早写于 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$

结合律：$(fg)h=f(gh)$

分配律： $(f+g)h = f h + g * h$

等式的性质：$f=g$ 的重要条件是 $fh = gh$ ，其中数论函数 $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

[4] https://oiwiki.org/math/poly/dgf