_rqy's Blog

一只猫猫,想成为天才少女数学家!

0%

生成函数简介

生成函数

生成函数(generating function)又称母函数,是处理组合数学问题的一大利器。

普通型生成函数

Definition

对于一个数列 f=<f0,f1,f2>f=<f_0,f_1,f_2\dots> ,构造形式幂级数

F(x)=i=0fixiF(x) = \sum_{i=0}^{\infty}f_ix^i

qi称为数列ff的普通型生成函数(ordinary generating function, 下简称OGF)。

一些常见的OGF有:

数列 OGF
<1,0,0,><1,0,0,\dots> 11
<1,1,1,><1,1,1,\dots> 11x\frac1{1-x}
<1,2,3,><1,2,3,\dots> 1(1x)2\frac1{(1-x)^2}
<1,1,1,1,><1,-1,1,-1,\dots> 11+x\frac1{1+x}
<1,2,1,0,0,><1,2,1,0,0,\dots> (1+x)2(1+x)^2
<1,4,6,4,1,0,0,><1,4,6,4,1,0,0,\dots> (1+x)4(1+x)^4

根据OGF的定义,容易发现OGF的运算和数列运算之间的关系:

αF(x)+βG(x)=n(αfn+βgn)xnxmF(x)=n[nm]fnmxnF(x)i=0m1fixixm=nfn+mxnF(cx)=ncnfnxnF(x)=n(n+1)fn+1xn0xF(t)dt=n[n>0]fn1nxnF(x)G(x)=n(i=0nfigni)xn\begin{aligned} \alpha F(x)+\beta G(x)&=\sum_n(\alpha f_n+\beta g_n)x^n\\ x^mF(x)&=\sum_n[n\geq m]f_{n-m}x^n\\ \frac{F(x)-\sum_{i=0}^{m-1}f_ix^i}{x^m}&=\sum_nf_{n+m}x^n\\ F(cx)&=\sum_nc^nf_nx^n\\ F^\prime(x)&=\sum_n(n+1)f_{n+1}x^n\\ \int_0^xF(t)\mathrm{d}t&=\sum_n[n>0]\frac{f_{n-1}}nx^n\\ F(x)G(x)&=\sum_n\left(\sum_{i=0}^nf_ig_{n-i}\right)x^n \end{aligned}

以上所有公式都是比较显然的,在此不证。

不过特别要注意最后一个式子,即OGF的乘积对应数列卷积。

通过上面的运算规则可以推出下面的式子。

数列 OGF
<1,c,c2,c3,><1,c,c^2,c^3,\dots> 11cx\frac1{1-cx}
<1,n,(n2),(n3),><1,n,\binom n2,\binom n3,\dots> (1+x)n(1+x)^n
<1,n,(n+12),(n+13),><1,n,\binom{n+1}2,\binom{n+1}3,\dots> (1x)n(1-x)^{-n}
<0,1,12,13,><0,1,\frac12,\frac13,\dots> ln11x\ln\frac1{1-x}
<0,1,12,13,14,><0,1,-\frac12,\frac13,-\frac14,\dots> ln(1+x)\ln(1+x)
<1,1,12,16,124,><1,1,\frac12,\frac16,\frac1{24},\dots> exe^x

你会发现以上都是一些看上去很简单的东西。那么生成函数到底哪里厉害了呢?

Examples

注:这里只是简介…所以并没有太多的例子…

