物理

生成函数（2）：指数型生成函数

本文介绍第二种类型的生成函数－－指数型生成函数。以下生成函数均指代指数型生成函数。数列$\{ a_n\}$的指数型生成函数是$f(x)=\sum^{\infty}_{i=0} \frac{a_i}{i!}x^i$，它和普通生成函数的运用原理是一样的，但是它们不同的形式决定的他们主要处理问题的类型有所不同。当一个数列和阶乘密切相关时，指数型生成函数会非常有用。比如，如果有一个数列的递推公式中出现了大量的组合数，那么可以考虑指数型生成函数。此外，我们之前也说过，指数型生成函数可以很好的消除求导导致的不良影响，类比指数函数，我们也能猜到指数型生成函数最有力的工具就是形式微分，为此，我们引入微分算子$\mathrm{D}=\frac{\mathrm{d}}{\mathrm{d}x}$。

记[n]={1,2,...,n}，$B_n$为集合$[n]$上划分的个数，并且定义$B_0=1$。

对于这种具有明显递降性质的数列，肯定考虑找它的递推公式。设包含元素n的那个集合有k个元素，那么剩余的k-1个元素要从$[n-1]$中选取，共有$C^{k-1}_{n-1}$中选法，剩下的集合构成了一个n-k元集合的划分，共$B_{n-k}$种选法，故我们得到了递推公式$B_n=\sum^{n}_{k=1} C^{k-1}_{n-1}B_{n-k}$。显然，我们应该考虑指数型生成函数而非普通生成函数，设其指数型生成函数为$B(x)=\sum^{\infty}_{i=0} \frac{B_i}{i!}x^i$。为了匹配递推公式中的n-1，我们在两边求导，并代入递推公式，得到$\mathrm{D}B(x)=\sum^{\infty}_{n=1} \frac{1}{(n-1)!} (\sum^{n}_{k=1} C^{k-1}_{n-1}B_{n-k})x^n$，这一坨看着非常恐怖，但是我们已经做完了。我们把它化简一下，立马就得到了$\mathrm{D} B(x)=\sum^{\infty}_{n=1} \sum^{n}_{k=1} \frac{1}{(k-1)!} \frac{B_{n-k}}{(n-k)!}x^{n-1}$。我们说过，角标之和与求和变量无关是卷积的一个特征，因此这个式子完全符合卷积的形式，因此我们考虑将它拆成两个形式幂级数的乘积。但是要注意，我们所有的求和都应该从0开始，这里我们需要调整一下角标，我们有$\mathrm{D}B(x)=\sum^{\infty}_{n=0} \sum^{n}_{k=0} \frac{1}{k!} \frac{B_{n-k}}{{(n-k)!}}x^n=\sum^{\infty}_{i=0} \frac{x^i}{i!} \sum^{\infty}_{j=0} \frac{B_j}{j!}x^j$，于是我们有$\mathrm{D}B(x)=e^xB(x)$。

下面只需要求解这个微分方程即可。如果这么简单的微分方程你都不会的话，那我梆梆给你两拳并且罚抄Nature佬的常微分算符一千遍。结合初值条件，解得$B(x)=e^{e^x-1}$。从而我们有$B(x)=\frac{1}{e} \sum^{\infty}_{k=0} \frac{e^{kx}}{k!}=\frac{1}{e} \sum^{\infty}_{k=0} \frac{1}{k!} \sum^{\infty}_{n=0}\frac{k^n}{n!}x^n$，整理之后，对比系数得到$B_n=\frac{1}{e}\sum^{\infty}_{k=0} \frac{k^n}{k!}$。

从上述这个例子我们会有两点体会，第一，当出现大量阶乘或者组合数时，指数型生成函数会非常好用，第二，利用形式微分，我们往往会得到有关生成函数的一个微分方程，这一点不同于普通生成函数。为什么形式微分在指数型生成函数中这么重要呢？其中一个原因是微分算子作用于指数型生成函数相当于一个“平移”算子。如下事实是容易证明的：

若数列$\{ a_n \}$的指数型生成函数为$f(x)$，则数列$\{ a_{n+1}\}$的指数型生成函数为$\mathrm{D}f(x)$。

反复利用这个性质，我们能得到关于形式微分的一个重要性质。

