生成函数引入

发表于 更新于 分类于 ， 阅读次数：

本文共约 8600 字。

Key Words：生成函数，简单递推数列，系数收敛性，二项式系数，差分与前缀和，组合恒等式，自然数幂和，哑演算*

基本概念

  • 生成函数

    对于无穷数列 ，构造形式幂级数 称 为数列 的生成函数（Generating Function）。

什么是形式幂级数？它和多项式有什么区别？封闭形式中的运算含义是什么？我们为何默认它收敛？见《多项式的计算》“形式幂级数”一节。

生成函数将零散的数列 封装为一个整体 ，这将带来许多便利。

A generating function is a device somewhat similar to a bag. Instead of carrying many little objects detachedly, which could be embarrassing, we put them all in a bag. And then, we have only one object to carry, the bag. —— George Polya

生成函数就像个包。捣鼓数列的每一项太烦，把它们塞进包里就简单了。—— 佐治亚·波利亚

常见数列的生成函数

先给出一系列常见数列的生成函数，在推导中，若能将陌生生成函数转化为若干熟悉生成函数的组合，则可以直接根据下表提取系数。

数列生成函数封闭形式

我们把目光放在表格中的第一行，它是最著名的生成函数。数列 的生成函数是 ，为了得到封闭形式，使用扰动法： 解得 ，即

做代换 ，可得数列 的生成函数是 。这是表格的第二行。

表格的三、四、五行提供了二项式系数的结论，它们的证明由（广义）二项式定理给出。

生成函数的运算

常见数列操作对应的生成函数运算如下：

  • 系数前移：，即减去前 项之后除以 。
  • 系数后移：。
  • 系数乘 ：，先求导然后后移即可。将算子 记为 。

简单递推数列

  • 例题 6.2.1 「一道高考题」

    数列 满足 ，，求 的通项公式。

Solution：记 ，则

整理得

解得封闭形式

它不在表中，无法直接提取系数。考虑进行分式分解，即将 分解为 的线性组合，再分别提取系数。

我们断言 能被表示成两个分式的和，待定系数为

通分并对比系数，可解得 。

提取系数，则

总结：本题的解答可以分为以下四步：

  • 构造目标数列的生成函数。

  • 将条件（如数列的递推关系）转化为生成函数方程。

  • 解方程，得到封闭形式。

  • 将封闭形式转化为我们熟悉的形式，提取系数。

  • 例题 6.2.2 「斐波那契数列」

    斐波那契数列 满足 ，且对于 有 。求 的通项公式。

Solution：记斐波那契数列的生成函数为 ，使用扰动法得

解得封闭形式

接下来进行分式分解。首先将分母因式分解，解一元二次方程 得 有 我们断言 能表示成两个分式的和，待定系数为 ： 通分并对比系数，解得 现在 中系数均已知，可以提取系数。 将 的值代入并整理，得斐波那契数列的通项公式

  • 例题 6.2.3 「又一道高考题」

    数列 满足 ，，求 的通项公式。

Solution：记 对应的生成函数为 ， 的生成函数是 。

记 ，，对应的生成函数为 。易知 。

可以看做对数列 按位乘 ，故

根据递推式，

在 及以上次数成立。 项经检验也成立。

代入 解得

断言存在 使得

展开对比系数，解得 ，则

提取系数得

二项式系数

在《组合数学》一章中，我们介绍了二项式系数 的概念和一些基本公式，只涉及到 且 的情形（这样的二项式系数具有良好的组合意义，故又名组合数）。接下来从代数视角将定义域进行拓展，并介绍更多的处理技巧。

  • 下降幂

    对 定义 的 次下降幂为

  • 广义二项式系数

    对于 ，定义

常用恒等式

对于广义二项式系数 ，首先值得观察的是 为负整数的情形。 观察表格中的数，递推公式 仍成立。而且，这些数似乎都是某些加了正负号的组合数，不难发现：

  • 上指标反转

证明： 两侧同除 即得。

