普通生成函数入门 | Sevenki's Blog

在 Netlify 博客上的前注

~~にまで，搬过来之后 mathjax 炸大锅了。~~

~~如果你真的想要阅读本文章，请前往我的洛谷专栏查看。~~

~~以后我可能会修一下，但是现在太懒了所以没修。~~

UPDATE: 修好了！让我们祝贺！

原文

由于是【入门】，比较追求通俗，所以有一些专业术语的表达问题请见谅！本文引用了很多文章的内容，在这里感谢文章的作者们！
Command_block 的文章让我学会很多！详见文末。

一个有趣的引入

仅仅让你感兴趣而已！这一部分可以跳过，但是看一下会更好！虽然公式很多，但是很容易看得懂！如果你不懂 $F (x)$ 的含义，请先跳到下面的【前置】部分！观察以下数字：

0.0104091625364964820 . . .

我们发现从左往右数，小数部分每两位数字都是完全平方数。但是有同学会指出我说法的谬误，到后面不是没有这个规律了嘛！真的没有吗？由于我们只给每个数字分配了两位，因此后面诸如“100”此类位数大于两位的数字就会自然溢出（或者说，进位）到前面去。比如 $. . . . . . .648 2 0. . . . . . . .$ ，这里的 $2$ 本来是 $81$ 的 $1$ ，由于后面 $100$ 的百位装不下了于是进位到前面。请问这是一个有理数还是无理数？答：有理数。考虑如下幂级数：

\begin{aligned} F (x) & = \sum_{i = 0}^{+ \infty} i^{2} x^{i} \\ = 0^{2} x^{0} + 1^{2} x^{1} + 2^{2} x^{2} + 3^{2} x^{3} + 4^{2} x^{4} . . . \end{aligned}

那么，把 $F (x)$ 乘上 $x$ ，可得：

x F (x) = 0^{2} x^{1} + 1^{2} x^{2} + 2^{2} x^{3} + 3^{2} x^{4} . . .

我们把以下两式用上式减去下式，得出 $(1 - x) F (x)$ ：

\begin{aligned} F (x) & = 0^{2} x^{0} + 1^{2} x^{1} + 2^{2} x^{2} + 3^{2} x^{3} + 4^{2} x^{4} . . . \\ x F (x) & = 0^{2} x^{1} + 1^{2} x^{2} + 2^{2} x^{3} + 3^{2} x^{4} . . . \\ (1 - x) F (x) & = (1^{2} - 0^{2}) x^{1} + (2^{2} - 1^{2}) x^{2} + (3^{2} - 2^{2}) x^{3} + (4^{2} - 3^{2}) x^{4} . . . \\ = (1 + 0) (1 - 0) x^{1} + (2 + 1) (2 - 1) x^{2} + (3 + 2) (3 - 2) x^{3} + (4 + 3) (4 - 3) x^{4} . . . \\ = 1 x^{1} + 3 x^{2} + 5 x^{3} + 7 x^{4} . . . \end{aligned}

再将 $(1 - x) F (x)$ 乘上 $x$ ，用同样的方法上减下：

\begin{aligned} (1 - x) F (x) & = 1 x^{1} + 3 x^{2} + 5 x^{3} + 7 x^{4} . . . \\ x (1 - x) F (x) & = 1 x^{2} + 3 x^{3} + 5 x^{4} . . . \\ (1 - x)^{2} F (x) & = 1 x^{1} + 2 x^{2} + 2 x^{3} + 2 x^{4} . . . \end{aligned}

再将 $(1 - x)^{2} F (x)$ 乘上 $x$ ，用同样的方法上减下：

\begin{aligned} (1 - x)^{2} F (x) & = 1 x^{1} + 2 x^{2} + 2 x^{3} + 2 x^{4} . . . \\ x (1 - x)^{2} F (x) & = 1 x^{2} + 2 x^{3} + 2 x^{4} . . . \\ (1 - x)^{3} F (x) & = x + x^{2} \end{aligned}

我们惊奇地发现无穷项被消除了！那么，我们再来尝试得出 $F (x)$ 的值，把 $(1 - x)^{3}$ 移到等式右边…

\begin{aligned} (1 - x)^{3} F (x) & = x + x^{2} \\ F (x) & = \frac{x + x^{2}}{(1 - x)^{3}} \end{aligned}

