母函数

生成函数即母函数，是组合数学中尤其是计数方面的一个重要理论和工具。生成函数有普通型生成函数和指数型生成函数两种，其中普通型用的比较多。形式上说，普通型生成函数用于解决多重集的组合问题，而指数型母函数用于解决多重集的排列问题。母函数还可以解决递归数列的通项问题（例如使用母函数解决斐波那契数列的通项公式）。

生成函数

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

普通型母函数

母函数就是一列用来展示一串数字的挂衣架。——赫伯特·唯尔夫。
定义：
对于任意数列a0, a1, a2…an即用如下方法与一个函数联系起来：

指数型母函数

序列 的指数型母函数为：

蒙特·卡罗方法

蒙特·卡罗方法（Monte Carlo method），也称统计模拟方法，是二十世纪四十年代中期由于科学技术的发展和电子计算机的发明，而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。是指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。与它对应的是确定性算法。蒙特·卡罗方法在金融工程学，宏观经济学，计算物理学（如粒子输运计算、量子热力学计算、空气动力学计算）等领域应用广泛。

母函数的应用

生成函数的应用简单来说在于研究未知（通项）数列规律，用这种方法在给出递推式的情况下求出数列的通项，生成函数是推导Fibonacci数列的通项公式方法之一，另外组合数学中的Catalan数也可以通过生成函数的方法得到。
生成函数是说，构造这么一个多项式函数g(x)，使得x的n次方系数为f(n)。 如：序列{0,1，2，3，4，5…n}的生成函数为：g(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)。
我们举一个例子说明，一些具有实际意义的组合问题也可以用像这样简单的一个函数全部表示出来。

