生成函数

生成函数:本质上就是一种泰勒展开式?(个人理解,因为它们之间实在有太多共性了。

简单的普通型生成函数中呢,有一个十分经典的例子:$1+x+x^2+x^3+\cdots=\frac{1}{1-x}$。

有一种很通俗的解释就是$\frac{1-x^{n+1}}{1-x}$,由于$x$在生成函数中没有实际意义,可取任意值,不妨令其级数收敛,

即$x\rightarrow 0,x^n\rightarrow 0$,也就相当于$\frac{1}{1-x}$了。

更广泛,也是本质的解释就是运用了泰勒展开式(通常$x_0=0$,也被成为麦克劳伦公式):

$f(x)=\sum\limits_{i=0}^{n} \frac{f^{(i)}(x_0)}{i!}(x-x_0)^i+R_n(x),R_n(x)\rightarrow 0$

详细可以参考这篇博文

关于导数初步可以了解这篇博文

那么我们就试着对$\frac{1}{1-x}$进行阶导。

根据链式法则,不妨将其分割成两个部分$\frac{1}{u},u=1-x$

有$(\frac{1}{u})'=-\frac{1}{u^2},(1-x)'=-1$,则$(\frac{1}{1-x})'=-(-\frac{1}{(1-x)^2})=\frac{1}{(1-x)^2}$。

一阶导:$\frac{1}{(1-x)^2}$

二阶导:

主要研究$(\frac{1}{u^2})'$,$\lim\limits_{\delta \rightarrow 0}\frac{\frac{1}{(u+\delta)^2}-\frac{1}{u^2}}{\delta}=\lim\limits_{\delta \rightarrow 0}\frac{\frac{-2\delta u-\delta^2}{(u+\delta)^2u^2}}{\delta}=-2\frac{u}{u^4}=-\frac{2}{u^3}$

显然地,二阶导就为$\frac{2}{(1-x)^3}$。

但这样一层层推也不是办法,找点规律。

如果忽略掉$\large\frac{\frac{-(\sum_{i=1}^n\delta^iu^{n-i})}{(u+\delta)^nu^n}}{\delta}$的中$(u+\delta)^nu^n$,那么其实际上类似于一个$x^n$的阶导。

也就是分子每一次都会$*n$.

即$n$阶导为:$\frac{(n-1)!}{(1-x)^n}$。

那么$\frac{1}{1-x}$的泰勒展开式的普通型生成函数$OGF$即为它本身。

由于这种理解需要具备一定的数学知识,所以在学习中提到的少之又少。

之前傻了,直接套 $f(g(x))=g'(x)f'(g(x))$ 就好了,关于 $x^n,n\in\text{R}$ 的证明

普通型生成函数

形如$F(x)=\sum\limits_{i=0}^\infty f_i x^i$,

其中的$f_i$等价于$\frac{F^{(i)}(x_0)}{i!}$。

运算法则(本质上就是导数运算:

  1. $aF(x)+bG(x)=\sum\limits_{i=0}^{\infty}(af_i+bg_i)x^i,a,b\in \operatorname{R}$
  2. $F(x)G(x)=\sum\limits_{n=0}^\infty(\sum\limits_{i=0}^nf_ig_{n-i})x^n$,卷积

一些常见的OGF

数列OGF
<$1,a,a^2,a^3,\cdots$>$\frac{1}{1-ax}$
<$1,n,\tbinom{n+1}{2}$,$\tbinom{n+2}{3}$,$\tbinom{n+3}{4}$,$\cdots$>$\frac{1}{(1-x)^n}$
<$1,n,\tbinom{n}{2},\tbinom{n}{3},\tbinom{n}{4},\cdots$>$(1+x)^n$
<$0,1,\frac{1}{2},\frac{1}{3},\frac{1}{4},\cdots$>$\ln\frac{1}{1-x}$
<$0,1,-\frac{1}{2},\frac{1}{3},-\frac{1}{4},\cdots$>$\ln (1+x)$
<$1,1,\frac{1}{2},\frac{1}{6},\frac{1}{24},\cdots$>$e^x$
$\cdots$$\cdots$

提示:$\ln'(x)=\frac{1}{x},(e^x)'=e^x$。