$F (x)$ 被我们用分式表达出来了！等等，如果把 $x = 2$ 代入，那就会得出以下逆天结果…

F (2) = \sum_{i = 0}^{+ \infty} i^{2} 2^{i} = \frac{2 + 2^{2}}{(1 - 2)^{3}} = - 6

这明显很不符合常理啊喂！原因是在 $x = 2$ 时， $F (x)$ 并不是收敛的！但是我们把 $x = 0.01$ 带进去，发现 $F (0.01)$ 就是我们上面提到的神奇的数，我们用刚刚计算出来的分式带入算算…

\begin{aligned} F (0.01) & = \frac{0.01 + {0.01}^{2}}{(1 - 0.01)^{3}} \\ = \frac{0.0101}{0.970299} \\ = \frac{10100}{970299} \end{aligned}

把这个分数喂入计算器里，我们得到了满意的结果：
很有趣！这就是生成函数推导的其中一点点有相关的内容！是相关，并不是生成函数内容！但是万一我要研究的东西不收敛怎么办？【普通生成函数】的重点在于将一个数列用一个 形式幂级数 表达，其中 $x$ 起到 代数符号 的作用，没有实际意义，因此我们不关心它的收敛情况。实际上你甚至会见到收敛半径为 $0$ 的生成函数，不过并不需要在意这些。听不懂没关系，我们接着往下。

前置

本部分大致由简到繁。

【前置1】什么是 $F (x)$

虽然我没学过高中数学，但是大家肯定或多或少了解： $F (x)$ 是一个自变量为 $x$ 的函数。这样理解当然没问题！但是，我这里想把 $F (x)$ 的概念重新讲述一遍：
$F (x)$ 是一个关于 $x$ 的数学式的记号。这个【数学式】，可以有有限项，可以有无限项，可以是代数式 … 这是一个记号，是为了方便表达的：举个例子， $7 + x + 2 x^{2} - 3 x^{3}$ 。你肯定不想每次都把这个式子写下来吧。这时候我们用一个记号 $F (x)$ 来代指它，令 $F (x) = 7 + x + 2 x^{2} - 3 x^{3}$ 。但是为什么不是 $F$ 而是 $F (x)$ 呢？因为这个式子的值是不确定的，有一个“未知数” $x$ ，令 $x$ 等于不同值会使该数学式变成不同值。所以我们在这个“表达记号”里开了一个“窗口”，方便表述未知数 $x$ 取不同值时的对应情况。比如，上述的 $F (x)$ 中，就有 $F (1) = 7 + 1 + 2 - 3 = 7$ 。不过在生成函数中，我们并不关心 $x$ 的具体取值。（有关原因下文讨论）因此我们只需要知道，类似于 $F (x)$ 、 $G (x)$ 此类是对数学式子的一种简记。

【前置2】一些符号的约定

$[x^{n}] F (x) 或 f_{x}$ 表示 $F (x)$ 的 $x^{n}$ 项的系数。

【前置3】多项式基础

这里讨论的多项式，默认都是只有一个字母（非常数） $x$ 的多项式。两个多项式的卷积，其实就是像初中学过的“整式的乘法”一样，把两个多项式乘起来。e.g:

\begin{aligned} F (x) & = 5 + x + 2 x^{2} \\ G (x) & = 2 - 7 x - x^{2} \\ (F * G) (x) & = (5 + x + 2 x^{2}) (2 - 7 x - x^{2}) \\ = - 2 x^{4} - 15 x^{3} - 8 x^{2} - 33 x + 10 \end{aligned}

总结一下规律：一个次数为 $i$ 和次数为 $j$ 的项相乘，会对结果上次数为 $i + j$ 的项的系数增加原来次数为 $i$ 和次数为 $j$ 的项的系数的乘积的贡献，即

f_{i} x^{i} \times g_{j} x^{j} = f_{i} g_{j} x^{i + j}

这样我们就可以将多项式乘法写成一般的形式，令 $f_{i}, g_{i}$ 分别为 $F (x), G (x)$ 的 $x_{i}$ 的系数。

(F * G) (x) = \sum_{i + j = k} f_{i} g_{j} x^{k}

这样子，可以得出 $[x^{k}] (F * G) (x) = \sum_{i = 0}^{k} f_{i} g_{k - i}$ 。

Main

【主线1-1】生成函数的定义

对于一个数列 $f$ ，它的生成函数就是以下式子：

