母函数[通俗易懂]

大家好，又见面了，我是全栈君。

在数学中，某个序列的母函数(Generating function，又称生成函数)是一种形式幂级数。其每一项的系数能够提供关于这个序列的信息。使用母函数解决这个问题的方法称为母函数方法。

我们首先来看下这个多项式乘法：

母函数[通俗易懂]

由此能够看出:

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

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

………

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

令a1,a2…an都等于1,由此可得

母函数[通俗易懂]

这里先给出两句话。不懂的能够等看完这篇文章再回过头来看：

1.“把组合问题的加法法则和幂级数的乘幂相应起来”

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

母函数的定义

对于序列a₀。a₁，a₂，…构造一函数：

母函数[通俗易懂]

第一种：

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

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

我们如果x表示砝码。x的指数表示砝码的重量。这样：

1个1克的砝码能够用函数1+1*x^1表示，

1个2克的砝码能够用函数1+1*x^2表示。

1个3克的砝码能够用函数1+1*x^3表示，

1个4克的砝码能够用函数1+1*x^4表示。

上面这四个式子懂吗？

我们拿1+x^2来说，前面已经说过，x表示砝码，x的指数表示砝码的重量！初始状态时，这里就是一个质量为2的砝码。

那么前面的1表示什么？依照上面的理解，1事实上应该写为：1*x^0,即1代表重量为2的砝码没有取。

所以这里1+1*x^2 = 1*x^0 + 1*x^2，即表示2克的砝码有两种状态。不取或取，不取则为1*x^0。取则为1*x^2

接着讨论上面的1+x^2。这里x前面的系数有什么意义？

这里的系数表示状态数(方案数)

1+x^2。也就是1*x^0 + 1*x^2，也就是上面说的不取2克砝码。此时有1种状态；或者取2克砝码，此时也有1种状态。(分析！)

所以，前面说的那句话的意义大家能够理解了吧？

几种砝码的组合能够称重的情况，能够用以上几个函数的乘积表示：

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

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

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

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

。！经典！！。）

比如右端有2^x^5 项，即称出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。即4拆分成1、2、3之和的拆分方案数为4；

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

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

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

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

代码模板：

#include <iostream>  
using namespace std;  
const int _max = 10001;   
// c1是保存各项质量砝码能够组合的数目  
// c2是中间量。保存没一次的情况  
int c1[_max], c2[_max];     
int main()  
{      
    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每次是从一个表达式中開始的。