物理

生成函数（1）：普通生成函数

众所周知，生成函数（母函数）是研究数列的一种非常强大的工具，在组合计数中我们经常会遇到它？本文旨在在竞赛的要求之上，更加详细更加全面地介绍生成函数的知识与应用。

生成函数实际上是给一个数列$\{ a_n \}$赋予了一个形式幂级数。首先我们来理解什么是形式幂级数。我们希望通过研究一个数列的生成函数，来了解一个数列的性质。幂级数意味着它具有“多项式”的形式（不一定有限），形式意味着我们只看这个幂级数长什么样子，与它的敛散性、收敛半径这些无关。例如我们知道，当x绝对值小于1时，我们有等式$\frac{1}{1-x}=\sum^{\infty}_{i=0} x^i$（当然x=0时$x^0$无定义，这里就不管这些细节了），但是从形式幂级数的角度，我们不在意它的收敛半径，我们认为$\frac{1}{1-x}=\sum^{\infty}_{i=0} x^i$就是成立的。最主要的好处在于，形式幂级数的系数、指数都能反映大量的信息，而且我们可以将一些数列的性质转化为形式幂级数的运算，这是很方便的。

生成函数主要分为三类：普通生成函数，指数型生成函数以及Dirichlet生成函数。本节我们研究普通生成函数，也就是大家最熟悉的形如$f(x)=\sum^{\infty}_{i=0} a_ix^i$的生成函数。在本文中，所有生成函数均指代普通生成函数。

我们首先考察形式幂级数的运算。形式幂级数$\sum^{\infty}_{i=0} a_ix^i=\sum^{\infty}_{i=0} b_ix^i$当且仅当$a_i=b_i$恒成立。这一事实看似平凡，实际上是我们利用生成函数解决问题的关键。对于形式幂级数，我们有如下运算法则：

（1）$\sum^{\infty}_{i=0} a_ix^i+\sum^{\infty}_{i=0} b_ix^i=\sum^{\infty}_{i=0} (a_i+b_i)x^i$

（2）$\alpha \sum^{\infty}_{i=0} a_ix^i=\sum^{\infty}_{i=0} \alpha a_ix^i$

（3）$(\sum^{\infty}_{i=0} a_ix^i )(\sum^{\infty}_{i=0} b_ix^i)=\sum^{\infty}_{i=0} c_ix^i$，其中$c_n=\sum^{n}_{i=0}a_ib_{n-i}$

读者可以找几个简单的多项式来检查这几条法则。（3）是很有意思的一点，因为它告诉我们两个数列的卷积的生成函数长什么样？意味着当我们看到一个数列满足一个卷积的性质时，我们可以考虑用（3）来得到这个数列，或者把它拆成更简单的数列。它有个很明显的特征，就是角标和与求和变量无关。我们再给几个常用的公式后来看几个例子。

（1）$\frac{1}{(1-x)^k}=\sum^{\infty}_{i=0} C^{k-1}_{i+k-1}x^i$

（2）$e^x=\sum^{\infty}_{i=0} \frac{x^i}{i!}$

(2)放在这里不太合适，应该等讲指数型生成函数时再给出，但是我想讲讲论坛上一位同学提的问题，需要用到这个公式。另外可以看出来这就是指数函数的泰勒展开，所以在使用生成函数时，不会算了可以暴力泰勒展开，但这不一定能得到简单的结果。

给定正整数k，令$h_n$表示不定方程$\sum^{k}_{i=1} x_i=n$的自然数解的个数。

这道题应该算是很简单的了，有高中水平就足以解决，我们试试用生成函数。生成函数的想法非常简单，我们让每一个$x_i$从0开始跑遍所有自然数，这样我们就得到了所有$x_i$可能的组合，因此它里面包含了对于所有自然数$n$，上述不定方程的解，我们只需要把他们分类提取出来即可。具体操作很简单，我们考虑形式幂级数$\frac{1}{1-x}=\sum^{\infty}_{i=0} x^i$，k个这样的幂级数相乘会发生什么呢？我们可以认为，这个成绩展开，相当于给每一个$x_i$赋了一个值，然后相乘，在指数上就会变成他们的和。而对于展开后的幂级数，恰有$h_n$个$x^n$，因此我们有$\sum^{\infty}_{i=0} h_ix^i=\frac{1}{(1-x)^k}$。利用公式(1)即可得到答案。