F (x) = \sum_{i = 0}^{n} f_{i} x^{i}

其中 $n$ 是数列的长度。如果该数列是无穷数列，那么 $n = + \infty$ 。我们把数列的每一项乘上 $x$ 的幂次，得到了这个数列的一个新的表达。注意，后文在描述时应该不会再给出求和运算的上界，请读者自行判断。

What is $x$ ？

$x$ 究竟是什么？是一个未知数吗？它在这里并不是未知数。它只充当一个“代数符号”的作用，并不需要有具体取值。所以这里的 $x$ 可以不当做“数字”看。我们只约定这个 $x$ 存在着某种乘法运算，使得我们可以通过幂次等形式表达“生成函数”。生成函数研究的根本是研究数列。所以，这个“生成函数”只是用于研究数列的工具，函数值什么的并不存在着具体意义。（指在生成函数的研究中没有意义）。所以，生成函数的收敛性什么的根本不重要！因为 本来你把 $x$ 的取值带入得出的结果对于研究数列就没有意义，讨论 $x$ 取何值时函数收敛又有什么作用呢？在【支线2-1】中你将会对这一部分有更深的理解。

【主线1-2】封闭形式的推导

观察以下无穷数列：

f = 1, 1, 1, 1, 1, 1, 1. . .

我们根据定义，很容易知道它的生成函数为：

F (x) = 1 + x + x^{2} + x^{3} + x^{4} . . .

但是你有没有感觉这样无限求和的式子非常不利于研究！所以，我们希望有一种神奇的魔法，把无限求和替换成有限的代数式…
我们先来看一个神奇的操作（这里先不用上面的 $F (x)$ 来演示，我们换一个函数，具体见下）：

\begin{aligned} G (x) & = 1 x^{0} + 2 x^{1} + 3 x^{2} + 4 x^{3} + 5 x^{4} . . . \\ x G (x) & = 1 x^{1} + 2 x^{2} + 3 x^{3} + 4 x^{4} . . . \end{aligned}

我们发现， $x G (x)$ 就是将所有系数 $g_{x}$ 向后平移了一位！那我们能不能 通过这种平移来消去无穷项 呢？我们再回到 $F (x)$ ，使用上述方法：

\begin{aligned} F (x) & = 1 x^{0} + 1 x^{1} + 1 x^{2} + 1 x^{3} + 1 x^{4} . . . \\ x F (x) & = 1 x^{1} + 1 x^{2} + 1 x^{3} + 1 x^{4} . . . \end{aligned}

观察上面对齐的项，发现从 $x_{1}$ 往后的几项都一模一样！这时手痒的你肯定会用上式减去下式：

\begin{aligned} F (x) & = 1 x^{0} + 1 x^{1} + 1 x^{2} + 1 x^{3} + 1 x^{4} . . . \\ x F (x) & = 1 x^{1} + 1 x^{2} + 1 x^{3} + 1 x^{4} . . . \\ (1 - x) F (x) & = 1 x^{0} = 1 \\ F (x) & = \frac{1}{1 - x} \end{aligned}

我们把无穷项都消去了！消去之后左边多了个 $(1 - x)$ ，那把它除到右边不就得到 $F (x)$ 了！这样子我们就求出了无穷数列生成函数的封闭形式！那么对于有穷数列呢？那已经是封闭形式了，不过有一些也可以进一步化简。类似地，利用 错位相减 法，我们可以很容易求出绝大多数序列的生成函数。当然，对于某些序列，如果它可以由已知序列的生成函数构造出来，那么会更容易求一点。练习：

求 $0, 1, 2, 3, 4, 5, 6, 7, 8. . .$ 的生成函数先向右平移一位，做一下减法就变成了 $0, 1, 1, 1, 1, 1. . .$ 。这下会了吧！
求 ${k^{0}, k^{1}, k^{2}, k^{3}, k^{4} . . .}$ 的生成函数。这个只需要我们在向后平移系数的同时给序列乘上一个 $k$ 再错位相减就可以啦！
求 ${1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0. . .}$ 的生成函数。一次直接向后平移系数 $4$ 位就可以啦！
求 ${1, 0, 0, 0, 2, 0, 0, 0, 3, 0, 0, 0. . .}$ 的生成函数。这不就是第一个练习和第三个练习的融合吗？

【主线1-3】生成函数的运算

我们来研究数列 $f$ 和 $g$ ，如果对他们的生成函数做运算会怎么样？