Example 1
fn={nn1fn1+fn2n>1f_n=\begin{cases}n&n\leq1\\f_{n-1}+f_{n-2}&n>1\end{cases}

简单的Fibonacci数列。

我们令 F(x)F(x) 表示其OGF,则

F(x)=nfnxn=n(fn+fn1+[n=1])xn=F(x)+xF(x)+x\begin{aligned} F(x)&=\sum_nf_nx^n\\ &=\sum_n(f_n+f_{n-1}+[n=1])x^n\\ &=F(x)+xF(x)+x \end{aligned}

从中我们解出F(x)=x1xx2F(x)=\frac{x}{1-x-x^2}。然而这有什么用呢?

我们令ϕ=1+52,ϕ^=152\phi=\frac{1+\sqrt5}{2},\hat\phi=\frac{1-\sqrt5}2,可以计算出F(x)=15(11ϕx11ϕ^x)F(x)=\frac{1}{\sqrt5}\left(\frac1{1-\phi x}-\frac1{1-\hat\phi x}\right)

根据11cx=ncnxn\frac1{1-cx}=\sum_nc^nx^n,我们可以知道fn=15(ϕnϕ^n)f_n=\frac1{\sqrt5}\left(\phi^n-\hat\phi^n\right)。就是这么简单。

Example 2

Warning!

许多线性递推的例子与上面的FF相类似,于是我们直接来跳到一个复杂的例子来。

众所周知的Catalan数列的生成函数如何呢?

fn={1n=0i=0n1fifni1n>0f_n=\begin{cases}1&n=0\\\sum_{i=0}^{n-1}f_if_{n-i-1}&n>0\end{cases}

F(x)=n([n=0]+i=0n1fifni1)xn=1+xn(i=0n1fifn1i)xn1=1+xF2(x)\begin{aligned} F(x)&=\sum_n\left([n=0]+\sum_{i=0}^{n-1}f_if_{n-i-1}\right)x^n\\ &=1+x\sum_n\left(\sum_{i=0}^{n-1}f_if_{n-1-i}\right)x^{n-1}\\ &=1+xF^2(x) \end{aligned}

亦即xF2F+1=0xF^2-F+1=0。代入二次方程求根公式,我们可以得到F(x)=1±14x2xF(x)=\frac{1\pm\sqrt{1-4x}}{2x}

然而±\pm取哪一个呢?我们发现一个数列ff的生成函数FF一定满足F(0)=f0F(0)=f_0(某些情况下或许应该写成limx0F(x)=f0\lim_{x\to0}F(x)=f_0)。然而f0=1f_0=1,这意味着F(0)=1F(0)=1。而如果我们令±\pm++,那么F(0)=20F(0)=\frac20是未定义的,这显然不是一个多项式应有的表现。

于是我们得到:Catalan数的生成函数是114x2x\frac{1-\sqrt{1-4x}}{2x}。这个生成函数令人有点难以置信,我们可以尝试展开它Warning!!!

展开它的方式是(x+y)c=i(ci)xiyci(x+y)^c=\sum_i\binom cix^iy^{c-i}在等式右端收敛(xy<1cN\left|\frac xy\right|<1\lor c\in \mathbb N)的情况下成立。然而生成函数是形式幂级数,这意味着我们不需要考虑收敛性。

于是

14x=n(12n)(4x)n\sqrt{1-4x}=\sum_n\binom{\frac12}{n}(-4x)^n (12n)=12(121)(12n+1)n!=(1)n11×1×3××(2n3)2nn!=(1)n1(2n2)!22n1n!(n1)!\because\binom{\frac12}n=\frac{\frac12(\frac12-1)\dots(\frac12-n+1)}{n!}=\frac{(-1)^{n-1}1\times1\times3\times\dots\times(2n-3)}{2^nn!}=\frac{(-1)^{n-1}(2n-2)!}{2^{2n-1}n!(n-1)!} 14x=n(12n)(4x)n=2n(2n2)!n!(n1)!xn\therefore\sqrt{1-4x}=\sum_n\binom{\frac12}{n}(-4x)^n=-2\sum_n\frac{(2n-2)!}{n!(n-1)!}x^n

这意味着114x2x=n(2n)!n!(n+1)!xn\frac{1-\sqrt{1-4x}}{2x}=\sum_n\frac{(2n)!}{n!(n+1)!}x^n,正是Catalan数的通项公式。

更多例子请见生成函数(可能有点困难…然而我的Blog里没几道简单题qaq…)。

或者Wikipedia

指数型生成函数

Definition

指数型生成函数(exponential generating function,简称EGF),其定义为

F(x)=nfnxnn!F(x)=\sum_nf_n\frac{x^n}{n!}

其意义体现在其乘法操作上:

F(x)G(x)=n(i=0n(ni)figni)xiF(x)G(x)=\sum_n\left(\sum_{i=0}^n\binom nif_ig_{n-i}\right)x^i

多出来的(ni)\binom ni告诉我们它适用于排列的计算(相对于OGF的普通卷积对应组合)。

EGF的运算法则:

αF(x)+βG(x)=n(αfn+βgn)xnn!xmF(x)=n[nm]nmfnmxnn!F(x)i=0m1fixixm=n1(n+m)mfn+mxnn!F(cx)=ncnfnxnn!F(x)=nfn+1xnn!0xF(t)dt=n[n>0]fn1xnn!F(x)G(x)=n(i=0n(ni)figni)xnn!\begin{aligned} \alpha F(x)+\beta G(x)&=\sum_n(\alpha f_n+\beta g_n)\frac{x^n}{n!}\\ x^mF(x)&=\sum_n[n\geq m]n^{\underline m}f_{n-m}\frac{x^n}{n!}\\ \frac{F(x)-\sum_{i=0}^{m-1}f_ix^i}{x^m}&=\sum_n\frac1{(n+m)^{\underline m}}f_{n+m}\frac{x^n}{n!}\\ F(cx)&=\sum_nc^nf_n\frac{x^n}{n!}\\ F^\prime(x)&=\sum_nf_{n+1}\frac{x^n}{n!}\\ \int_0^xF(t)\mathrm{d}t&=\sum_n[n>0]f_{n-1}\frac{x^n}{n!}\\ F(x)G(x)&=\sum_n\left(\sum_{i=0}^n\binom nif_ig_{n-i}\right)\frac{x^n}{n!} \end{aligned}

同样有一些基本的EGF:

数列 EGF
<1,1,1,><1,1,1,\dots> exe^x
<0,1,2,><0,1,2,\dots> xexxe^x
<1,c,c2,><1,c,c^2,\dots> ecxe^{cx}
\dots \dots

好吧你只需要注意到<fn><f_n>的EGF实际上就是<fnn!><\frac{f_n}{n!}>的OGF,就能找到不少例子。

那么EGF又有什么作用呢?

Examples

Example 1

贝尔数ωn\omega_n是把大小为nn的子集分割成若干非空不相交子集的方案数。

通过枚举第一个元素所在的子集大小ii,我们可以得到

ωn=[n=0]+i=1n(n1i1)ωni\omega_n=[n=0]+\sum_{i=1}^n\binom{n-1}{i-1}\omega_{n-i}

于是其EGF满足

F(x)=1+0xetF(t)dtF(x)=1+\int_0^xe^tF(t)\mathrm{d}t

两边求导

F(x)=exF(x)dFdx=exF(x)dFF=exdxdFF=exdxlnF=ex+CF=eex+C\begin{aligned} F^\prime(x)&=e^xF(x)\\ \frac{\mathrm{d}F}{\mathrm{d}x}&=e^xF(x)\\ \frac{\mathrm{d}F}F&=e^x\mathrm{d}x\\ \int\frac{\mathrm{d}F}F&=\int e^x\mathrm{d}x\\ \ln F&=e^x+C\\ F&=e^{e^x+C}\\ \end{aligned}

F(0)=ω0=1F(0)=\omega_0=1代入即得F(x)=eex1F(x)=e^{e^x-1}。这个多项式的系数可以利用eg=ngnn!e^g=\sum_n\frac{g^n}{n!}计算。

F(x)=eex1F(x)=e^{e^x-1}也可以这样理解:g(x)=ex1g(x)=e^x-1nn次项系数是“n个数组成一个非空集合”的方案数(显然),而gc(x)g^c(x)nn次项系数(由于EGF对应排列)就是“n个数划分成c个非空集合”的方案数。而由于这cc个集合是不可区分的,所以要乘上1c!\frac1{c!}。于是我们得到F(x)=ngn(x)n!=eg(x)=eex1F(x)=\sum_n\frac{g^n(x)}{n!}=e^{g(x)}=e^{e^x-1}

留坑待填

PS:_rqy太懒了以至于他不想写了 PS2: 已经坑了。