生成函数的妙用

在这一节中，你将会看到，我们是如何用全新的数学工具去解决一个数学难题的。

有这么一个经典的概率问题：平均需要抛掷多少次硬币，才会首次出现连续两个正面？答案是6次。它的计算方法大致如下。

首先，让我们来考虑这样一个问题：k枚硬币摆成一排，其中每一枚硬币都可正可反；如果里面没有相邻的正面，则一共有多少种可能的情况？这可以用递推的思想来解决。不妨用 f（k）来表示摆放k枚硬币的方案数。我们可以把这些方案分成两类：最后一枚硬币是反面，或者最后一枚硬币是正面。如果是前一种情形，则我们只需要看前k-1枚硬币有多少摆法就可以了；如果是后一种情形，那么倒数第二枚硬币必须是反面，因而这种情形下的方案数就取决于前k-2枚硬币的摆放方案数。因此我们得到，（）因而事实上 f（k）就等于Fk﹢2，其中Fi表示斐波那契数列1，1，2，3，5，8，…的第i 项。

而“抛掷第k次才出现连续两个正面”的意思就是，最后三枚硬币是反、正、正，并且前面k-3枚硬币中正面都不相邻。因此，在所有2k种可能的硬币正反序列中，只有F_k-1个是满足要求的。也就是说，我们有的概率在第二次抛币就得到了连续两个正面，有的概率在第三次得到连续两个正面，有的概率在第四次得到连续两个正面……因此，我们要求的期望值就等于：

不过，怎样求解这个无穷级数的和呢？你会发现，数学归纳法、求通项公式、错位相消等传统的数列求和方法此时似乎都没有了用武之地。现在，让我们来介绍一种更加强大的数列处理工具——生成函数。

让我们先来说说什么是生成函数吧。生成函数就是对数列进行编码的一种方式。我们可以用一个无穷级数a₁·x¹﹢a₂·x²﹢a₃·x³+…把整个数列的全部信息装进去，其中第i次项系数就表示数列的第i项。因此，斐波那契数列的生成函数就可以写成：

厉害就厉害在，我们可以把生成函数表示成一个更简单的形式。先来看看g（x）·x的结果：

再看看g（x）﹢g（x）·x的结果：

你会发现，斐波那契数列的递推性质，使得上面这行式子与g（x）本身非常相像。事实上，如果把g（x）的每一项都除以x，再减去最前面多出来的1，就能得到上面的这行式子了。因此，我们有：

我们甚至可以就此解出g（x）来：

于是，整个无穷级数g（x）被我们化简为了一个关于x的代数式！注意，虽然这个等式只在x充分小（小到级数g（x）收敛）的时候才有意义，不过这并不妨碍我们用这个代数式来代表斐波那契数列的生成函数。我们可以把斐波那契数列看做是生成函数的一个“展开”：

也就是说，这么一个小小的代数式就容纳了斐波那契数列的全部信息！

生成函数是如此地具有代表性，以至于在研究数列时，我们常常会给出它的生成函数。在网络在线数列百科全书oeis.org中，生成函数几乎是必不可少的一项。例如，在斐波那契数列的描述中，FORMULA一栏的第一行就是 G.f.:x/（1-x-x^2），说的就是斐波那契数列的生成函数。

更绝的是，我们还可以直接对数列的生成函数进行变换，从而得到新的数列。比方说，在生成函数上再乘以一个x，我们就会让每一项的x的指数加 1，从而让整个数列右移一位，得到了一个新的数列F_i-1，即0，1，1，2，3，5，…

现在，我们需要用各种代数运算手段，对等式左边的生成函数进行变换，让等式右边的展开式变成本文开头的那个数列。什么操作能够同时让数列第1项除以2，第2项除以4，第3项除以8，以此类推，让所有的第i项都除以2ⁱ呢？我们可以把所有的x都用x/2来替代：

化简一下：

这就是数列的生成函数了。接下来，我们想要让第i项系数乘以一个i，也就是想要让每一项的系数都乘以该项的次数，这该怎么办呢？最神奇的地方出现了——我们对生成函数进行求导：

也就是：

不过，求导的同时，x的次数也移动了一位。我们在生成函数上再乘以x，把x的次数纠正回来：

这就是本文最初的那个数列的生成函数了。令x＝1，便有：

答案跃然纸上！