2019-04-28 20:38 已编辑哈尔滨工业大学后端

关注

【博客】小学生都能看懂的生成函数入门教程

前言

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

现在网上讲生成函数的教程大多都是从 $\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!}$ 。内容会比较基础，高端玩家可以直接看鏼爷的集训队论文

生成函数

定义

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

在数学中，某个序列 $(a_n)_{n \in \mathbb{N}}$ 的母函数（又称生成函数，英语：Generating function）是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。

讲的通俗一点，对于某个序列 ${a_0, a_1, \dots, a_n}$ ，我想找一个函数来表示它，假设是 $G(x) = a_0 + a_1x + a_2x^2 \dots a_n x^n$ 。这时候函数第 $i$ 项的**系数**就表示了序列中的第 $i$ 个元素。同时我们也可以看到，函数中的自变量 $x$ 好像并没有什么意义，他的取值并不影响序列的表示，因此我们称这种函数为形式幂级数

用处

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

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

普通生成函数

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

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

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。

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

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

普通生成函数的推广

简单介绍

这个也不能叫推广吧，是我自己瞎起的名字。。。

在我们刚刚的运算中出现了一个常用的函数 $G(x) = \sum_{i=0}^n x^i$ ，这个东西怎么化简呢？

结论： $\sum_{i=0}^{\infty} x^i = \frac{1}{1-x}$

可能你和当初一次见到这个式子的我一样，大概是这个表情

我们来证明一下。

$S = 1 + x + x^2 + \dots x^{\infty}$

$xS = x + x^2 + x^3 + \dots x^{\infty}$

$S - xS = 1$

$S = \frac{1}{1-x}$

是不是证的天衣无缝但是又十分扯淡？因为这玩意儿显然只有 $x^{\infty}$ 收敛也就是 $x\in(-1, 1)$ 时成立。其实在这里只要在 $x\in(-1, 1)$ 成立就可以了，因为生成函数是形式幂级数，我们并不关心 $x$ 的具体取值

有了这个我们能干什么呢？我们可以对 $\frac{1}{1-x}$ 变形来表示更多的序列，同时我们知道了 $\frac{1}{1-x}$ 对应序列的第 $i$ 项的系数为 $1$ ，那么当我们知道了某一个序列的生成函数之后我们也可以把它变成类似于 $\frac{1}{1-x}$ 的形式从而得到通项公式。

首先介绍一些简单的变换，建议大家手玩一下下面的生成函数的推广形式，比如把"乘 $2$ "换成"乘 $k$ "

将 $x$ 替换为 $-x$ ， $\frac{1}{1+x} = {1, -1, 1, -1, \dots}$
将 $x$ 替换为 $2x$ ， $\ \frac{1}{1-2x} = {1, 2, 4, 8, 16, \dots}$
将 $x$ 替换为 $x^2$ , $\ \ \ \frac{1}{1-x^2} = {1, 0, 1, 0, 1 \dots}$
将分子乘 $2$ , $\ \ \ \ \quad\frac{2}{1-x} = {2, 2, 2, 2, 2, \dots}$
将分子乘 $x^3$ , $\ \ \quad \frac{x^3}{1-x} \ = {0, 0, 0, 1, 1, 1, 1 \dots}$
求个导, $\qquad \ \ \ \ \ \frac{1}{(1-x)^2} = {1, 2, 3, 4, 5} \dots$
再求一次， $\quad \ \ \ \frac{2}{(1-x)^3} ={2 + 6 + 12 + 20 \dots}$

问题来了，我如果知道了某一个数列的生成函数，怎么求它的通项公式呢？一般的思路就通过各种奇技淫巧往上面的几个生成函数转化。这里要提一下比较常用的广义二项式定理

$\frac{1}{(1-x)^n} = \sum_{k=0}^{\infty} C_{n+k-1}^{k-1} x^k$

我们来通过两个例子来具体讲一下它的用处

求斐波那契数列通项公式

~~非常不不要脸的~~抄一下自己以前的博客

首先要知道斐波那契数列的递推式

$f_i = f_{i-1} + f_{i - 2}$ $f_0 = f_1 = 1$

那么推导一下

设 $A = 1 + 1x + 2x^2 + 3x^3 + 5x^4 + 8x^5 \dots$

根据递推式，我们可以这样变化，显然有

$\begin{aligned} A = \ 1 + 1x + &2x^2 + 3x^3 + 5x^4 + 8x^5 \dots \\ xA = \ \ \qquad x + &1x^2 + 2x^3 + 3x^4 + 5x^5\dots \\ x^2A =\qquad \qquad &1x^2 + 1x^3 + 2x^4 + 3x^5 \dots \end{aligned}$

那么可以得到一个方程 $A - xA - x^2A = 1$

整理一下 $A =\frac{1}{1-x-x^2}$

这样我们就得到了斐波那契数列的生成函数，然而并没有什么卵用，因为我们不能直接通过观察看出每一项的系数。

现在考虑一下，我们接下来可以干什么。我们已经知道了 $\frac{1}{1-x}$ 和 $\frac{1}{1-kx}$ 所表示的序列。接下来要干的当然是把 $\frac{1}{1-x-x^2}$ 往上面的两个式子转化。

$\frac{1}{1-x-x^2}$ 这玩意儿下半部分是个一元二次方程，我们可以配方

$1-x-x^2 = (1-\phi_1x)(1-\phi_2x)$ $\phi_1 = \frac{1+\sqrt{5}}{2}, \phi_2 = \frac{1-\sqrt{5}}{2}$

(解的时候可以直接把后面的式子拆开，把这两个式子对应项联立组成方程组, $\phi_1 \phi_2$ 的取值是可以反过来的)

这个时候我们发现已经找到与 $\frac{1}{1-kx}$ 的联系了，我们可以把 $\frac{1}{(1-\phi_1 x)(1-\phi_2 x)}$ 拆成求和的形式。可以裂一下项

原式变为 $\frac{a}{1-\phi_1x} + \frac{b}{1-\phi_2 x}$ ，然后再解一个方程 $a(1-\phi_2 x) + b(1-\phi_1x) = 1$

解这个方程就没那么休闲了，这里我们选择把 $x$ 当做主元对方程进行变换

$(a+b - 1) - x(a\phi_2 + b\phi_1) = 0$

这样就好处理了，只要列个二元一次方程组

$\begin{cases} a+b-1 = 0\\ a\phi_2 + b\phi_1 = 0 \end{cases}$

解一下可以得到 $a = \frac{1}{\sqrt{5}} \phi_1, b = -\frac{1}{\sqrt{5}} \phi_2$

带回去

$A = \frac{\phi_1}{\sqrt{5}} \frac{1}{1-\phi_1x} - \frac{\phi_2}{\sqrt{5}} \frac{1}{1-\phi_2x}$

那么第 $n$ 项的公式为

$A_n = \frac{1}{\sqrt{5}} ((\frac{1+\sqrt{5}}{2})^{n+1} - (\frac{1-\sqrt{5}}{2})^{n+1})$

解决组合类问题

比如这种休闲板子题

至多为 $k$ 就是 $\frac{1-x^{k+1}}{1-x}$

$k$ 的倍数就是 $\frac{1}{1-x^k}$

化简完了就只剩下一个 $\frac{1}{(1-x)^5}$

这个东西可以直接广义二项式定理展开，然后交一发pypy2就过了。。

指数生成函数的推广

和上面的很类似，这里直接说结论

$e^x = \sum_{i=0}^{\infty} \frac{x^i}{i!}$

证明考虑直接将 $e^x$ 在 $x_0 = 0$ 处泰勒展开由泰勒展开的公式 $f(x) = f(x_0) + \frac{f^1(x_0)}{1} (x-x_0) + \frac{f^2(x_0)}{2!} (x-x_0)^2 + \dots + \frac{f^n(x0)}{n} (x-x_0)^n \xi$ ( $f^n$ 的意思是求 $n$ 次导数)
可以直接得到。

一些常用变换

$e^{-x} = 1 - \frac{x}{1} + \frac{x}{2!} -\frac{x}{3!} + \frac{x}{4!}\dots$
$\frac{e^x + e^{-x}}{2} = 1 + \frac{x^2}{2!} + \frac{x^4}{4!} + \frac{x^6}{6!}\dots$
$\frac{e^x - e^{-x}}{2} = \frac{x}{1} + \frac{x^3}{3!} + \frac{x^5}{5!} + \frac{x^7}{7!}$
$e^{kx} = 1 + \frac{kx}{1} + \frac{k^2x^2}{2!} + \frac{k^3x^3}{3!} + \frac{k^4x^4}{4!} \dots$