生成函数概述

普通型母函数

指数型母函数

母函数（Generating function）详解

生成函数概述

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

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

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

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

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

普通型母函数

定义：

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

~G(x) = a0 + a1x + a2x*2 + a3x^3 +....+ anx^n

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

例子：

比较典型的是：A(x) = (1+x)^n~C(n,0),C(n,1),C(n,2),C(n,3),.....,C(n,n)

基本运算：

<img src="file:///D:/Personal/Temp/moz-screenshot.jpg" alt=""> 用图片表示

指数型母函数

生成函数是说，构造这么一个多项式函数g(x)，使得x的n次方系数为f(n)。 如：序列{0,1，2，3，4，5...n}的生成函数为：f(x)=0+x+2x^2+3x^3+4x^4+...+nx^n

生成函数最绝妙的是，某些生成函数可以化简为一个很简单的函数。也就是说，不一定每个生成函数都是用一长串多项式来表示的。比如，这个函数f(n)=1 （n当然是属于自然数的），它的生成函数就应该是g(x)=1+x+x^2+x^3+x^4+...（每一项都是一，即使n=0时也有x^0系数为1，所以有常数项）。再仔细一看，这就是一个有无穷多项的等比数列求和嘛。如果-1<x<1，那么g(x)就等于1/(1-x)了。在研究生成函数时，我们都假设级数收敛，因为生成函数的x没有实际意义，我们可以任意取值。于是，我们就说，f(n)=1的生成函数是g(x)=1/(1-x)。

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

考虑这个问题：从二班选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+6x^2+4x^3+x^4。这不就是……二项式展开吗？于是，g(x)=(1+x)^4。

你或许应该知道，(1+x)^k=C(k,0)x^0+C(k,1)x^1+...+C(k,k)x^k；但你或许不知道，即使k为负数和小数的时候，也有类似的结论：(1+x)^k=C(k,0)x^0+C(k,1)x^1+...+C(k,k)x^k+C(k,k+1)x^(k+1)+C(k,k+2)x^(k+2)+...（一直加到无穷；式子看着很别扭，自己写到草稿纸上吧，毕竟这里输入数学式子很麻烦）。其中，广义的组合数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。这里看晕了不要紧，后文有另一种方法可以推导出一模一样的公式。事实上，我们有一个纯组合数学的更简单的解释方法。因为我们刚才的几何级数1+x+x^2+x^3+x^4+...=1/(1-x)，那么(1+x+x^2+x^3+x^4+...)^k就等于1/(1-x)^k。仔细想想k个(1+x+x^2+x^3+x^4+...)相乘是什么意思。(1+x+x^2+x^3+x^4+...)^k的展开式中，n次项的系数就是我们的答案，因为它的这个系数是由原式完全展开后k个指数加起来恰好等于n的项合并起来得到的。

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

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

结合刚才的k个(1+x+x^2+x^3+x^4+...)相乘，我们也可以算出这个问题的生成函数。

引用内容

g(x)=(1+x^2+x^4+...)(1+x^5+x^10+..)(1+x+x^2+x^3+x^4)(1+x)

=[1/(1-x^2)]*[1/(1-x^5)]*[(1-x^5)/(1-x)]*(1+x) （前两个分别是公比为2和5的几何级数，

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

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

=(1-x)^(-2)=C(1,0)+C(2,1)x+C(3,2)x^2+C(4,3)x^3... （参见刚才对1/(1-x)^k的展开）

=1+2x+3x^2+4x^3+5x^4+....

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

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

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

我们用两种方法得到了这样一个公式：1/(1-x)^n=1+C(n,1)x^1+C(n+1,2)x^2+C(n+2,3)x^3+...+C(n+k-1,k)x^k+...。这个公式非常有用，是把一个生成函数还原为数列的武器。而且还是核武器。

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

Fibonacci数列是这样一个递推数列：f(n)=f(n-1)+f(n-2)。现在我们需要求出它的生成函数g(x)。g(x)应该是一个这样的函数：

g(x)=x+x^2+2x^3+3x^4+5x^5+8x^6+13x^7+...

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

x*g(x)=x^2+x^3+2x^4+3x^5+5x^6+8x^7+...

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

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

g(x)+x*g(x)=x+2x^2+3x^3+5x^4+8x^5+...

把这最后一个式子和第一个式子好好对比一下。如果第一个式子的系数往左边移动一位，然后把多余的“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)。