这个例子启发了我们一点，形式幂级数的指数可以体现“和”，而系数可以体现“个数”，这样可以将它转化为一些形式幂级数的乘积。我们往往可以利用这个原理来解决一些组合计数的问题。提取系数这一步我想分享一个东西，有可能我们我们需要提取的不是某一项，而是一些项系数的和。如果我们要提取幂次为素数p的倍数的项的系数的和，可以考虑引入单位根，这是因为设$\zeta$为p次本原单位根，$\sum^{p-1}_{i=0} \zeta^{im}$在m为p的倍数时，取值为p，其他时候取值为0。利用这个性质我们就能消去不需要的项。反之，如果我们看到了长得像单位根的东西，也可以还原成母函数。这个方法称为单位根法。

我们还可以用生成函数来解决一些递推数列的问题。

求Fibonacci数列的通项公式。

这个问题也很简单，用特征根方程就可以秒杀。我们试试生成函数的方法。记Fibonacci数列的第n+1项为$f_n$(为了把第0项凑出来)，考虑他的生成函数$f(x)=\sum^{\infty}_{i=0} f_ix^i$，我们只需要在生成函数上"复刻"它的递推公式即可。为了找到$f_i+f_{i+1}$这一项，我们考虑$(1+x)f(x)=f_0+(f_0+f_1)x+(f_1+f_2)x^2+\cdot \cdot \cdot=f_1+f_2x+f_3x^2+\cdot \cdot \cdot$，这样我们就发现规律了，这玩意和原本的生成函数几乎一样啊。我们两边再乘上一个x，有$(x^2+x)f(x)=f(x)-1$，即$f(x)=\frac{-1}{x^2+x-1}$，我们只需要裂项，就可以凑出$\frac{A}{B-x}$型的分式，利用$\sum^{\infty}_{i=0} x^i＝\frac{1}{1-x}$就可以得到想要的形式幂级数。

更一般地，学过复分析的同学都知道，只要是个有理函数，都可以给他拆成一些形如$\frac{A}{(B-x)^k}$的项的和，我们只需要把分母因式分解后待定系数，利用极限来计算每个系数（其实暴力计算也可以）。

下面我们看满足更复杂关系的数列，这是来自论坛上一位同学的题目。

已知$\sum^{n}_{i=0} \frac{a_i}{(n-i)!}=1$对任意自然数n都成立，求$a_n$。

这道题一眼看上去就是非常标准的卷积，所以我们直接考虑生成函数。我们有$\sum^{\infty}_{n=0} x^n=\sum^{\infty}_{n=0} (\sum^{n}_{i=0} \frac{a_i}{(n-i)!})x^n=(\sum^{\infty}_{i=0} a_ix^i)(\sum^{\infty}_{j=0} \frac{x^j}{j!})$，这样我们就把想要的生成函数分离出来了，并且剩下的部分都是很好计算的，因为我们可以利用泰勒展开，知道$\sum^{\infty}_{i=0} a_ix^i=(\sum^{\infty}_{i=0} x^i)(\sum^{\infty}_{i=0} \frac{(-1)^i}{i!}x^i)$，再次展开后就能得到我们想要的结果。

从这里我们也能看到一个有用的结果，设$\{ a_n\}$的生成函数为$f(x)$，那么$\{ \sum^{n}_{i=0} a_i \}$的生成函数为$\frac{f(x)}{1-x}$.

此外，对于形式幂级数，我们同样可以求导，称为形式微分或者形式导数。求导的好处在于我们可以把指数拿到系数上，变成一个因子。有时这会变得简单，而有时求导反而会让结果更复杂。为了消去这种不良影响，我们将引入指数型生成函数（长得跟泰勒展开一模一样），这是后话了。我们也给出一道例题。

设$H_0=0$，当n为正整数时，$H_n=\sum^{n}_{i=1} \frac{1}{n}$，求$\{ H_n \}$的生成函数。

这里给出的实际上就是调和级数，现在我们要求它的生成函数。由前所说，我们只需要看$\{ \frac{1}{n}\}$的生成函数$\sum^{\infty}_{i=1} \frac{x^i}{i}$即可，而我们只需对它求导即可消去分母，再做一次积分就能得到我们想要的结果。