Loading [MathJax]/jax/output/HTML-CSS/jax.js

The Mother Function

生成函数(mother function)是一种非常诡异的求数列通项的方法。核心思想是把数列a的第n项当作某个某个位置函数A(x)xn系数系数。我们通过递推式来求得A(x),然后将A(x)展开来得到xn的系数既是数列的通项:

A(x)=i=0aixi

下面我们就以几个循序渐进的例子来讲解这个生成函数方法的使用。

线性递推

线性递推式是数列递推式中最简单的递推式,其形式如下:

an+1=pan+q

其中p,q为常数。这里为了简单起见,我们以p=2,q=1,a0=0为例来说明生成函数方法的使用。假设该数列的生成函数为A(x)=i=0aixi,则我们可以得到

A(x)=i=0aixi=a0+i=0ai+1xi+1=a0+i=0(2ai+1)xi+1=a0+x(2i=0aixi+i=0xi)=a0+x(2A(x)+i=0xi)=a0+2xA(x)+x1x=2xA(x)+x1x

由此我们可以得到:

A(x)=x(1x)(12x)=x{212x11x}={2x+(2x)2+(2x)3+}{x+x2+x3+}=i=1(2i1)xi

所以,通过这么长的递推,我们终于得到了ai=2i1,虽然说这个递推高一水平的人就可以做出来。但是我们总是会经历一个从这TM也需要证到这TM也能证的过程吧。

伪线性递推

所谓伪线性递推是我生造的一个词,其递推结构与之前的一样,只不过q,p可能为i的线性表示。下面以例子来说明:

ai+1=2ai+ia0=1

这里重复之前的推导过程,我们可以得到:

A(x)1=2xA(x)+xi=1ixi

此时我们需要利用微积分的知识:

i=1ixi=i=1x(d(xn)dx)=x(ddx)i=1xi=x(ddx)11x)=x(1x)2

所以,我们将上式带入到之前,可以得到:

A(x)=12x+2x2(1x)2(12x)=1(1x)2+212x

又因为

1(1x)2=i=0(i+1)xi

所以

ai=2i+1i1

斐波那契数列

斐波那契数列作为数列里面最经典的例子,本文自然不能放过。其数列递推式如下:

Fn+2=Fn+1+Fnw.r.t.F0=0,F1=1

同样 ,设其生成函数为A(x) ,我们可以得到

A(x)=x+x(F2x+F3x2+F4x3+)=x+x{{F1x+F2x2+F3x3+}+{F0x+F1x2+F2x3+}}=x+x(A(x)+xA(x))

所以

A(x)=x1xx2=15{1(1(1+5)x/211(15)x/2}

然后经过一些稀里糊涂的中间步骤,我们可以得到

Fi=15((1+52)i(1+52)i)

双索引递推

在上文中我们只涉及到了一个变量x,此时对应只有一个索引的数列的情况。对于有两个不同索引的数列递推式,单一变量的生成函数不再适用,我们需要添加另外的一个变量y来构造双变量的生成函数B(x,y)。这种情况。在排列组合问题中,双索引的数列是非常常见的。例如,给定非负整数n,k0kn,我们能从{1,2,,n}中得到多少个不同的k子集。

此时我们假设f(n,k)是该问题的解,我们可以非常容易的得到下面的递推式

f(n,k)=f(n1,k)+f(n1,k1)w.r.t.f(n,0)=1

此时我们定义一个新的生成函数

Bn(x)=k0f(n,k)xk

根据原来的递推公式15,我们可以得到

Bn(x)1=(Bn1(x)1)+xBn1(x)Bn(x)=(1+x)Bn1(x)Bn(x)=(1+x)nf(n,k)=(nk)

双变量生成函数

对付一些简单的双索引递推公式,我们很多时候用单变量的生成函数即可处理。然而,不是所有的双索引递推都是这么简单的。考虑下面的一个排列组合的例子:将一个大小为n的集合分割为k个不为空的子集。例如n=4,k=2时,其不同划分有如下几种:

(12),(34);(13),(24);(14),(23);(123),(4);(124),(3);(134),(2);(234)(1)

我们用f(n,k)来代表其不同的子集划分数。根据{n}这个元素是否单独作为一个集合,我们可以把原来的问题分为两种情况:

  • 是单独集合,原问题规约到了将n1个元素划分为k1子集的问题,此时的子集划分个数为f(n1,k1);

  • 不是单独集合,此时对于任意的一个n1元素的k划分,元素n可以插入到这k个划分的任意一个集合中,此时的子集划分个数为f(n1,k)k

所以,我们有如下的递推式:

f(n,k)=f(n1,k1)+kf(n1,k)w.r.t.nk0

此时,我们设

Bk(x)=nf(n,k)xn

由此定义我们可以得到:

Bk(x)=nf(n,k)xn=n(f(n1,k1)xn+kf(n1,k)xn=xnf(n1,k1)xn1+kxnf(n1,k)xn1=xBk1(x)+kxBk(x)

所以,我们可以得到Bk(x)的解析式为

Bk(x)=x1kxBk1(x)=xk(1x)(12x)(13x)(1kx)

现在我们的问题就在于如何求出后面的展开式。为此,我们定义一个记号[xn]B(x)为函数B(x)展开式中xn的系数。此时

f(n,k)=[xn]{xk(1x)(12x)(13x)(1kx)}=[xnk]{1(1x)(12x)(13x)(1kx)}=[xnk]kr=1αr1rx=kr=1αr[xnk]11rx=kr=1αrrnk

在这里我们得到了一个看上去非常美的结果,但是其实目前还没啥用,因为我们还没有求出满足下式的常数αr

xk(1x)(12x)(13x)(1kx)=ki=1αi1ix

为了得到αr,我们又需要利用一些诡异的技巧。首先在上式两边都乘以1rx,然后令x=1/r。此时右边就只剩下αr了。所以

αr=1(11/r)(12/r)(1(r1)/r)(1(r+1)/r)(1k/r)=(1)krrk1(r1)!(kr)!

将此式带入之前的式子,可得

f(n,k)=kr=1(1)krrnr!(kr)!

现在是不是感觉很爽!

其实写本篇文章的动机是为了求解这个递推式

f(m,n)=m(f(m1,n1)+f(m,n1))nmf(m,m)=m!f(1,n)=1

该递推式的背景是一道微软的面试题,具体的内容忘记了。这是一个写代码的题,主要考察点是DP优化。但是正如前面所说的,我们可以直接求出其通项公式。其求解过程跟之前的基本一样.此时,我们设

Bk(x)=nf(n,k)xn

由此定义我们可以得到:

Bk(x)=nf(n,k)xn=kn(f(n1,k1)xn+f(n1,k)xn=kxnf(n1,k1)xn1+kxnf(n1,k)xn1=kx(Bk1(x)+Bk(x))

所以,我们可以得到Bk(x)的解析式为

Bk(x)=kx1kxBk1(x)=xkk!(1x)(12x)(13x)(1kx)

由此可得

f(n,k)=k![xn]{xk(1x)(12x)(13x)(1kx)}=k![xnk]{1(1x)(12x)(13x)(1kx)}=k![xnk]kr=1αr1rx=k!kr=1αr[xnk]11rx=k!kr=1αrrnk=k!kr=1(1)krrnr!(kr)!
Published:
2015-04-28 19:37
Category:
Tag: