生成函数(mother function)是一种非常诡异的求数列通项的方法。核心思想是把数列a的第n项当作某个某个位置函数A(x)的xn系数系数。我们通过递推式来求得A(x),然后将A(x)展开来得到xn的系数既是数列的通项:
下面我们就以几个循序渐进的例子来讲解这个生成函数方法的使用。
线性递推¶
线性递推式是数列递推式中最简单的递推式,其形式如下:
其中p,q为常数。这里为了简单起见,我们以p=2,q=1,a0=0为例来说明生成函数方法的使用。假设该数列的生成函数为A(x)=∑i=0aixi,则我们可以得到
由此我们可以得到:
所以,通过这么长的递推,我们终于得到了ai=2i−1,虽然说这个递推高一水平的人就可以做出来。但是我们总是会经历一个从这TM也需要证到这TM也能证的过程吧。
伪线性递推¶
所谓伪线性递推是我生造的一个词,其递推结构与之前的一样,只不过q,p可能为i的线性表示。下面以例子来说明:
这里重复之前的推导过程,我们可以得到:
此时我们需要利用微积分的知识:
所以,我们将上式带入到之前,可以得到:
又因为
所以
斐波那契数列¶
斐波那契数列作为数列里面最经典的例子,本文自然不能放过。其数列递推式如下:
同样 ,设其生成函数为A(x) ,我们可以得到
所以
然后经过一些稀里糊涂的中间步骤,我们可以得到
双索引递推¶
在上文中我们只涉及到了一个变量x,此时对应只有一个索引的数列的情况。对于有两个不同索引的数列递推式,单一变量的生成函数不再适用,我们需要添加另外的一个变量y来构造双变量的生成函数B(x,y)。这种情况。在排列组合问题中,双索引的数列是非常常见的。例如,给定非负整数n,k且0≤k≤n,我们能从{1,2,⋯,n}中得到多少个不同的k子集。
此时我们假设f(n,k)是该问题的解,我们可以非常容易的得到下面的递推式
此时我们定义一个新的生成函数
根据原来的递推公式15,我们可以得到
双变量生成函数¶
对付一些简单的双索引递推公式,我们很多时候用单变量的生成函数即可处理。然而,不是所有的双索引递推都是这么简单的。考虑下面的一个排列组合的例子:将一个大小为n的集合分割为k个不为空的子集。例如n=4,k=2时,其不同划分有如下几种:
我们用f(n,k)来代表其不同的子集划分数。根据{n}这个元素是否单独作为一个集合,我们可以把原来的问题分为两种情况:
-
是单独集合,原问题规约到了将n−1个元素划分为k−1子集的问题,此时的子集划分个数为f(n−1,k−1);
-
不是单独集合,此时对于任意的一个n−1元素的k划分,元素n可以插入到这k个划分的任意一个集合中,此时的子集划分个数为f(n−1,k)∗k。
所以,我们有如下的递推式:
此时,我们设
由此定义我们可以得到:
所以,我们可以得到Bk(x)的解析式为
现在我们的问题就在于如何求出后面的展开式。为此,我们定义一个记号[xn]B(x)为函数B(x)展开式中xn的系数。此时
在这里我们得到了一个看上去非常美的结果,但是其实目前还没啥用,因为我们还没有求出满足下式的常数αr。
为了得到αr,我们又需要利用一些诡异的技巧。首先在上式两边都乘以1−rx,然后令x=1/r。此时右边就只剩下αr了。所以
将此式带入之前的式子,可得
现在是不是感觉很爽!
其实写本篇文章的动机是为了求解这个递推式
该递推式的背景是一道微软的面试题,具体的内容忘记了。这是一个写代码的题,主要考察点是DP优化。但是正如前面所说的,我们可以直接求出其通项公式。其求解过程跟之前的基本一样.此时,我们设
由此定义我们可以得到:
所以,我们可以得到Bk(x)的解析式为
由此可得