若数列$\{ a_n \}$的指数型生成函数为$f(x)$，则数列$\{ a_{n+k}\}$的指数型生成函数为$\mathrm{D}^kf(x)$。

求Fibonacci数列的通项公式。

这个问题我们前面已经研究过了，我们用新的视角再看一遍。设Fibonacci数列的指数型生成函数为$f(x)$，那么它的递推意味着$\mathrm{D}^2f(x)=\mathrm{D}f(x)+f(x)$，这就是一个简单的二阶微分方程，结合初值即可解出$f(x)$。这样看来指数型生成函数在解决线性递推时比普通生成函数还要简单一些。

从这个例子中，我们能再次体会到形式微分在指数型生成函数中起到的重要作用。利用类似的方法，我们能很容易地理解微分方程与数列线性递推的特征根方程间的联系。

下面我们要研究另一个很重要的点。如果我们知道两个数列的指数型生成函数（后面生成函数默认都是指数型生成函数）$f(x)$和$g(x)$，那么$f(x)g(x)$是哪个数列的指数型生成函数？

设$f(x)=\sum^{\infty}_{i=0} \frac{a_i}{i!}x^i$，$g(x)=\sum^{\infty}_{i=0} \frac{b_i}{i!} x^i$，那么我们有$f(x)g(x)=\sum^{\infty}_{n=0} \sum^{n}_{k=0} \frac{a_k}{k!}\frac{b_{n-k}}{(n-k)!}x^n$，看到分母是两个和为定值的数的阶乘之积，很容易让我们联想到组合数，所以我们来凑组合数。得到$f(x)g(x)=\sum^{\infty}_{n=0} \sum^{n}_{k=0} \frac{C^{k}_{n}a_kb_{n-k}}{n!}x^n$。我们发现现在我们就有想要的结果了。

若$f(x)$与$g(x)$为数列$\{ a_n\}$与$\{ b_n\}$的生成函数，那么$f(x)g(x)$是数列$\{ \sum^{n}_{k=0}C^{k}_{n}a_kb_{n-k}\}$的生成函数。

为什么我们说这个结果很重要呢？观察新数列每一项的形式，是否觉得很眼熟呢？这难免让我们联想到二项式反演。这里我们把二项式反演作为一个推论给出。

若$b_n=\sum^{n}_{k=0} C^{k}_{n} a_k$，则有$a_n=\sum^{n}_{k=0} (-1)^{n-k}b^k$成立，反之也成立。

如果刚刚不觉得熟悉，那我给出了二项式反演之后呢？证明非常简单，同样考虑它们的生成函数，由性质2，第一式告诉我们$g(x)=e^xf(x)$，第二式告诉我们$f(x)=e^{-x}g(x)$，两式显然等价。换而言之，二项式反演是性质2的特例，或者说性质2是二项式反演的推广，无论怎么说，它都展示了它强大的威力。性质2得到的新数列这一形式称为二项式卷积。事实上，三种生成函数都对应了一种卷积的形式，同样也会对应一种反演，普通生成函数对应的一般的卷积（它的反演比较平凡），指数型生成函数对应的是二项式卷积以及二项式反演，Dirichlet生成函数对应的是Dirichlet卷积以及Mobius反演。

我们现在再次回到例1，它现在是个很简单的问题了。利用性质1与性质2，我们马上能看出要求解的微分方程，在此不多赘述。

下面是一个具体应用例子。

求每位数均为奇数且9和1出现次数为偶数次的n位数个数$h_n$。

这个问题可以换一种说法，不定方程$x_1+x_2+x_3+x_4+x_5=n$的自然数解中有多少组满足$x_1$与$x_2$为偶数？那这个问题与我们之前遇到过的一个问题相似。我们考虑$h_n$的生成函数$h(x)=(\sum^{\infty}_{i=0} \frac{x^{2i}}{(2i)!})^2(\sum^{\infty}_{i=0} \frac{x^i}{i!})=(\frac{e^x+e^{-x}}{2})^2(e^x)^3$，化简后，我们可以得到$h(x)=\frac{e^{5x}+2e^{3x}+e^x}{4}$，展开之后对比系数即可得到答案。

最后留一个小小的练习题：

已知$\sum^{n}_{i=0} \frac{a_i}{(n-i)!}=1$对任意自然数n都成立，求$a_n$。（用指数型生成函数解决）