生成函数

组合数学术语

生成函数即母函数，是组合数学中尤其是计数方面的一个重要理论和工具。最早提出母函数的人是法国数学家拉普拉斯（LaplaceP.S.）在其1812年出版的《概率的分析理论》中明确提出。生成函数有普通型生成函数和指数型生成函数两种，其中普通型用的比较多。生成函数的应用简单来说在于研究未知（通项）数列规律，用这种方法在给出递推式的情况下求出数列的通项，生成函数是推导斐波那契（Fibonacci）数列的通项公式方法之一。另外生成函数也广泛应用于编程与算法设计、分析上，运用这种数学方法往往对程序效率与速度有很大改进。

概念

生成函数即母函数，是组合数学中尤其是计数方面的一个重要理论和工具。

生成函数有普通型生成函数和指数型生成函数两种，其中普通型用的比较多。形式上说，普通型生成函数用于解决多重集的组合问题，而指数型母函数用于解决多重集的排列问题。

最早提出母函数的人是法国数学家拉普拉斯（LaplaceP.S.）在其1812年出版的《概率的分析理论》中明确提出“生成函数的计算”，书中对生成函数思想奠基人——欧拉（Euler L）在18世纪对自然数的分解与合成的研究做了延伸与发展。生成函数的理论由此基本建立。

生成函数的应用简单来说在于研究未知（通项）数列规律，用这种方法在给出递推式的情况下求出数列的通项，生成函数是推导斐波那契（Fibonacci）数列的通项公式方法之一，另外组合数学中的卡特兰数（Catalan）也可以通过生成函数的方法得到。

另外生成函数也广泛应用于编程与算法设计、分析上，运用这种数学方法往往对程序效率与速度有很大改进。

普通型母函数

定义

对于任意数列a0,a1,a2...an 即用如下方法与一个函数联系起来：

则称G(x)是数列的生成函数(generating function)。

例子：

比较典型的是：

指数型母函数

用来整体表示数列的幂级数。

生成函数是构造一个多项式函数g(x)，使得x的n次方系数为f(n)。

生成函数最绝妙的是某些生成函数可以化简为一个很简单的函数。也就是说，不一定每个生成函数都是用一长串多项式来表示的。例如函数f(n)=1 （n当然是属于自然数的），它的生成函数是：（每一项都是1，即使n=0时也有x0系数为1，所以有常数项）。再仔细一看，这就是一个有无穷多项的等比数列求和。

我们举一个例子说明，一些具有实际意义的组合问题也可以用像这样简单的一个函数全部表示出来。

考虑这个问题：从只有4个MM的二班选n个MM出来有多少种选法。学过简单的排列与组合的同学都知道，答案就是C(4,n)。也就是说。从n=0开始，问题的答案分别是1,4,6,4,1,0,0,0,...（从4个MM中选出4个以上的人来方案数当然为0喽）。那么它的生成函数g(x)就应该是g(x)=1+4x+6x2+4x3+x4。这不就是……二项式展开吗？于是，g(x)=(1+x)4。

你或许知道，；但你或许不知道，即使k为负数和小数的时候，也有类似的结论：（一直加到无穷；式子看着很别扭，自己写到草稿纸上吧，毕竟这里输入数学式子很麻烦）。其中，广义的组合数C(k,i)就等于k(k-1)(k-2)(k-i+1)/i!，例如C(4,6)=4*3*2*1*0*(-1)/6!=0，再例如C(-1.4,2)=(-1.4)*(-2.4)/2!=1.68。后面这个就叫做牛顿二项式定理。当k为非负整数时，所有i>k时的C(k,i)中分子都要“越过”0这一项，因此后面C(k,k+1),C(k,k+2)之类的都为0了，与我们的经典二项式定理结论相同；不同的是，牛顿二项式定理中的指数k可以是任意实数。

我们再举一个例子说明一些更复杂的生成函数。n=x1+x2+x3+...+xk有多少个非负整数解？这道题是学排列与组合的经典例题了。把每组解的每个数都加1，就变成n+k=x1+x2+x3+...+xk的正整数解的个数了。教材上或许会出现这么一个俗气的名字叫“隔板法”：把n+k个东西排成一排，在n+k-1个空格中插入k-1个“隔板”。答案我们总是知道的，就是C(n+k-1,k-1)。它就等于C(n+k-1,n)。它关于n的生成函数是g(x)=1/(1-x)^k。这个生成函数是怎么来的呢？其实，它就是(1-x)的-k次方。把(1-x)^(-k)按照刚才的牛顿二项式展开，我们就得到了x^n的系数恰好是C(n+k-1,n)，因为C(-k,n)*(-x)^n=[(-1)^n*C(n+k-1,n)]*[(-1)^n*x^n]=C(n+k-1,n)x^n。这里看晕了不要紧，后文有另一种方法可以推导出一模一样的公式。事实上，我们有一个纯组合数学的更简单的解释方法。

现在我们引用“组合数学”上超经典的一个例题。很多书上都会有这类题。

我们要从苹果、香蕉、橘子和梨中拿一些水果出来，要求苹果只能拿偶数个，香蕉的个数要是5的倍数，橘子最多拿4个，梨要么不拿，要么只能拿一个。问按这样的要求拿n个水果的方案数。

引用内容

（前两个分别是公比为2和5的几何级数，

第三个嘛，(1+x+x^2+x^3+x^4)*(1-x)不就是1-x^5了吗）

=1/(1-x)^2 （约分，把一大半都约掉了）

（参见刚才对1/(1-x)^k的展开）

于是，拿n个水果有n+1种方法。我们利用生成函数，完全使用代数手段得到了答案！

如果你对1/(1-x)^k的展开还不熟悉，我们这里再介绍一个更加简单和精妙的手段来解释。

是前面说过的。我们对这个式子等号两边同时求导数。于是，。一步就得到了我们所需要的东西！不断地再求导数，我们同样可以得到刚才用复杂的牛顿二项式定理得到的那个结论（自己试试吧）。生成函数还有很多其它的处理手段，比如等式两边同时乘以、除以常数（相当于等式右边每一项乘以、除以常数），等式两边同时乘以、除以一个x（相当于等式右边的系数“移一位”），以及求微分、积分等。神奇的生成函数啊。

我们用两种方法得到了这样一个公式：。这个公式非常有用，是把一个生成函数还原为数列的武器。而且还是核武器！

接下来我们要演示如何使用生成函数求出斐波那契（Fibonacci）数列的通项公式。

斐波那契（Fibonacci）数列是这样一个递推数列：。现在我们需要求出它的生成函数g(x)。g(x)应该是一个这样的函数：

等式两边同时乘以x，我们得到：

就像我们前面说过的一样，这相当于等式右边的所有系数向右移动了一位。

现在我们把前面的式子和后面的式子相加，我们得到：

把这最后一个式子和第一个式子好好对比一下。如果第一个式子的系数往左边移动一位，然后把多余的“1”去掉，就变成了最后一个式子了。由于递推函数的性质，我们神奇地得到了：g(x)+x*g(x)=g(x)/x-1。也就是说，g(x)*x^2+g(x)*x-g(x)=-x。把左边的g(x)提出来，我们有：g(x)(x^2+x-1)=-x。于是，我们得到了g(x)=x/(1-x-x^2)。

我们最后看一个例子。我们介绍硬币兑换问题：我有1分、2分和5分面值的硬币。请问凑出n分钱有多少种方法。想一下刚才的水果，我们不难得到这个问题的生成函数：

现在，我们需要把它变成通项公式。我们的步骤同刚才的步骤完全相同。我我们像刚才一样求出常数满足：

这个解太复杂了，我用Mathematica解了几分钟，打印出了起码几十KB的式子。虽然复杂，但我确实是得到了通项公式。你有兴趣的话可以尝试用Mathematica解决一下1/[(1-x)(1-x^3)] （只有1分和3分的硬币）。解c的值时可以用SolveAlways[]函数。你可以亲眼见到，一个四五行的充满虚数的式子最后总是得到正确的整数答案。

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省

云南省