普通生成函数

序列 的普通生成函数（ordinary generating function，OGF）定义为形式幂级数：

既可以是有穷序列，也可以是无穷序列。常见的例子（假设 以 为起点）：

1. 序列 的普通生成函数是 。
2. 序列 的普通生成函数是 。
3. 序列 的生成函数是 。
4. 序列 的生成函数是 。

换句话说，如果序列 有通项公式，那么它的普通生成函数的系数就是通项公式。

基本运算

考虑两个序列 的普通生成函数，分别为 。那么有

因此 是序列 的普通生成函数。

考虑乘法运算，也就是卷积：

因此 是序列 的普通生成函数。

封闭形式

在运用生成函数的过程中，我们不会一直使用形式幂级数的形式，而会适时地转化为封闭形式以更好地化简。

例如 的普通生成函数 ，我们可以发现

那么解这个方程得到

这就是 的封闭形式。

考虑等比数列 的生成函数 ，有

等比数列的封闭形式与展开形式是常用的变换手段。

斐波那契数列的生成函数

接下来我们来推导斐波那契数列的生成函数。

斐波那契数列定义为 。设它的普通生成函数是 ，那么根据它的递推式，我们可以类似地列出关于 的方程：

那么解得

那么接下来的问题是，如何求出它的展开形式？

展开方式一

不妨将 当作一个整体，那么可以得到

我们得到了 的通项公式，但那并不是我们熟知的有关黄金分割比的形式。

展开方式二

考虑求解一个待定系数的方程：

通分得到

待定项系数相等，我们得到

解得

那么我们根据等比数列的展开式，就可以得到斐波那契数列的通项公式：

这也被称为斐波那契数列的另一个封闭形式（ 是一个封闭形式）。

对于任意多项式 ，生成函数 的展开式都可以使用上述方法求出。在实际运用的过程中，我们往往先求出 的根，把分母表示为 的形式，然后再求分子。

当对分母进行因式分解但有重根时，每有一个重根就要多一个分式，如考虑生成函数

的系数的通项公式，那么有

解得

那么

牛顿二项式定理

我们重新定义组合数的运算：

注意 的范围是复数域。在这种情况下。对于 ，有

二项式定理其实是牛顿二项式定理的一个特殊情况。

卡特兰数的生成函数

参考

Catalan 数的封闭形式

应用

接下来给出一些例题，来介绍生成函数在 OI 中的具体应用。

食物

这是一道经典的生成函数题。对于一种食物，我们可以设 表示这种食物选 个的方案数，并求出它的生成函数。而两种食物一共选 个的方案数的生成函数，就是它们生成函数的卷积。多种食物选 个的方案数的生成函数也是它们生成函数的卷积。

在理解了方案数可以用卷积表示以后，我们就可以构造生成函数（标号对应题目中食物的标号）：

1. 。
2. 。
3. 。
4. 。
5. 。
6. 。
7. 。
8. 。

那么全部乘起来，得到答案的生成函数：

然后将它转化为展开形式（使用封闭形式练习中第五个练习）：

因此答案就是 。

Sweet

在第 堆吃 个糖果的方案数（显然为 1）的生成函数为

因此总共吃 个糖果的方案数的生成函数就是

现在我们要求的是 。

由于 ，因此我们可以暴力展开 （最多只有 项）。

然后对 使用牛顿二项式定理：

我们枚举 中 项的系数，假设为 。那么它和 相乘后，对答案的贡献就是

这样就可以 地求出答案了。

时间复杂度 。