生成函数入门

读完这篇博客，您的生成函数水平将会到达入门前（即还没有入门但是有概念）的水平。本文只会提到 OGF 和 EGF。因为 DGF（迪利克雷生成函数）很多内容于数论重叠，后续补充数论内容大概率会写，不想重复写（其实就是现在不会），当然还有一些比如概率生成函数之类这里更加没有提及。

• 普通生成函数（OGF）。
• 指数生成函数（EGF）。

本文约定：对于任意实数 $x$，$x^0=1$，包括 $x=0$。

简介

生成函数（generating function）又称为“母函数”，是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。

本博客的行文思路和引导例题大多也借鉴（copy）了 OI-wiki。

一般来说，生成函数可以表示为这样的形式：

$F(x) = \sum_i a_ik_i(x)$

其中 $k_i(x)$ 为核函数。不同的核函数可以得到不同的生成函数，$a_i$ 为系数序列。使用 $[k_n(x)]F(x)$（可能会直接写成 $[x^n]F(x)$，不管核函数是不是 $k_i(x)=x^i$）表示第 $n$ 项系数，即 $a_n$。

系数序列既可以是有限序列，也可以是无穷序列。

普通生成函数

核函数 $k_i(x) = x^i$​ 时，得到的生成函数叫普通生成函数，简称 OGF。一个普通生成函数的形式幂级数可以写成下面这个样子：

$F(x) = \sum_i a_ix^i$

下面我们考虑一个封闭的 OGF 如果转化为封闭形式。以 $a=\left\langle1,3,9,27,81,\cdots\right\rangle$ 为例子（等比数列），其 OGF 为：

$F(x) = \sum_{i\geq 0} 3^ix^i$

发现这个函数有这样的性质：

$3xF(x)+1=F(x)$

因此：

$F(x) = \frac{1}{1-3x}$

这就是原生成函数的封闭形式。类似的，我们能得到等比数列生成函数的封闭形式 $F(x) = \frac{1}{1-px}$，其中 $p$ 为公比。再类比一下，求 $\sum_{i\geq n} p^ix^i$ 的封闭形式？

$pxF(x)+p^nx^n = F(x)$

因此有：

$F(x) = \sum_{i\geq n} p^ix^i = \frac{p^nx^n}{1-px}$

这个式子非常有用，请务必牢记。

写出序列 $a=\left\langle0,1,0,1,\cdots\right\rangle$ 的生成函数的幂级数形式和封闭形式。

不难发现实际上就是只有 $x$ 的奇数次幂，所以很容易写出其形式幂级数写法：

$F(x) = \sum_{i\geq 0} x^{2i+1}$

因此 $x^2F(x) +x=F(x)$，因此：

$F(x) = \frac{x}{1-x^2}$

写出序列 $a_n=\binom{m}{n}$ 的生成函数的幂级数形式和封闭形式。

用二项式定理即可：

$F(x) = \sum_{i\geq 0} \binom{m}{i} x^i = (x+1)^m$

---

当然只知道封闭形式用处不大，我们还需要转化。注意这里的转化可能仍然是一个封闭形式。一个生成函数的封闭形式可能有多个，而另一个就能由某一个转化得到，例如……

写出序列 $a=\left\langle0,1,1,2,3,5,8,13,\cdots\right\rangle$ 即斐波那契的生成函数。

根据递推式 $a_n = a_{n-1} + a_{n-2}$：

$F(x) = xF(x) + x^2F(x) +x$

如何理解这个式子？

实际上，函数乘上一个 $x$ 相当于各项系数向右移动一位，乘上 $x^2$ 同理。直接求和发现少了一个系数 $1$，也就是边界系数，需要加上 $x$。

根据这个式子获得封闭形式 $F(x)= \frac{x}{1-x-x^2}$。下面考虑如何把这个玩意转化。回想到等差数列的封闭形式，用待定系数法构造等差数列：

$\frac{A}{1-ax}+\frac{B}{1-bx} = \frac{x}{1-x-x^2}$

不难得到：

$\begin{cases} A+B = 0 \\ Ab+aB = -1 \\ a+b = 1 \\ ab=-1 \end{cases}$