现在的任务是要把x/(1-x-x^2)还原成通项公式。这不是我们刚才的1/(1-x)^n的形式，我们要把它变成这种形式。我们发现，1-x-x^2=[1-(1-√5)x/2]*[1-(1+√5)x/2] （(1-√5)/2和(1+√5)/2是怎么算出来的？显然它们应该是x^2-x-1=0的两个根）。那么x/(1-x-x^2)一定能表示成?/[1-(1-√5)x/2]+?/[1-(1+√5)x/2]的形式（再次抱歉，输入数学公式很麻烦，将就看吧）。这是一定可以的，因为适当的?的取值可以让两个分式通分以后分子加起来恰好为一个x。?取值应该是多少呢？假设前面一个?是c1，后面那个是c2，那么通分以后分子为c1*[1-(1+√5)x/2]+c2*[1-(1-√5)x/2]，它恰好等于x。我们得到这样两个式子：常数项c1+c2=0，以及一次项-c1*(1+√5)/2-c2*(1-√5)/2=1。这两个式子足够我们解出c1和c2的准确值。你就不用解了，我用的Mathematica 5.0。解出来c1=-1/√5，c2=1/√5。你不信的话你去解吧。现在，我们把x/(1-x-x^2)变成了-(1/√5)/[1-(1-√5)x/2] + (1/√5)/[1-(1+√5)x/2]。我们已经知道了1/[1-(1-√5)x/2]的背后是以(1-√5)/2为公比的等比数列，1/[1-(1+√5)x/2]所表示的数列公比为(1+√5)/2。那么，各乘以一个常数，再相加，我们就得到了Fibonacci数列的通项公式：f(n)=-(1/√5)*[(1-√5)/2]^n + (1/√5)*[(1+√5)/2]^n。或许你会问，这么复杂的式子啊，还有根号，Fibonacci数列不都是整数吗？神奇的是，这个充满根号的式子对于任何一个自然数n得到的都是整数。熟悉用特征方程解线性递推方程的同学应该知道，以上过程实质上和找特征根求解没有区别。事实上，用上面所说的方法，我们可以求出任何一个线性齐次递推方程的通项公式。什么叫做线性齐次递推呢？就是这样的递推方程：f(n)等于多少个f(n-1)加上多少个f(n-2)加上多少个f(n-3)等等。Fibonacci数列的递推关系就是线性齐次递推关系。

我们最后看一个例子。我们介绍硬币兑换问题：我有1分、2分和5分面值的硬币。请问凑出n分钱有多少种方法。想一下刚才的水果，我们不难得到这个问题的生成函数：g(x)=(1+x+x^2+x^3+...)(1+x^2+x^4+...)(1+x^5+x^10+..)=1/[(1-x)(1-x^2)(1-x^5)]。现在，我们需要把它变成通项公式。我们的步骤同刚才的步骤完全相同。我们把(1-x)(1-x^2)(1-x^5)展开，得到1-x-x^2+x^3-x^5+x^6+x^7-x^8。我们求出-1+x+x^2-x^3+x^5-x^6-x^7+x^8=0的解，得到了以下8个解：-1,1,1,1,-(-1)^(1/5),(-1)^(2/5),-(-1)^(3/5),(-1)^(4/5)。这个不是我解出来的，我还是用的Mathematica 5.0。不是我不想解，而是我根本不会解这个8次方程。这也是为什么信息学会涉及这些东西的原因：次数稍微一高，只好交给计算机解决了。于是，(1-x)(1-x^2)(1-x^5)=(1+x)(1-x)^3(1+(-1)^(1/5) x)()()() （省略不写了）。注意那个(1-x)^3。由于等根的出现，我们不得不把(1-x)^3所包含的(1-x)和(1-x)^2因子写进一会儿的分母里，不然会导致解不出合适的c来。你可以看到很多虚数。不过没关系，这些虚数同样参与运算，就像刚才的根式一样不会影响到最后结果的有理性。然后，我们像刚才一样求出常数满足1/(1-x)(1-x^2)(1-x^5)=c1/()+c2/(1-x)+c3/(1-x)^2+c4/(1-x)^3...+c8/()。这个解太复杂了，我用Mathematica解了几分钟，打印出了起码几十KB的式子。虽然复杂，但我确实是得到了通项公式。你有兴趣的话可以尝试用Mathematica解决一下1/[(1-x)(1-x^3)] （只有1分和3分的硬币）。解c的值时可以用SolveAlways[]函数。你可以亲眼见到，一个四五行的充满虚数的式子最后总是得到正确的整数答案。

生成函数还有很多东西，例如：Catalan数列啊，指数生成函数啊，之类的。

母函数（Generating function）详解

在数学中，某个序列的母函数是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。使用母函数解决问题的方法称为母函数方法。

母函数可分为很多种，包括普通母函数、指数母函数、L级数、贝尔级数和狄利克雷级数。对每个序列都可以写出以上每个类型的一个母函数。构造母函数的目的一般是为了解决某个特定的问题，因此选用何种母函数视乎序列本身的特性和问题的类型。

这里先给出两句话，不懂的可以等看完这篇文章再回过头来看：“把组合问题的加法法则和幂级数的t的乘幂的相加对应起来”

“母函数的思想很简单—就是把离散数列和幂级数一一对应起来，把离散数列间的相互结合关系对应成为幂级数间的运算关系，最后由幂级数形式来确定离散数列的构造. “

我们首先来看下这个多项式乘法： （以下图片都可以点击放大）由此可以看出:

