铃悬的数学小讲堂——生成函数初步

PS: 看不懂的可以先跳过去...我也没有办法，毕竟简单题不好找。 PS2：这基本上是给没有学过的人看的...所以如果有 dalao 看了一遍说没学到什么不要喷我qwq... ## -1. 符号及约定 1. $[P]$ （艾弗森括号）是指，若 $P$ 为真，则 $[P]=1$，否则 $[P]=0$。即 $[P]=\begin{cases}1&P\\0&\lnot P\end{cases}$。特别的，若 $P$ 为假，$[P]\times e$ 即使在 $e$ 未定义时也为 $0$（例如，$[n\neq0]\frac1n$ 在 $n=0$ 是为 $0$，而不是未定义值）。 2. 大写字母代表一个函数，例如 $F(x)$ 代表 $\{f_n\}$ 的生成函数。有时为方便整洁会省略参数列表，即 $F(x)$ 省略为 $F$。 3. 若无特殊约定，数列下标均从 $0$ 开始。 4. 斜体表示吐槽~~，你完全不需要看明白~~。 5. $x^0=1$ 对所有数成立，包括 $0$。 ## 0. 前备知识 1. 二项式系数（组合数） $\binom nm=\frac{n!}{m!(n-m)!}$ 表示 $n$ 个物品中选出 $m$ 个的方案数。当 $n\in\mathbb R,m\in\mathbb N$ 时定义广义二项式系数 $\binom nm=\frac{n(n-1)\cdots(n-m+1)}{m!}$。易知在 $n\in\mathbb N$ 时广义二项式系数与之前的定理相符。 2. 广义二项式定理：$(1+x)^a=\sum_{i=0}^{\infty}\binom{a}{i}x^i$，其中 $a$ 为任意实数*（当 $a\notin\mathbb N$ 时收敛半径是$1$，不过你可以不在意这个）*。注意 $a\in\mathbb N$ 时 $i>a$ 的项都为 $0$，这时即为一般的二项式定理。 3. 一些简单的关于二项式系数的恒等式，比如 $\binom{n}{k}=\binom{n}{n-k},\binom{n}{k}=(-1)^k\binom{k-n-1}{k}$ 之类的（第一个恒等式要求 $n$ 也是非负整数并且 $\geq k$，第二个恒等式可以手动展开得到（实际上就是把定义里分子的每个因式都乘上了$-1$））。 4. 一些比较简单的微积分，比如求比较简单的函数的导数，以及比较简单的函数的积分。~~（“比较简单”大概就是“连这都不会的话就不要说自己学过微积分了”）~~ ## 1. 引入——斐波那契 众所周知的斐波那契数列 $\{f_n\}$ 有许多有趣的性质，但是我们现在先忘掉它们，假设你是第一次遇到它。 斐波那契数的定义是 $$f_n=\begin{cases}0&n=0\\1&n=1\\f_{n-1}+f_{n-2}&n>1\end{cases}$$ 前几项就是（从 $0$ 开始） $0,1,1,2,3,5,8,13,21,34,55,89,144,\dots$。 当然你可以通过各种方式来求它的通项、或是一些性质，但是既然我们要讲生成函数，那就用生成函数的方式解决吧。 我们定义一个**生成函数** $F$ 为 $F(x)=\sum_{i=0}^{\infty}f_ix^i$。类似于小学（或初中？高中？）所讲的“错位相减法”，我们写下下面的式子： $$\begin{array}{r}F(x)&=&f_0x^0&+&f_1x^1&+&f_2x^2&+&f_3x^3&+&f_4x^4 &+&\dots\\xF(x)&=& & &f_0x^1&+&f_1x^2&+&f_2x^3&+&f_3x^4&+&\dots\\x^2F(x)&=& & & & &f_0x^2&+&f_1x^3&+&f_2x^4&+&\dots\\\end{array}$$ 可以发现，上面那一行几乎就是下面两行的和。之所以说“几乎”，是因为还差了一个 $f_1x$，即 $x$。于是可以得到 $$F(x)=x+xF(x)+x^2F(x)$$ 接下来应该干什么？出于对代数方法~~（和本文作者）~~的信任，我们应该尝试解出 $F(x)$ 来。 $$F(x)=\frac{x}{1-x-x^2}$$ 这看上去很奇怪。我们可以尝试从这里面重新搞出 $f_n$ 来。 根据等比数列求和的式子，我们有 $\frac{1}{1-ax}=\sum_{i=0}^{\infty}a^ix^i$，那可以考虑把 $\frac{x}{1-x-x^2}$ 分解成 $\frac A{1-ax}+\frac B{1-bx}$ 的形式。 那么首先根据 $(1-ax)(1-bx)=1-x-x^2$，可以知道 $a$ 和 $b$ 实际上就是 $1-x-x^2$ 的解的倒数，或者说 $x^2-x-1$ 的解。 可以得到两个解，即 $\phi=\frac{1+\sqrt5}{2},\hat\phi=\frac{1-\sqrt5}{2}$。再对 $A$ 和 $B$ 列个方程就能解出 $A=\frac1{\sqrt5},B=-A=-\frac1{\sqrt5}$。于是 $$\begin{aligned}F(x)=\frac x{1-x-x^2}&=\frac1{\sqrt5}\left(\frac1{1-\phi x}-\frac1{1-\hat\phi x}\right)\\&=\frac1{\sqrt5}\left(\sum_{i=0}^{\infty}\phi^ix^i-\sum_{i=0}^{\infty}\hat\phi^ix^i\right)\\&=\sum_{i=0}^{\infty}\frac{\phi^i-\hat\phi^i}{\sqrt5}x^i\\\end{aligned}$$ 于是 $f_n=\frac1{\sqrt5}(\phi^i-\hat\phi^i)$。当然你可以通过比例因子法、常系数递推特征多项式及特征根~~、百度、谷歌~~等方法得到它的递推式，不过生成函数可不止于此。 *什么，你问收敛性？好吧 $F(x)$ 的收敛半径是 $\phi$，但是大可不必在意。实际上你甚至会见到收敛半径为 $0$ 的生成函数，不过实际上并不需要在意这些。如果你真的好奇我们为什么可以忽略掉收敛性，我只能告诉你我们实际是在域 $\mathbb R$ 或 $\mathbb C$ 的形式幂级数环 $\mathbb R[[x]]$ 或 $\mathbb C[[x]]$ 上做运算。* ## 2. 定义及简单的运算 对于一个数列 $\{f_n\}$，定义它的**生成函数**（或**普通型生成函数**，Ordinary Generating Function，简称 OGF）为 $\sum_{n\geq0}f_nx^n$。$f_n$ 称为 $x^n$ 在 $F(x)$ 中的**系数（Coefficient）**，写作 $$f_n=[x^n]F(x)$$ ### 2.1 四(san)则运算 既然是生成函数，就应该有各种运算，比如加减乘除什么的。容易验证下面的加减，以及乘法法则： $$\begin{aligned}\left(\sum_{n\geq0}f_nx^n\right)\pm\left(\sum_{n\geq0}g_nx^n\right)&=\sum_{n\geq0}(f_n\pm g_n)x^n\\c\times\left(\sum_{n\geq0}f_nx^n\right)&=\sum_{n\geq0}cf_nx^n\\\left(\sum_{n\geq0}f_nx^n\right)\left(\sum_{n\geq0}g_nx^n\right)&=\sum_{n\geq0}\left(\sum_{i=0}^nf_ig_{n-i}\right)x^n\end{aligned}$$ 当我们对 $F(x)$ 和 $G(x)$ 做乘法的时候， $f_nx^n$ 与 $g_mx^m$ 的乘积会加到 $x^{n+m}$ 项上，于是可以得到上述的乘法的式子。 $\{h_n\}=\Bigl\{\sum_{i=0}^nf_ig_{n-i}\Bigr\}$ 称为数列 $\{f_n\}$ 与 $\{g_n\}$ 的**卷积（Convolution）**。 *虽然最开始的“卷积”的定义是连续的（求和改成了积分）* 至于卷积的意义，可以理解为要从 $A,B$ 两类物品中选出 $n$ 个物品，那么可以从 $A$ 中选出 $i$ 个、从 $B$ 中选出 $n-i$ 个，这样的话总方案就是 $A$ 中选 $i$ 个的方案乘上 $B$ 中选 $n-i$ 个方案，对 $i=0\dots n$ 求和。 ### 2.2 移位 另外有的时候我们需要对生成函数进行移位，即类似 $h_n=f_{n-1}$ 这种。容易发现 $$\begin{aligned}x^m\sum_{n\geq0}f_nx^n&=\sum_{n\geq m}f_{n-m}x^n\\\frac1{x^m}\left(\sum_{n\geq0}f_nx^n-f_0-f_1x-\dots-f_{m-1}x^{m-1}\right)&=\sum_{n\geq 0}f_{n+m}x^n\\\end{aligned}$$ 第二个式子里如果不减去前 $m$ 项的话就会除出负指数，就不是生成函数了。 ### 2.3 微积分 我们也可以对生成函数求导或者积分，方法是对求和项逐项求导、逐项积分。 $$\begin{aligned}\frac{\rm d}{{\rm d}x}\left(\sum_{n\geq 0}f_nx^n\right)&=\sum_{n\geq0}(n+1)f_{n+1}x^n\\\int\left(\sum_{n\geq 0}f_nx^n\right){\rm d}x&=\sum_{n>0}\frac{f_{n-1}}{n}x^n+C\end{aligned}$$ 这是因为 $f_nx^n$ 求导得到 $nf_nx^{n-1}$，积分得到 $\frac{f_n}{n+1}x^{n+1}$。 不定积分时不可避免地出现了常数 $C$ *什么？你积分~~像cxk~~不加 C？*。如果你想要去掉 $C$，让零次项系数为 $0$ 的话，应该写作 $$\int_0^xF(t){\rm d}t=\int_0^x\left(\sum_{n\geq 0}f_nt^n\right){\rm d}t=\sum_{n>0}\frac{f_{n-1}}{n}x^n$$ 一般情况下不需要这么较真，只需要不定积分积出来之后看看零次项和你想要的是不是一样就可以了。以下我们简写作 $\int F(x){\rm d}x$（即写出这个式子的时候默认常数项为 $0$）。 ### 2.4 一些例子 这里举一些 OGF 的例子： $$\begin{aligned}\sum_{n\geq0}[n=m]x^n&=x^m\\\sum_{n\geq0}x^n&=\frac1{1-x}\\\sum_{n\geq m}x^n&=\frac{x^m}{1-x}\\\sum_{n\geq0}c^nx^n&=\frac1{1-cx}\\\sum_{n\geq0}\binom{n+k-1}{n}x^n&=\frac1{(1-x)^k}\\\sum_{n\geq0}\frac{c^nx^n}{n!}&=e^{cx}\\\sum_{n>0}\frac{(-1)^{n-1}}{n}x^n&=\ln(1+x)\\\sum_{n>0}\frac{1}{n}x^n&=\ln\frac1{1-x}\\\end{aligned}$$ ## 3. 略复杂的例子 ### 3.1 简单数列的部分和 所谓数列 $\{a_n\}$ 的 “部分和”，也就是前缀和，即 $$s_n=\sum_{i=0}^n a_i$$ 一个例子：怎么求斐波那契数列的前缀和？ $$\begin{aligned}S(x)=&\sum_{n\geq0}s_nx^n\\=&\sum_{n\geq0}\left(\sum_{i=0}^nf_i\right)x^n\\=&\sum_{i\geq0}f_i\sum_{n\geq i}x^n\\=&\sum_{i\geq0}f_i\frac{x^i}{1-x}\\=&\frac1{1-x}\sum_{i\geq0}f_ix^i\\=&\frac1{1-x}F(x)\end{aligned}$$ 因此要求一个数列的部分和的生成函数，只需要把它的生成函数乘上 $(1-x)^{-1}$ 就可以了。 所以斐波那契数列的部分和对应的生成函数就是 $$S(x)=\frac{x}{(1-x)(1-x-x^2)}$$ emm...这种东西当然还是可以分解成 $\frac{A}{1-ax}+\frac{B}{1-bx}+\frac{C}{1-x}$ 的形式，这都是力气活，这里就不多说了... ### 3.2 卡特兰数 卡特兰数定义为 $$c_n=\begin{cases}1&n=0\\\sum_{i=0}^{n-1}c_ic_{n-i-1}&n>0\end{cases}$$ 可以看做有 $n$ 对括号的合法括号序列数（每种长为 $2n$ 的合法括号序列都形如 $(A)B$，其中 $A,B$ 分别是长为 $2i$ 和 $2(n-i)$ 的合法括号序列），或者 $n$ 个点的二叉树的个数（注意，二叉树的左右儿子是有区别的），或者 $n+2$ 边形的三角划分方案数，总之有很多种解释。 怎么求 $\{c_n\}$ 的生成函数 $C(x)$？我们发现 $c_{n+1}$ 就是 $\{c_n\}$ 与自己卷积的第 $n$ 项。换句话说，只需要把 $\{c_n\}$ 和自己卷积，再移一位，就几乎可以得到它自己，而只差 $n=0$ 一项。用式子表达出来： $$\begin{aligned}C(x)&=\sum_{n\geq0}c_nx^n\\C(x)&=1+\sum_{n\geq1}\left(\sum_{i=0}^{n-1}c_ic_{n-i-1}\right)x^n\\C(x)&=1+x\sum_{n'\geq0}\left(\sum_{i=0}^{n'}c_ic_{n'-i}\right)x^{n'}\\C(x)&=1+xC^2(x)\\xC^2(x)-C(x)+1&=0\end{aligned}$$ 第二步中我们令 $n'=n-1$，之后可以发现右边的和式就是 $C(x)$ 与自身的卷积，即 $C^2(x)$。 继续利用代数方法，可以用二次函数求根公式解出 $C(x)$，即 $$C(x)=\frac{1\pm\sqrt{1-4x}}{2x}$$ 取 $+$ 还是 $-$？注意到如果 $F(x)$ 是一个生成函数，那么它的零次项系数应该是 $F(0)$。如果取 $+$ 的话，$C(x)=2/0$ 不可能存在，而取 $-$ 时则为 $0/0$*（实际上可以用洛必达法则得到零次项系数就是 1）*。如果你不理解为什么可以出现 $0/0$，不妨想一想 $F(x)=x/x=1$ 这个东西。 所以我们必须要取 $C(x)=(1-\sqrt{1-4x})/(2x)$。接下来要把这个东西展开。 $\sqrt{1-4x}=(1-4x)^{1/2}$，从而根据广义二项式定理， $$\begin{aligned}\sqrt{1-4x}&=\sum_{n\geq0}\binom{1/2}n(-4x)^n\\&=1+\sum_{n\geq1}\frac{(1/2)(-1/2)(-3/2)\cdots((3-2n)/2)}{n!}(-4x)^n\\&=1+\sum_{n\geq1}(-1)^{n-1}\frac{1\times3\times5\times\dots\times(2n-3)}{2^nn!}(-4x)^n\\&=1-\sum_{n\geq1}\frac{1\times3\times5\times\dots\times(2n-3)}{n!}(2x)^n\\&=1-\sum_{n\geq1}\frac{1\times2\times3\times4\times\dots\times(2n-3)\times(2n-2)}{2\times4\times\dots\times (2n-2)\times n!}(2x)^n\\&=1-\sum_{n\geq1}\frac{(2n-2)!}{(n-1)!\times n!\times2^{n-1}}(2x)^n\\&=1-2\sum_{n\geq1}\frac{(2n-2)!}{(n-1)!\times n!}x^n\\\end{aligned}$$ 于是可以把这东西代到 $C(x)$ 里，就可以得到 $$\begin{aligned}C(x)&=\frac1{2x}\left(2\sum_{n\geq1}\frac{(2n-2)!}{(n-1)!\times n!}x^n\right)\\&=\sum_{n\geq1}\frac{(2n-2)!}{(n-1)!\times n!}x^{n-1}\\&=\sum_{n\geq0}\frac{(2n)!}{n!\times(n+1)!}x^n\\&=\sum_{n\geq0}\frac{\binom{2n}n}{n+1}x^n\\\end{aligned}$$ 于是 $c_n=\binom{2n}{n}/(n+1)$，与我们所熟知的相同。 ### 3.3 整数拆分 对于一个非负整数 $n$，它的一个**拆分**定义为若干个正整数 $a_1,a_2,\dots,a_k$，使得 1. $a_1+a_2+\dots+a_k=n$； 2. $a_1\geq a_2\geq\dots\geq a_k>0$。 第二个条件是避免像 $3=1+2=2+1$ 这样重复计算。 令 $p_n$ 表示 $n$ 的不同的拆分方案数，例如，$4=4=3+1=2+2=2+1+1=1+1+1+1$，于是 $p_4=5$。特别的，$p_0=1$。 对于 $p_n$ 的生成函数 $P(x)$，我们给出一个式子： $$P(x)=\frac1{1-x}\times\frac1{1-x^2}\times\dots=\prod_{i=1}^{\infty}\frac1{1-x^i}$$ 对此，可以取 $i=1\dots k$，把它展开： $$\begin{aligned}P_k(x)&=\prod_{i=1}^{k}\frac{1}{1-x^i}\\&=\prod_{i=1}^{k}\left(1+x^i+x^{2i}+x^{3i}+\dots\right)\\&=\sum_{a_1=0}^{\infty}\sum_{a_2=0}^{\infty}\sum_{a_3=0}^{\infty}\cdots\sum_{a_k=0}^{\infty}x^{a_1+2a_2+3a_3+\dots}\end{aligned}$$ 第二行到第三行就是不停应用乘法分配律把所有乘积都展开成单项式。可以发现这就是在枚举整数拆分中 $1$ 的个数、$2$ 的个数等等，不难看出 $[x^n]P_k(x)$ 就是用不超过 $k$ 的正整数来拆分 $n$ 的方案数。当 $k\rightarrow\infty$ 时，这就是 $p_n$。 这个生成函数有什么用？ #### 五边形数定理 $$\begin{aligned}\prod_{i=1}^{\infty}(1-x^i)&=\sum_{k=-\infty}^{\infty}(-1)^kx^{k(3k-1)/2}\\&=\sum_{k=0}^{\infty}(-1)^kx^{k(3k\pm1)/2}\\&=1-x-x^2+x^5+x^7-x^{12}-x^{15}+\dots\end{aligned}$$ 定理证明与生成函数关系不大，可以自行查阅 [Wikipedia](https://en.wikipedia.org/wiki/Pentagonal_number_theorem)。 由于我们有 $P(x)\prod_{i=1}^{\infty}(1-x^i)=1$，展开乘积则有 $$\begin{aligned}P(x)-xP(x)-x^2P(x)+x^5P(x)+x^7P(x)-x^{12}P(x)-\dots&=1\\1+xP(x)+x^2P(x)-x^5P(x)-x^7P(x)+x^{12}P(x)+\dots&=P(x)\end{aligned}$$ 类比斐波那契数列的 $f_n=[n=1]+f_{n-1}+f_{n-2}\Leftrightarrow F(x)=x+xF(x)+x^2F(x)$，令上式左右 $x^n$ 系数相等即得 $$p_n=[n=0]+p_{n-1}+p_{n-2}-p_{n-5}-p_{n-7}+p_{n-12}+\dots$$ 于是可以 $O(n\sqrt n)$ 求出 $p_1\dots p_n$，因为五边形数 $k(3k\pm1)/2\leq n$ 的话 $k$ 的个数是 $O(\sqrt n)$ 的。 实际上可以通过分治 FFT $O(n\log^2n)$ 或多项式求逆 $O(n\log n)$ 求出，但这并不是本篇文章的重点。 ## 4. 一道例题：CF947E Perpetual Subtraction ### Description 有一个非负整数 $x$ 。你要执行 $m$ 次操作，每次操作是 `x = randint(0, x)` （ `=` 表示赋值， `randint(0, x)` 均匀随机地在 $[0, x]$ 中取一个整数）。 现在已知初始的 $x$ 会随机在 $[0, n]$ 取值，且取 $i$ 的概率是 $p_i$ ，求最后取到 $[0, n]$ 每个数的概率。 $$n\leqslant10^5, m\leqslant10^{18}$$ ### Solution 看懂这个题解大概需要很简单的概率基础（就是小学概率那种）。 假设某个时候 $x=j$ 的概率是 $f_j$，那么做一次操作后，对每个 $0\leq i\leq j$，它都会有 $\frac1{j+1}$ 的概率会变成 $i$。 因此若令 $f^*_i$ 表示一次操作之后 $x=i$ 的概率，则 $$f^*_i=\sum_{j\geq i}\frac{f_j}{j+1}$$ （以下内容已经和概率无关了） 我们写出 $\{f^*_i\}$ 的生成函数： $$\begin{aligned}F^*(x)=&\sum_{i=0}^nf^*_ix^i\\=&\sum_{i=0}^n\left(\sum_{j=i}^n\frac{f_j}{1+j}\right)x^i\\=&\sum_{j=0}^n\frac{f_j}{j+1}\sum_{i=0}^jx^i\\=&\frac1{x-1}\sum_{j=0}^nf_j\frac{x^{j+1}-1}{j+1}\\=&\frac1{x-1}\sum_{j=0}^nf_j\int_1^xt^j{\rm d}t\\=&\frac1{x-1}\int_1^xF(t){\rm d}t\\\end{aligned}$$ 这个东西不太好搞，因为是从 $1$ 积分到 $x$（我们会做的是从 $0$ 积分到 $x$）。 那么可以搞一个 $G(x)=F(x+1)$，对应的，$G^*(x)=F^*(x+1)$，就可以发现 $$G^*(x)=F^*(x+1)=\frac1{(x+1)-1}\int_1^{x+1}G(t-1){\rm d}t=\frac1x\int_0^xG(t){\rm d}t$$ 这样的话，换成数列形式就是 $g^*_i=\frac1{i+1}g_i$。 这是进行一次操作，如果是 $m$ 次的话就是 $g^*_i=\frac1{(i+1)^m}g_i$。 至于从 $f$ 求 $g$ 和从 $g^*$ 求 $f^*$ 的话可以 FFT，具体（和代码）可以看 [\_rqy 的题解](https://rqy.moe/Solutions/cf947E/) qwq... ## 5. 总结 这么快就总结了...生成函数的内容实在太多，我打算分成几篇写...这一篇是初步，只是讲了讲基础的应用。 下一篇准备讲指数型生成函数（和 $\ln,\exp$ 之类的东西），大概例题会多一些... emm 如果有问题的话麻烦 QQ 上找我（luogu私信几个月看不了一次）...也很欢迎提供一些简单的例题...