解这个方程是简单的，解得 $A=\frac{\sqrt 5}{5},B=-\frac{\sqrt 5}{5},a=\frac{1+\sqrt 5}{2},b=\frac{1-\sqrt 5}{2}$。然后再利用等比数列的展开式，就可以得到斐波那契数列的另一个封闭形式。具体展开比较复杂无趣这里不展开（其实就是懒得推直接摆结论算了）。

$F(x) = \sum_{n\geq 0} x^n \frac{\sqrt 5}{5} \left[ \left(\frac{1+\sqrt 5}{2}\right)^n - \left(\frac{1-\sqrt 5}{2}\right)^n \right]$

不难发现这就是我们常看到的斐波那契数列通项公式。

写出任意数列 $f$（生成函数为 $F$）的前缀和的数列的生成函数 $S$。

$\begin{aligned} S(x) &= \sum_{n\geq 0} x^n \sum_{i=0}^n f_i \\ &= \sum_{i\geq 0} a_i\sum_{n\geq i} x^n \\ &= \sum_{i\geq 0} a_i \frac{x^i}{1-x} \\ &= \frac{1}{1-x} F(x) \end{aligned}$

因此一个数列前缀和的生成函数就是原数列生成函数乘 $\frac{1}{1-x}$。

写出卡特兰数的生成函数。卡特兰数的定义为 $c_n = \sum_{i=0}^{n-1} c_ic_{n-i-1}$，边界 $c_0=1$。

不难发现 $n>0$ 的情况其实就是这个生成函数和自己的卷积：

$C(x) = 1+xC^2(x)$

解出：

$C(x) = \frac{1\pm\sqrt{1-4x}}{2x}$

问题在于，这个符号到底取正还是取负？不妨考虑把分子有理化：

$C(x) = \frac{2}{1\mp\sqrt{1-4x}}$

（注意分母的正负和分子的正负是反的）若分母符号取负，当 $x=0$ 代入时，结果为 $\frac{2}{0}$ 无意义；分母取正，当 $x=0$ 代入时为 $\frac{2}{2}=1$ 符合题意。因此分母应该取正，也就是分子取负。

$C(x) = \frac{1-\sqrt{1-4x}}{2x}$

然后考虑将其转化。从这个根号开始，用广义二项式定理暴力拆：

$\begin{aligned} \sqrt{1-4x} &= \sum_{i\geq 0} \binom{\frac{1}{2}}{i} (-4x)^i \\ &= 1 - \sum_{i\geq 1} \frac{1\times3\times5\times\cdots\times(2i-3)}{i!}(2x)^i \\ &= 1 - \sum_{i\geq 1} \frac{(2i-2)!}{i!\times 2\times 4\times 6\times\cdots\times(2i-2)} 2^ix^i \\ &= 1- \sum_{i\geq 1} \frac{(2i-2)!}{i!(i-1)!} 2x^i \end{aligned}$

这玩意往回代入：

$\begin{aligned} C(x) &= \frac{1}{2x}[1-(1-\sum_{i\geq 1} \frac{(2i-2)!}{i!(i-1)!}2x^i)] \\ &= \sum_{i\geq 1} \frac{(2i-2)!}{i!(i-1!)} x^{i-1} \\ &= \sum_{i\geq 0} \frac{(2i)!}{i!(i+1)!} x^i \\ &= \sum_{i\geq 0} \binom{2i}{i}\frac{1}{i+1}x^i \end{aligned}$

这也是我们熟悉的卡特兰数通项公式 $c_n = \frac{\binom{2n}{n}}{n+1}$。

指数生成函数

当核函数为 $k_n(x) = \frac{x^n}{n!}$ 时，这玩意就变成了指数生成函数，简称 EGF。其形式幂级数为：

$F(x) = \sum_{n} a_n \frac{x^n}{n!}$

什么问题一般不用 OGF 而用 EGF？考虑计算一些东西的时候，如果物品是有顺序的（即带编号的），可能会整出来这样一个卷积：

$h_n = \sum_{i=0}^n \binom{n}{i} f_ig_{n-i}$

这时候考虑展开组合数：

$\frac{h_n}{n!} = \sum_{i=0}^n \frac{f_i}{i!} \times \frac{g_{n-i}}{(n-i)!}$

然后就出现了标准的指数生成函数。当然你也可以认为 $a$ 的指数生成函数就是 $\frac{a_i}{i!}$ 的普通生成函数。

下面依然考虑如何封闭一个 EGF。这个比 OGF 难得多。先从 $a=\left\langle1,1,1,\cdots\right\rangle$ 开始：

$F(x) = \sum_{i\geq 0} \frac{x^i}{i!}$

相当于在原点处把 $e^x$ 泰勒展开。因此：

$F(x) = e^x$

如果你不会泰勒展开，可以直接记这个东西，背一些常见的：

$\sum_{i\geq 0} p^i \frac{x^i}{i!} = e^{px}$

$\sum_{i\geq 0} i^{\underline k} \frac{x^i}{i!} = x^ke^x$

$\sum_{i\geq 0} (i-1)!\frac{x^n}{i!} = \ln\frac{1}{1-x}$

写出 $a_n = \mathrm{P}_n^k$ 的 EGF。$\rm{P}$ 为排列数。

$\begin{aligned} F(x) &= \sum_{i=0}^n \mathrm{P}_n^i \frac{x^i}{i!} \\ &= \sum_{i=0}^n \frac{x^in!}{i!(n-i)!} \\ &= (1+x)^n \end{aligned}$

写出圆排列的 EGF。

$n$ 个数的圆排列为 $(n-1)!$，因此：

$Q(x) = \sum_{i>0} (i-1)! \frac{x^i}{i!} = \ln\frac{1}{1-x}$

这里会出现一个有意思的事情，如果你求出了普通排列数的 EGF，就会发现普通排列的 EGF 为 $P(x) = \frac{1}{1-x} = \exp Q$。不妨证明一下：

考虑构造长度为 $n$ 的排列相当于把 $n$ 拆成很多置换环，每个置换环组合的方案数，也就是先将 $1,2,\cdots,n$ 划分为若干集合，每个集合形成一个置换环的方案。而一个集合的数形成置换环的方案数就是这个集合大小的圆排列数，因此长度为 $n$ 的排列的方案数为把 $1\sim n$ 划分为若干集合，每个集合圆排列方案数的积。这是多项式 exp 的一种理解。

因此还能得出：

记 $n$ 个有标号点的无向连通图数量的 EGF 为 $F$，则 $n$ 个有标号点的无向图的数量的 EGF 为 $\exp F$。

注意它也刻画出“树”和“森林” EGF 的关系，这比无向图的关系更容易考到。

写出错排数的 EGF。

从置换环的角度做这个题就简单多了，因为“错排”在置换环上的表现就是不存在自环。不存在大小为 $1$ 的置换环对应的生成函数为：

$G(x) = \sum_{i>1} (i-1)!\frac{x^i}{i!}$

注意这里是 $i>1$，所以：

$G(x) = -x + \ln\frac{1}{1-x}$

所以错排数的指数生成函数为：

$F(x) = \exp G = \exp(-x+\ln\frac{1}{1-x})$

例题

BZOJ3028 食物

你要带 $n$ 个物品（$n\leq 10^{500}$），物品有八种，每种无限个，但是有携带限制：

1. 必须选偶数个。
2. 最多选 $1$ 个。
3. 最多选 $2$ 个。
4. 必须选奇数个。
5. 必须选 $4$ 的倍数个。
6. 最多选 $3$ 个。
7. 最多选 $1$ 个。
8. 必须选 $3$ 的倍数个。

求携带方案数。对 $10007$ 取模。

题解

对于每个种类，写出 OGF 的封闭形式：

1. $\frac{1}{1-x^2}$。
2. $1+x$。
3. $1+x+x^2$。
4. $\frac{x}{1-x^2}$。
5. $\frac{1}{1-x^4}$。
6. $1+x+x^2+x^3$。
7. $1+x$。
8. $\frac{1}{1-x^3}$。