注意：当上标 不是 的时候，对称恒等式 不再生效。

  • 广义二项式定理

    对于 ，形式幂级数 有展开式

证明：考虑 的麦克劳林展开，多次求导会使系数形成下降幂。

  • 范德蒙德卷积

证明：注意到加法卷积的形式，构造 两侧提取 系数得

  • 下降幂的二项式定理

证明：将范德蒙德卷积中的组合数展开 这说明原式在 时成立。

构造二元多项式 它在 上均不超过 次，只需考虑 个系数。

在 时成立，这提供了无穷多个“点值”，足以让我们确定 的系数全是 ，这就证明了原式。（这意味着，范德蒙德卷积实际上也对实数成立）

这种方法称为“多项式推理法”：先用组合方法证明整数的情形，然后用插值推广到实数。

类似地，上升幂也满足二项式定理，利用上指标反转公式 即可证明。

  • 加倍公式

证明：

两个错开 的下降幂放大以后可以拼成一个下降幂。

加倍公式提供了处理 形组合数（被称为中心二项式系数）的方法。

令 取 得 ，两侧除以 可得

使用上指标反转又得

右侧的 比 更容易处理。利用这一点，尝试证明下面的恒等式

  • 例题 6.2.4 「一个中心二项式系数的恒等式」

    求证

Solution：这是卷积的形式，构造 则 接下来求 ，由广义二项式定理： 故 ，。

差分与前缀和

对于数列 ，其差分与前缀和为两个新数列，记为 ，满足 记 为 进行 次差分/前缀和的结果。

记 的生成函数为 、 的生成函数为 ，则 反过来，易知 的生成函数 。这有另一个解释：与数列 进行加法卷积，相当于前缀和。

记 的生成函数为 ，有 提取系数得

  • 例题 6.2.5 链上二次求和（简化版）

    维护序列 ，有 个操作，需要支持单点修改，单点查询 。

    ，。

Solution： 对 的贡献是 。

中 是常数，这是一个关于“相对距离” 的 次多项式，记为 ，则 记 ，则 记 ，则 。若能求出 ，代入 即可。

容易 预处理 的系数。 是 的前缀和，可以树状数组维护。复杂度 。

二项式反演

二项式反演是一类重要的组合变换。

  • 数列 满足

    则

证明：

法一：拆卷积

从左侧等式出发，将组合数拆开整理得

辨认出加法卷积，记 ，则 。

辨认出 ，则 ，展开得 > 法二：直接构造生成函数，写成简单复合方程

构造生成函数

对 进行换元，欲得到 整体，记 ，解得 ，代入整理得

提取系数得

法一告诉我们，二项式反演是一种加法卷积，可以用 FFT 加速计算。

法二和二项式反演的组合本质有关，具体见《符号化反演》一节。

简单组合求和问题

在这一小节中，我们将介绍一些典型的组合求和问题，并用生成函数解决它们。

二项式系数

  • 例题 6.2.6.

    记 为斐波那契数列，证明恒等式

证明：直接写出生成函数 结果 正是斐波那契数列前移一位对应的生成函数。

  • 例题 6.2.7.

    求下列求和的封闭形式

证明：直接写出生成函数 提取 系数得

  • 例题 6.2.5.

    证明恒等式

证明：此处有两个变量，直接按 写出二元生成函数，验证两侧的生成函数相等即可。

对于左侧

注意到 具有很好的封闭形式，可以到此打住。对于右侧，不需要再写二元生成函数，只需要在 上构造一元生成函数即可

注：继续推导可得 。

数列的 次方和

  • 给出数列 ，对于 ，分别求出 。

写出答案的生成函数 只需要 的前 项系数，可以分治 FFT 计算，复杂度 。

自然数幂和

  • 自然数幂和多项式

    多项式 满足 时 ，称其为自然数幂和多项式。

例如 ，则 。

  • 结论： 对 都存在，且次数为 。

证明略。接下来，我们将求出 的具体系数。（下面的内容也可视为一种构造性证明）