1.x的系数是a1,a2,…an 的单个组合的全体。

2. x2的系数是a1,a2,…a2的两个组合的全体。

………

n. xn的系数是a1,a2,….an的n个组合的全体（只有1个）。

由此得到：如有图

母函数的定义：

对于序列a0，a1，a2，…构造一函数：

图三

称函数G(x)是序列a0，a1，a2，…的母函数

这里先给出2个例子，等会再结合题目分析：第一种：

有1克、2克、3克、4克的砝码各一 枚，能称出哪几种重量？每种重量各有几种可能方案？

考虑用母函数来解决这个问题：

我们假设x表示砝码，x的指数表示砝码的重量，这样：

1个1克的砝码可以用函数1+x表示，

1个2克的砝码可以用函数1+x∧2表示，

1个3克的砝码可以用函数1+x∧3表示，

1个4克的砝码可以用函数1+x∧4表示，

上面这四个式子懂吗？

我们拿1+x来说，前面已经说过，x表示砝码，x的指数表示砝码的重量！即这里就是一个质量为2的砝码，那么前面的1表示什么？按照上面的理解，1其实应该写为：1*x^0,即1代表重量为2的砝码数量为0个。（理解！）

不知道大家理解没，我们这里结合前面那句话：

“把组合问题的加法法则和幂级数的t的乘幂的相加对应起来“

1+x表示了两种情况：1表示质量为2的砝码取0个的情况，x表示质量为2的砝码取1个的情况。这里说下各项系数的意义：

在x前面的系数a表示相应质量的砝码取a个，而1就表示相应砝码取0个，这里可不能简单的认为相应砝码取0个就该是0*x(想下为何？结合数学式子)。

所以，前面说的那句话的意义大家可以理解了吧？几种砝码的组合可以称重的情况，可以用以上几个函数的乘积表示：

(1+x)(1+x∧2)(1+x∧3)(1+x∧4)

= (1+x+x^2+x^3)(1+x^3+x^4+x^7)

=1+x+x^2+2x^3+2x^4+2x^5+2x^6+2x^7+x^8+x^9+x^10

从上面的函数知道：可称出从1克到10克，系数便是方案数。（！！！经典！！！）

例如右端有2x项，即称出5克的方案有2：5=3+2=4+1；同样，6=1+2+3=4+2；10=1+2+3+4。

故称出6克的方案有2，称出10克的方案有1 。

接着上面，接下来是第二种情况：求用1分、2分、3分的邮票贴出不同数值的方案数：

大家把这种情况和第一种比较有何区别？第一种每种是一个，而这里每种是无限的。

以展开后的x为例，其系数为4，即4拆分成1、2、3之和的拆分数为4；

即 ：4=1+1+1+1=1+1+2=1+3=2+2

这里再引出两个概念整数拆分和拆分数：

所谓整数拆分即把整数分解成若干整数的和（相当于把n个无区别的球放到n个无标志的盒子，盒子允许空，也允许放多于一个球）。

整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。

现在以上面的第二种情况每种种类个数无限为例，给出模板：

// Author: Tanky Woo

// 母函数详解

#include <iostream>

using namespace std;

const int _max = 10001;

// c1是保存各项质量砝码可以组合的数目

// c2是中间量，保存每一次的情况

int c1[_max], c2[_max];

int main()

{ //int n,i,j,k;

int nNum; //

int i, j, k;

while(cin >> nNum)

{

for(i=0; i<=nNum; ++i) // ---- ①

{

c1[i] = 1;

c2[i] = 0;

}

for(i=2; i<=nNum; ++i) // ----- ②

{

for(j=0; j<=nNum; ++j) // ----- ③

for(k=0; k+j<=nNum; k+=i) // ---- ④

{

c2[j+k] += c1[j];

}

for(j=0; j<=nNum; ++j) // ---- ⑤

{

c1[j] = c2[j];

c2[j] = 0;

}

}

cout << c1[nNum] << endl;

}

return 0;

}

我们来解释下上面标志的各个地方：(***********！！！重点！！！***********)

① 、首先对c1初始化，由第一个表达式(1+x+x+..x)初始化，把质量从0到n的所有砝码都初始化为1.

② 、 i从2到n遍历，这里i就是指第i个表达式，上面给出的第二种母函数关系式里，每一个括号括起来的就是一个表达式。

③、j 从0到n遍历，这里j就是(前面i个表达式累乘的表达式)里第j个变量，(这里感谢一下seagg朋友给我指出的错误，大家可以看下留言处的讨论)。如(1+x)(1+x^2)(1+x^3)，j先指示的是1和x的系数，i=2执行完之后变为

（1+x+x^2+x^3）(1+x^3)，这时候j应该指示的是合并后的第一个括号的四个变量的系数。.

④ 、 k表示的是第j个指数，所以k每次增i（因为第i个表达式的增量是i）。

⑤ 、把c2的值赋给c1,而把c2初始化为0，因为c2每次是从一个表达式中开始的