单独每一个函数，$[x^n]F(x)$ 表示这种食物选 $n$ 个的方案数，而两种食物一共 $n$ 个的方案数，就是这两个函数的卷积的第 $n$ 项系数。因此全部乘起来，化简得到：

$F(x) =\frac{x}{(1-x)^4}$

二项式定理：

$F(x) = \sum_{i=0}\binom{i+3}{i} x^{i+1}$

因此第 $n$ 项系数为 $\binom{n+2}{n}$。

Luogu3978 概率论

对于一个随机生成的 $n$ 个点的二叉树，求叶子数的期望。

$n\leq 10^9$，误差不超过 $10^{-9}$。

题解

先 DP 设 $f_i$ 表示有 $i$ 和点的二叉树个数，$g_i$ 表示有 $i$ 个点的所有二叉树的叶子数的和。考虑 $f,g$ 的关系：

• 对于 $n$ 个点的二叉树，设有 $k$ 个叶子，任意删除一个都会得到 $n-1$ 个点的二叉树。且删去两个不同的叶子，得到的二叉树不同构。
• 对于 $n-1$ 个点的二叉树，恰好有 $n$ 个位置可以添加一个新的叶子。因此每个 $n-1$ 个点的二叉树都有 $n$ 种方法得到一个 $n$ 个点的二叉树，添加位置不同时，树不同构。

因此有 $g_n = nf_{n-1}$。$f$ 的递推式则考虑枚举左子树叶子节点数得到：

$f_n = \sum_{i=1}^{n-1} f_i f_{n-i-1}$

这是一个卷积的形式，令 $F$ 为 $f$ 的生成函数，用和卡特兰数一样的方法得到 $F(x) = \sum_{i\geq 0} \binom{2i}{i}\frac{1}{i+1}x^i$。

因此 $f_n = \frac{\binom{2n}{n}}{n+1}$，则答案为：

$\frac{g_n}{f_n} = \frac{n(n+1)}{2(2n-1)}$

Luogu4841 城市规划

求 $n$ 个简单有标号无向连通图的数量。

$n\leq 1.3\times 10^5$，答案对 $479+2^{31}+1$ 取模（原根为 $3$）。

题解

首先这个模数不影响我们 NTT。

下面考虑求出有标号无向图的数量的 EGF $F$，就可以得到答案生成函数 $G = \ln F$。

相当于一个完全图，每个边可以选或者不选，因此 $[\frac{x^n}{n!}] F(x) = 2^{\frac{n(n-1)}{2}}$。

套上一个多项式 $\ln$ 即可。

Luogu2012 拯救世界 2

你要按顺序拿走 $n$ 个物品（$n<2^{63}$），物品有十二种，每种无限个，有拿取限制：

• $1,2,3,4$ 这四种可以任意拿。
• $5,6,7,8$ 这四种必须分别拿奇数个。
• $9,10,11,12$ 这四种必须分别拿偶数个。

答案对 $10^9$ 取模。

题解

十二种物品可以归为三类。因为选取有顺序，所以用 EGF。这三个的 EGF 分别为：

$F(x) = \sum_{i\geq 0} \frac{x_i}{i!} = e^x$

$G(x) = \sum_{i\geq 0} \frac{x^{2i+1}}{(2i+1)!} = \frac{e^x-e^{-x}}{2}$

$H(x) = \sum_{i\geq 0} \frac{x^{2i}}{(2i)!} = \frac{e^x + e^{-x}}{2}$

和前面一样，全部乘起来，注意这三类的每一类都还分了 $4$ 种，因此有：

$\begin{aligned}P(x) &= (F(x)G(x)H(x))^4 \\&= (\frac{e^{3x}-e^{-x}}{4})^4 \\&= \frac{e^{12x}-4e^{8x}+6e^{4x}+e^{-4x}-4}{256}\end{aligned}$

$256$ 在模 $10^9$ 意义下没有逆元。在 $n$ 比较小的时候特判答案，$n$ 较大时：

$ans = n![x^n] P(x)$

代入有：

$81\times 12^{n-4} - 8^{n-2} + 6\times 4^{n-4} + (-4)^{n-4}$

快速幂即可。