The Mother Function - spirits away

[guevara]

The Mother Function - spirits away

https://ift.tt/0paKevk

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

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

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

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

$(3)A(x)=\sum i=0aixi=a0+\sum i=0ai+1xi+1=a0+\sum i=0(2\ast ai+1)xi+1=a0+x\ast (2\ast \sum i=0aixi+\sum i=0xi)=a0+x\ast (2\ast A(x)+\sum i=0xi)=a0+2x\ast A(x)+x1-x=2x\ast A(x)+x1-x$

由此我们可以得到：

$(4)A(x)=x(1-x)(1-2x)=x\{21-2x-11-x\}=\{2x+(2x)2+(2x)3+\cdots \}-\{x+x2+x3+\cdots \}=\sum i=1(2i-1)xi$

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

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

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

$(6)A(x)-1=2x\ast A(x)+x\sum i=1ixi$

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

$(7)\sum i=1ixi=\sum i=1x(d(xn)dx)=x(ddx)\sum i=1xi=x(ddx)11-x)=x(1-x)2$

所以，我们将上式带入到之前，可以得到：

$(8)A(x)=1-2x+2x2(1-x)2(1-2x)=-1(1-x)2+21-2x$

又因为

所以

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

$(11)Fn+2=Fn+1+Fnw.r.t.F0=0,F1=1$

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

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

所以

$(13)A(x)=x1-x-x2=15\{1(1-(1+5)x/2-11-(1-5)x/2\}$

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

$(14)Fi=15((1+52)i-(1+52)i)$

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

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

$(15)f(n,k)=f(n-1,k)+f(n-1,k-1)w.r.t.f(n,0)=1$

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

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

$(17)Bn(x)-1=(Bn-1(x)-1)+xBn-1(x)\Rightarrow Bn(x)=(1+x)Bn-1(x)\Rightarrow Bn(x)=(1+x)n\Rightarrow f(n,k)=(nk)$

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

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

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

• 是单独集合，原问题规约到了将$n-1$个元素划分为$k-1$子集的问题，此时的子集划分个数为$f(n-1,k-1)$;

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

所以，我们有如下的递推式：

$(19)f(n,k)=f(n-1,k-1)+kf(n-1,k)w.r.t.n\ge k\ge 0$

此时，我们设

由此定义我们可以得到：

$(21)Bk(x)=\sum nf(n,k)xn=\sum n(f(n-1,k-1)xn+kf(n-1,k)xn=x\sum nf(n-1,k-1)xn-1+kx\sum nf(n-1,k)xn-1=xBk-1(x)+kxBk(x)$

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

$(22)Bk(x)=x1-kxBk-1(x)=xk(1-x)(1-2x)(1-3x)\cdots (1-kx)$

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

$(23)f(n,k)=[xn]\{xk(1-x)(1-2x)(1-3x)\cdots (1-kx)\}=[xn-k]\{1(1-x)(1-2x)(1-3x)\cdots (1-kx)\}=[xn-k]\sum r=1k\alpha r1-rx=\sum r=1k\alpha r[xn-k]11-rx=\sum r=1k\alpha rrn-k$

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

$(24)xk(1-x)(1-2x)(1-3x)\cdots (1-kx)=\sum i=1k\alpha i1-ix$

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

$(25)\alpha r=1(1-1/r)(1-2/r)\cdots (1-(r-1)/r)(1-(r+1)/r)\cdots (1-k/r)=(-1)k-rrk-1(r-1)!(k-r)!$

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

$(26)f(n,k)=\sum r=1k(-1)k-rrnr!(k-r)!$

现在是不是感觉很爽!

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

$(27)f(m,n)=m\ast (f(m-1,n-1)+f(m,n-1))n\ge mf(m,m)=m!f(1,n)=1$

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

由此定义我们可以得到：

$(29)Bk(x)=\sum nf(n,k)xn=k\sum n(f(n-1,k-1)xn+f(n-1,k)xn=kx\sum nf(n-1,k-1)xn-1+kx\sum nf(n-1,k)xn-1=kx(Bk-1(x)+Bk(x))$

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

$(30)Bk(x)=kx1-kxBk-1(x)=xkk!(1-x)(1-2x)(1-3x)\cdots (1-kx)$

由此可得

$(31)f(n,k)=k![xn]\{xk(1-x)(1-2x)(1-3x)\cdots (1-kx)\}=k![xn-k]\{1(1-x)(1-2x)(1-3x)\cdots (1-kx)\}=k![xn-k]\sum r=1k\alpha r1-rx=k!\sum r=1k\alpha r[xn-k]11-rx=k!\sum r=1k\alpha rrn-k=k!\sum r=1k(-1)k-rrnr!(k-r)!$

via spiritsaway.info https://ift.tt/xtvPQyO

November 13, 2024 at 10:07AM