普通生成函数

序列 的普通生成函数(ordinary generating function,OGF)定义为形式幂级数:

既可以是有穷序列,也可以是无穷序列。常见的例子(假设 为起点):

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

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

基本运算

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

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

考虑乘法运算,也就是卷积:

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

封闭形式

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

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

那么解这个方程得到

这就是 的封闭形式。

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

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

小练习

请求出下列数列的普通生成函数(形式幂级数形式和封闭形式)。难度是循序渐进的。

  1. 是常数,)。
  2. 是常数,)。
答案

第一个:

第二个:

第三个(求导):

第四个(二项式定理):

第五个:

可以使用归纳法证明。

首先当 时,有

而当 时,有

斐波那契数列的生成函数

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

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

那么解得

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

展开方式一

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

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

展开方式二

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

通分得到

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

解得

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

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

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

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

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

解得

那么

牛顿二项式定理

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

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

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

卡特兰数的生成函数

参考 Catalan 数的封闭形式

应用

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

食物

食物

在许多不同种类的食物中选出 个,每种食物的限制如下:

  1. 承德汉堡:偶数个
  2. 可乐:0 个或 1 个
  3. 鸡腿:0 个,1 个或 2 个
  4. 蜜桃多:奇数个
  5. 鸡块:4 的倍数个
  6. 包子:0 个,1 个,2 个或 3 个
  7. 土豆片炒肉:不超过一个。
  8. 面包:3 的倍数个

每种食物都是以“个”为单位,只要总数加起来是 就算一种方案。对于给出的 你需要计算出方案数,对 取模。

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

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

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

然后将它转化为展开形式(使用封闭形式练习中第五个练习):

因此答案就是

Sweet

「CEOI2004」Sweet

堆糖果。不同的堆里糖果的种类不同(即同一个堆里的糖果种类是相同的,不同的堆里的糖果的种类是不同的)。第 个堆里有 个糖果。现在要吃掉至少 个糖果,但不超过 个。求有多少种方案。

两种方案不同当且仅当吃的个数不同,或者吃的糖果中,某一种糖果的个数在两个方案中不同。

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

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

现在我们要求的是

由于 ,因此我们可以暴力展开 (最多只有 项)。

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

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

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

时间复杂度


评论