第一次当标题党真是有点不适应

现在网上讲生成函数的教程大多都是从开始，但是我不认为这样有助于大家理解生成函数的本质。我最开始学的时候也是在这里蒙了好久，直到看到了朱全民老师的课件，才真正的理解了生成函数的本质——处理排列组合问题的有利工具，而不是简单的的指标代换。所以这篇文章，我打算从最基本的排列组合问题写起，最后慢慢扩展到。内容会比较基础，高端玩家可以直接看鏼爷的集训队论文

维基百科上是这么定义的：

在数学中，某个序列 的母函数（又称生成函数，英语：Generating function）是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。

讲的通俗一点，对于某个序列，我想找一个函数来表示它，假设是。这时候函数第项的**系数**就表示了序列中的第个元素。同时我们也可以看到，函数中的自变量好像并没有什么意义，他的取值并不影响序列的表示，因此我们称这种函数为形式幂级数

那么这样定义由什么好处呢？

我们仔细观察一下，不难发现这是一个多项式函数，对于多项式我们知道他有加、减、乘、 ~~除,求逆,取ln,exp~~ 等运算。那么我们对进行乘法运算，也就是相当于对序列进行乘法运算，那么这样干有什么意义呢？我们不妨从一个题目入手。

有三种物品，分别有个，问拿出个进行**组合**算一种)的方案数是多少

学过dp的人可能会一眼看出是背包板子题。直接设表示当前到第个位置，已经选了个物品的方案数。转移的时候枚举一下当前选了几个