\begin{aligned} F (x) & = \sum_{i} f_{i} x^{i} \\ G (x) & = \sum_{i} g_{i} x^{i} \\ F (x) \pm G (x) & = \sum_{i} (f_{i} \pm g_{i}) x^{i} \end{aligned}

对两个数列的生成函数做加减得到的新的生成函数，就是将两个数列对应项相加减得到的新数列的生成函数！那如果是乘法呢？

\begin{aligned} F (x) & = \sum_{i} f_{i} x^{i} \\ G (x) & = \sum_{i} g_{i} x^{i} \\ (F * G) (x) & = \sum_{i} f_{i} x^{i} \sum_{j} g_{j} x^{j} \\ = \sum_{i, j} f_{i} g_{j} x^{i + j} \\ = \sum_{k} \sum_{i \leq k} f_{i} g_{k - i} x^{k} \end{aligned}

我们把得到的新的生成函数所对应的数列，叫作数列 $f$ 与 $g$ 的卷积。为什么叫“卷”积？请看一下图示过程。对于一个结果数列的 $x^{k}$ ，它的计算是这样的：
就是维护两个指针，然后各往反方向“卷”。

思考题

把一个数列与 $f = {1, 1, 1, 1, 1, 1. . .}$ 做卷积，结果如何？答：结果是原数列的前缀和。除法这里先不讨论，涉及到多项式求逆。

【支线1-1】斐波那契！（求通项公式）

学会了生成函数，来看看它的实际应用！你有没有发现，斐波那契数列通项公式里的 $\sqrt{5}$ 很莫名其妙？现在我们就来用魔法求出它的通项公式！但是我们只会已知【通项公式】或【递推式】求【生成函数】，怎么反过来求？利用一些简单数列生成函数的特点。斐波那契数列定义： $f_{0} = 0, f_{1} = 1, f_{n} = f_{n - 1} + f_{n - 2} (n \geq 2)$ 。先求一下生成函数：

\begin{aligned} F (x) & = f_{0} x^{0} + f_{1} x^{1} + f_{2} x^{2} + f_{3} x^{3} . . . \\ x F (x) & = f_{0} x^{1} + f_{1} x^{2} + f_{2} x^{3} . . . \\ x^{2} F (x) & = f_{0} x^{2} + f_{1} x^{3} . . . \\ (1 - x - x^{2}) F (x) & = f_{0} x^{0} + f_{1} x^{1} - f_{0} x^{1} = x \\ F (x) & = \frac{x}{1 - x - x^{2}} \end{aligned}

这个不是我们熟悉的形式啊？怎么逆？我们考虑把它拆成一些更简单的分式相加的形式。先把分母因式分解一下：解一元二次方程 $1 - x - x^{2} = 0$ ，直接套公式，得 $x_{1} = \frac{- \sqrt{5} - 1}{2}, x_{2} = \frac{\sqrt{5} - 1}{2}$ 。那么 $1 - x - x^{2} = (x - x_{1}) (x - x_{2})$ 。什么？你问我为什么？我们在解一元二次方程的时候有时候会运用“十字相乘法” ~~（在我看来就是瞪眼法）~~ 将方程分解成形如 $(x - x_{1}) (x - x_{2}) = 0$ 的形式，那么可以直接得出 $x_{1}, x_{2}$ 是方程的解。反过来，由于 $x_{1}, x_{2}$ 是方程的解，所以 $(x - x_{1}) (x - x_{2}) = 0$ 自然成立。需要注意的是，我们这里两个方程的二次项系数都可以看做是 $1$ ，因此可以这么搞。否则需要先将原方程提取一下二次项系数，再按该方法分解。然后我们就可以设

\begin{aligned} \frac{a}{x - x_{1}} + \frac{b}{x - x_{2}} & = \frac{x}{1 - x - x^{2}} \\ \frac{a (x - x_{2}) + b (x - x_{1})}{1 - x - x^{2}} & = \frac{x}{1 - x - x^{2}} \\ a (x - x_{2}) + b (x - x_{1}) & = x \\ (a + b) x - (a x_{2} + b x_{1}) & = x \end{aligned}

上式可得以下方程：

{\begin{cases} a + b = 1 \\ a x_{2} + b x_{1} = 0 \end{cases}

解得

{\begin{cases} a + b = 1 \\ a x_{2} + b x_{1} = 0 \end{cases}