尝试建立二元生成函数 不妨设 进行推理，由多项式推理法，这样能提供无数个点值，得到的是正确的多项式。 此处 仍然保留在求和上标中，无法得到 的多项式的形式。（事实上，这是走了“数列 k 次方和的”老路）

重新尝试。考虑为 配上 的因子，后面我们会看到，这是一类常用手法（无论是组合上还是代数上）。令 可以发现， 导致了 的产生，使和式有了一个封闭形式。

接下来提取 系数得到 ： 记 ，则 所需的 可以用多项式求逆计算（实际上，这是伯努利数的 EGF），复杂度 。

习题

  • 组合求和其一

    求 的封闭形式。

Solution：构造生成函数

即为答案。

  • 组合求和其二

    求

    的封闭形式。

Solution：构造生成函数

记 ，则 （对比常数项，易得开根取 ）

即为答案。

  • 组合变换其二

    数列 满足

    证明

Solution：构造生成函数 欲得到 整体，记 ，解得 （根据常数项的收敛性，取正号），则

提取系数得

此处的任务是【例题6.1.5】“幂的横截”。 的复合逆是 （显然，因为前者就是这么构造出来的），根据（扩展）拉格朗日反演

若给出 ，求 ，计算多项式复合即可（先复合 ，再复合 ），复杂度 。

见闻*

哑演算

哑演算，又称本影演算，其思想是将数列 映射到形式幂 ，然后用幂级数的代数推导代替传统的和式推导，从而简化推理过程。

设 为是形式幂元（被称作“哑元”），构造线性变换 满足如下性质：

  • 的定义域为 的形式幂级数（显然，定义域是线性空间， 构成定义域的一组基）

  • （根据这一规则，可以计算任意的 ，即对每个单项式分别求和）

  • 对于任意 和不含 的式子 （可以是常数或者关于 的多项式等），有 （线性性）

  • 对于任意 ，都有 （线性性）

将数列 和幂级数 沟通了起来，我们尝试观察 的 OGF 和 EGF 在 中的形式 两者都有很好的封闭形式，这能够简化我们的计算，同时，也为我们提取生成函数留下两个出口。

由于 具有线性性， 等线性算子也可以往里塞 。例如，我们知道 EGF 求导相当于将数列前移一位，尝试写出 中的形式 我们借由 得到了正确的结果。

伯努利数

  • 伯努利数 满足如下恒等式

    求 。

Solution：首先看传统方法。将和式展开成卷积的形式，再辨识出封闭形式

其中 ，由此可得 多项式求逆即可。

下面来看哑演算方法。令线性变换 满足 ，观察递推式在 中的形式

构造 的生成函数（EGF）得

同时，右侧 的 EGF 显然是 ，这样就得到了 ，殊途同归。

我们引入 并将其消除，本质上完成的任务是 传统方法要做到这一点并不难，该例并没有体现出哑演算的优越性，下面再看两例。

组合变换其三

  • 给出 ，对于 ，分别求

    答案对 取模。

Solution：令线性变换 满足 。则

此处若直接构造答案的生成函数，无法提取 的生成函数，故到此剥除 ，用其他方法接着处理。

记 ，则

显然这是个线性算法（输入是 输出是 ），将其转置得到

注意 和 的系数对齐了，记 ，则

众所周知，复合一次分式可以卷积计算。将这个算法转置，复杂度 。

传统推导留作读者练习。

线性递推

  • 数列 有递推公式 。

    给出 ，快速求解 的值。

Solution：令线性变换 满足 。则将递推式用 转写：

根据线性性，整理得

为了方便，记 当且仅当 。

根据 的线性性， 连接的“等式”可以（左右两侧同时）加减形式幂级数，或乘除实数，但不能乘除关于 的形式幂级数。

上式简写为

记 （恰好是特征多项式）则 。

于是我们知道，对于任意 ， ，这相当于多项式取模，于是

二者等价。

考虑我们要求的 ，只需计算 ， 只有系数 ，则

推导完毕。计算时，只需倍增求解 ，FFT 可做到 。

不难发现这和市面上流传的常系数线性递推算法等价。