都能看懂的生成函数入门教程

来源：珠海童程童美少儿编程培训学院时间：2022/12/31 17:05:17

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

　　普通生成函数

　　有三种物品，分别有\(3, 2, 3\)个，问拿出\(4\)个进行组合\((\{1123\}, \{3211\}\)算一种)的方案数是多少

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

　　f[0][0] = 1;

　　for(int i = 1; i <= 3; i++)

　　for(int j = 0; j <= 8; j++) //当前总共要选出j个

　　for(int k = 0; k <= j; k++) //已经选了k个

　　if(j - k <= v[i]) //此时要选j-k个

　　f[i][j] += f[i - 1][k];

　　可以得到\(f[3]\)的系数为\(\{1\ 3\ 6\ 9\ 10\ 9\ 6\ 3\ 1 \}\)(从0开始编号)，\(4\)较对应的一项是\(10\)。

　　那用生成函数怎么做呢?

　　我们可以对每个物品构造一个多项式函数，其中第\(i\)项的系数\(a_i\)表示选了\(i\)个当前物品的方案数。

　　那么个物品的生成函数为\(G_1(x) = 1 + x^1 + x^2 + x^3\) (相同的物品选\(i\)个的方案数当然是1)

　　第二个物品的生成函数为\(G_2(x) = 1 + x^1 + x^2\)

　　第三个为\(G_3(x) = 1 + x^1 + x^2 + x^3\)

　　先说结论：较终答案是\(G_1(x) * G_2(x) * G_3(x)\)的第\(4\)项的系数

　　这是为什么呢?考虑两个多项式相乘的结果\(f* g\)，它的第\(k\)项的系数为\(\sum_{i=0}^k f_i g_{k-i}\)。这个过程是相当于是在枚举个物品选了几个，比如\(4\)这一项，他等于\(f_0g_4 + f_1g_3 + f_2 g_2 + f_3g_1 + f_4g_0\)。

　　再具体一点，抛开刚刚那个题目中系数等于\(1\)的限制，我们假设\(f_1 = 2, g_3 = 3\)，也就是说从个物品中选出\(1\)个有两种方案，第二个物品中选出\(3\)个有三种方案，那么\(f_1 * g_3=2 * 3\)就相当于个物品的两种方案可以与第二个物品的三种方案任意组合来得到\(4\)种物品。(再看不懂的话建议去补一下高中组合计数qwq，这里讲的这么详细是为了给指数生成函数做铺垫)

　　这里建议大家去手玩一下多项式乘法，玩一下(玩的时候枚举\(x^i\)算他的系数)就会发现这个过程与背包的过程惊人的相似，因为事实上背包的过程就是在模拟多项式乘法。

　　这里为了下文(指数型生成函数)好讲解，本菜鸡直接把多项式相乘的结果(抄一下)写出来

　　\[\begin{aligned} G(x) &= (1+x+x^2+x^3)(1+x+x^2)(1+x+x^2+x^3) \\ &= (1+2x+3x^2+3x^3+2x^4+x^5)(1+x+x^2+x^3)\\ &=1+3x+6x^2+9x^3+10x^4+9x^5+6x^6+3x^7+x^8 \end{aligned} \]

　　其中\(x^4\)项可以由下面这些得到，这种形式与我们的手玩结果就非常相似了

　　\[x_1x_3^3+x_2x_3^3+x_1^2x_3^2+x_1x_2x_3^2+x_2^2x_3^2+x_1^3x_3+x_1^2x_2x_3+x_1x_2^2x_3+x_1^3x_3+x_1^2x_2^2 \]

　　形如\(G(x) = \sum_{i=0}^n a_ix_i\)的表示一个序列的多项式函数，我们称之为普通生成函数

　　讲到这里你需要大概明白：生成函数的基本概念，生成函数相乘的组合意义。

　　接下来按道理应该讲\(\frac{1}{1-x}\)及其运算，但是我想先介绍一下指数生成函数的基本概念。

　　指数生成函数

　　通过刚刚的讲解我们不难看出，普通生成函数的意义在于解决组合类计数问题。但是别忘了组合的兄弟排列呀。指数生成函数就是用来解决排列类问题。

　　还是刚刚的题目，我们改一下限制

　　有三种物品，分别有\(3, 2, 3\)个，问拿出\(4\)个进行排列\((\{1123\}, \{3211\}\)算不同方案)的方案数是多少( HDU1521)

　　这一类问题仅仅是比刚刚多了一个顺序的原因，但是难度却比刚刚大了不少(背包也可以做，只要在转移的时候乘一个组合数即可，留给大家思考)

　　这里先介绍一下多重集排列数

　　设\(S = \{a_1, a_2 \dots a_n\}, N = \sum_{i=1}^n a_i\)，其中第\(a_i\)表示第\(i\)个物品有\(a_i\)个。

　　从中选出\(N\)个进行排列的方案数为\(\frac{N!}{a_1!a_2! \dots a_n!}\)

　　解释的话就是相当于任意排列之后减去同种物品之间多出来的方案

　　这样我们就得到了一个思路：先把所有组合得到的方案算出来，然后再对每一种方案分别计算排列数，较后加起来。

　　比如我们刚刚已经得到了组合的方案：

　　\[x_1x_3^3+x_2x_3^3+x_1^2x_3^2+x_1x_2x_3^2+x_2^2x_3^2+x_1^3x_3+x_1^2x_2x_3+x_1x_2^2x_3+x_1^3x_3+x_1^2x_2^2 \]

　　其中\(x_1 x_3^3\)这一项的排列方案就是\(\frac{4!}{1!3!}\)，\(x_1x_2x_3^2\)这一项的排列方案就是\(\frac{4!}{1!1!2!}\)。观察一下，所有方案的分子都是\(4!\)，分母都是选出来的对应数量的阶乘。

　　于是我们引进指数型生成函数

　　形如\(G(x) = \sum_{i=0}^n a_i \frac{x_i}{i!}\)的表示序列的多项式函数，我们称之为指数生成函数。

　　同时我们分别构造出\(G_1(x) = 1+\frac{x^1}{1} + \frac{x^2}{2!} + \frac{x^3}{3!}\)

　　\(G_2(x) = 1 + \frac{x^1}{1} + \frac{x^2}{2}\)

　　\(G_3(x) = 1 + \frac{x^1}{1} + \frac{x^2}{2!} + \frac{x^3}{3!}\)

　　这时候再计算一下\(G_1(x) * G_2(x) * G_3(x)\)

　　\[\begin{aligned} G_e(x) &= (1 + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!})(1+\frac{x}{1!} + \frac{x^2}{2!}) (1 + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!})\\ &= (1+2x+2x^2+\frac{7}{6}x^3 + \frac{5}{12}x^4 + \frac{1}{12}x^5) (1+x+\frac{1}{2}x^2 + \frac{1}{6}x^3)\\ &=(1+3x + \frac{9}{2}x^2 + \frac{14}{3}x^3 + \frac{35}{12}x^4 + \frac{17}{12}x^5 + \frac{35}{72} x^6 + \frac{8}{72}x^7 + \frac{1}{71}x^8) \end{aligned} \]

　　这时候如何计算选出\(4\)个物品的答案呢?简单\(\frac{35}{12} * 4! = 70\)

　　可能大家不禁思考，为什么这么定义函数乘起来就是排列数呢?想一想，因为我们对每个系数构造的\(\frac{1}{i!}\)就相当于是多重集排列数中的分母呀

　　好了，如果你到这里都看懂了的话，说明你已经对生成函数有个大概的了解了。但是不知道大家是不是和我有着同样的感觉：生成函数好麻烦啊qwq。

　　那么有没有一套可以简化些运算的理论呢?

　　答案是：当然有了!(不然我问个毛线)。下面讲的内容可以会有些刺激，需要大家有一定的数学基础(其实只要高中知识就行了)

尊重原创文章，转载请注明出处与链接：http://www.peixun360.com/970/news/588651/违者必究！ 以上就是珠海童程童美少儿编程培训学院 小编为您整理 都能看懂的生成函数入门教程的全部内容。