考虑这个问题：从只有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+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)=43210(-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可以是任意实数。

重点重点重点

接下来我们要演示如何使用生成函数求出Fibonacci数列的通项公式。
Fibonacci数列是这样一个递推数列：f(n)=f(n-1)+f(n-2)。我们需要求出它的生成函数g(x)。
g(x)=x+x^2+2x^3+3x^4+5x^5+8x^6+13x^7+…
等式两边同时乘以x，我们得到：
xg(x)=x^2+x^3+2x^4+3x^5+5x^6+8x^7+…
就像我们前面说过的一样，这相当于等式右边的所有系数向右移动了一位。
我们两式相加，我们得到：
g(x)+xg(x)=x+2x^2+3x^3+5x^4+8x^5+…
把这最后一个式子和第一个式子好好对比一下。如果第一个式子的系数往左边移动一位，然后把多余的“1”去掉，就变成了最后一个式子了。由于递推函数的性质，我们神奇地得到了：g(x)+xg(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)。

自己的理解

母函数可以求数列的通项公式。
普通型的母函数，即生成函数。定义为g(x) = a0 + a1x + a2x^2 + a3x^3 + … + anx^n。

a0, a1, a2, a3, …, an是一个数列的前几项，即0, 1, 2, 3, …, n项，也就是x上面的指数为第几项。
eg：

• 从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。

• Fibonacci数列是这样一个递推数列：f(n)=f(n-1)+f(n-2)。我们需要求出它的生成函数g(x)。g(x)=x+x^2+2x^3+3x^4+5x^5+8x^6+13x^7+…

我们最后看一个例子。我们介绍硬币兑换问题：我有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)。解得(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/()。
生成函数还有很多东西，例如：Catalan数列，指数生成函数等。

经典中的经典，一看就会理解

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

不知道大家理解没，我们这里结合前面那句话：
“把组合问题的加法法则和幂级数的t的乘幂的相加对应起来“
1+x^2表示了两种情况：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个无标志的盒子，盒子允许空，也允许放多于一个球）。
整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。
以上面的第二种情况每种种类个数无限为例， 给出模板：接着上面，接下来是第二种情况：求用1分、2分、3分的邮票贴出不同数值的方案数：
大家把这种情况和第一种比较有何区别？第一种每种是一个，而这里每种是无限的。

以展开后的x为例，其系数为4，即4拆分成1、2、3之和的拆分数为4；
即 ：4=1+1+1+1=1+1+2=1+3=2+2
这里再引出两个概念整数拆分和拆分数：
所谓整数拆分即把整数分解成若干整数的和（相当于把n个无区别的球放到n个无标志的盒子，盒子允许空，也允许放多于一个球）。
整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。
以上面的第二种情况每种种类个数无限为例， 给出模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

//整数拆分模板
#include <iostream>
using namespace std;
const int lmax=10000;
//c1是用来存放展开式的系数的，而c2则是用来计算时保存的，
//他是用下标来控制每一项的位置，比如 c2[3] 就是 x^3 的系数。 
//用c1保存，然后在计算时用c2来保存变化的值。 
int c1[lmax+1],c2[lmax+1];
int main()
{
            int n, i, j, k ;
           // 计算的方法还是模拟手动运算，一个括号一个括号的计算，
           // 从前往后 
           while ( cin>>n )

          {
                     //对于 1+x+x^2+x^3+ 他们所有的系数都是 1 
                     // 而 c2全部被初始化为0是因为以后要用到 c2[i] += x ; 
                     for ( i=0; i<=n; i++ )

                     {
                                c1[i]=1;
                                c2[i]=0;
                     }
                      //第一层循环是一共有 n 个小括号，而刚才已经算过一个了
                      //所以是从2 到 n 
                     for (i=2; i<=n; i++)

                   {
                                 // 第二层循环是把每一个小括号里面的每一项，都要与前一个
                                 //小括号里面的每一项计算。 
                                for ( j=0; j<=n; j++ )
                                 //第三层小括号是要控制每一项里面 X 增加的比例 
                                 // 这就是为什么要用 k+= i ; 
                                         for ( k=0; k+j<=n; k+=i )

                                        {
                                                 // 合并同类项，他们的系数要加在一起，所以是加法，呵呵。 
                                                 // 刚开始看的时候就卡在这里了。 
                                                 c2[ j+k] += c1[ j];
                                         }
                               // 刷新一下数据，继续下一次计算，就是下一个括号里面的每一项。 
                              for ( j=0; j<=n; j++ )

                              {
                                          c1[j] = c2[j] ;
                                          c2[j] = 0 ;
                              }
                   }
                    cout<<c1[n]<<endl;
        }
         return 0;
}
//这句 c2[j+k] += c1[j];的理解还要自己好好的体会体会啊！

母函数的基本代码模板

自己理解：对于（#式） (1+x+x^2+x^3+x^4+x^5+….)(1+x^2+x^4+x^6+x^8+x^10+….)(1+x^3+x^6+x^9+x^12….)…..
第一个for给c1 和 c2 赋值 ， 把上面#式的第一个括号(1+x+x^2+x^3+x^4+x^5+….)的系数给放在c1中，
从而再次计算从 # 的 第二个括号开始 ， 所以 i 就是代表的# 式第几个括号，
而 用程序模拟手工计算 ， 就是 先计算第一个括号 与 第二个括号 计算 ， 把结果放到c2中，
在把结果与第三个括号计算 ， 把结果放到c2中 ， 在和第四个括号计算，……..
所以j 就是指的 已经计算出 的 各项的系数 ，比如第一次之后 1+x+x^2+x^3+x^4+x^5+… ， j=0指向1 ，
j=2 指向x ， …. ， 而 k 就是指 将要计算的那个括号中的项 ， 因为第i个括号 ， 中的指数为0 ， i ， 2i….所以 k要 + i ；
而结果 c2[j+k] += c1[j]; 就是把 以计算出的 j项的系数 和 现在正在计算的括号的k项相乘 ， 所以指数为j+k ， 所以结果放到c2[j+k] 中 ， 这就是这几个for的作用！
最后刷新下结果 ， 下一组数据计算！

c1[n]保存着Xn项前的系数，也就是n个(a1,…,an)组合数