介绍

生成函数可以解决形如 满足XX条件的方案数共有多少种 的问题,它也能够解决 推导通项公式 等问题,生成函数常常与多项式运算结合在一起。

定义

对于一个无限数列

$$a = \{a_0, a_1, a_2, …\}$$

它的生成函数为

$$f(x) = a_0 + a_1x + a_2x^2 + … = \sum\limits_{i=0}^{\infty}a_ix^i$$

其中 $x$ 的值并没有意义。

• 有限数列 $\{a_0, a_1, a_2, …, a_n\}$ 的生成函数就是 $f(x) = a_0 + a_1x + a_2x^2 + … + a_nx^n = \sum\limits_{i=0}^{n}a_ix^i$

• 我们定义 $[x^{k}]f(x)$ 为 $f(x)$ 表达式中,$x^k$ 的系数。(为了方便表达,有的时候也会使用 $a_k, b_k$)

封闭形式与展开形式

生成函数有 封闭形式展开形式 两种形态。

封闭形式适合进行生成函数之间的运算展开形式则可以得到生成函数各项的系数(通项公式),从而获得最终的答案(方案数的统计)。

例如,对于无限数列

$$\{1,1,1,1,…\}$$

它的生成函数展开形式为:

$$f(x) = 1+x+x^2+x^3+…$$

很明显这是一个等比数列,公比为 $x$,进行求和可以得到封闭形式:

$$f(x) = 1+x+x^2+x^3+… = \frac{1}{1-x}$$

一些常见的封闭式与展开式的对应

封闭形式 展开形式 数列
$\frac{1}{1-x}$ $\sum\limits_{i=0}^{\infty}x^i = 1+x+x^2+x^3+…$ $\{1,1,1,1,…\}$
$\frac{1}{(1-x)^2}$ $\sum\limits_{i=0}^{\infty}(i+1)x^i = 1+2x+3x^2+4x^3+…$ $\{1,2,3,4,…\}$
$\frac{1}{1-ax}$ $\sum\limits_{i=0}^{\infty}a^ix^i = 1+ax+a^2x^2+a^3x^3+…$ $\{1,a,a^2,a^3,…\}$
$\frac{1}{(1-ax)^n}$ $\sum\limits_{i=0}^{\infty}C_{(n-1)+i}^{(n-1)}a^ix^i$ $\{1, C_{n}^{1}a^1, C_{n+1}^{2}a^2,C_{n+2}^{3}a^3,…\}$
$\frac{1}{1+x}$ $\sum\limits_{i=0}^{\infty}(-1)^ix^i = 1-x+x^2-x^3+…$ $\{1,-1,1,-1,…\}$

证明

证明1

$$\frac{1}{1-x} = 1+x+x^2+x^3+…$$

证:等比数列,公比为 $x$。

证明2

$$\frac{1}{(1-x)^2} = 1+2x+3x^2+4x^3+…$$

证:因为

$$\frac{1}{(1-x)^2} = (\frac{1}{1-x})^2 = (1+x+x^2+x^3+…)^2$$

根据组合意义,对于 $x^k$,有 $(0,k),(1,k-1),…,(k,0)$ 共 $(k+1)$ 种组合方式,并且每一种的系数为 $1$,所以 $x^k$ 的系数为 $(k+1)$。

证明3

$$\frac{1}{1-ax} = 1+ax+a^2x^2+a^3x^3+…$$

证:等比数列,公比为 $ax$。

证明4

$$\frac{1}{(1-ax)^n} = \sum\limits_{i=0}^{\infty}C_{(n-1)+i}^{(n-1)}a^ix^i$$

证:因为

$$\frac{1}{(1-ax)^n} = (1+ax+a^2x^2+a^3x^3+…)^n$$

根据组合意义,对于 $x^k$ 而言,每个 $(1+ax+a^2x^2+a^3x^3+…)$ 都可以贡献给 $k$,而这样的式子有 $n$ 个。

所以相当于:

求 $a_1+a_2+…+a_n = k$ 的非负整数解的个数。

这是 小球放盒子 模型,$k$ 个球放入 $n$ 个盒子并且允许空盒,用隔板法即可,方案数为 $C_{(n-1)+k}^{(n-1)}$,这就是 $a^kx^k$ 的系数。

证明5

$$\frac{1}{1+x} = 1-x+x^2-x^3+…$$

等比数列,公比为 $-x$。

计算例子

例1

题意

求无限数列 $a_i = i^2$ 的生成函数。

分别求出展开式和封闭式。

展开式 $\Rightarrow$ 封闭式

数列 $a$ 为:

$$a = \{0,1,4,9,16,…\}$$

那么生成函数的展开式为:

$$f(x) = x + 4x^2 + 9x^3 + 16x^4 + … = \sum\limits_{i=1}^{\infty}i^2x^i$$

在推导生成函数的封闭式时,一个非常重要的 trick 是给展开式 乘上一个 $x$

那么乘上 $x$ 以后,相当于整个展开式向右移动了一位,对应的生成函数就是

$$xf(x) = 0 + x^2 + 4x^3 + 9x^4 + … = \sum\limits_{i=1}^{\infty}(i-1)^2x^i$$

所以两者相减,可得:

$$(1-x)f(x) = \sum\limits_{i=1}^{\infty}(i^2 - (i-1)^2)x^i = \sum\limits_{i=1}^{\infty}(2i-1)x^i$$

$$=2\sum\limits_{i=1}^{\infty}ix^i - \sum\limits_{i=1}^{\infty}x^i$$

$$=\frac{2x}{(1-x)^2} - \frac{x}{1-x}$$

• 注意到因为求和是从 $i=1$ 开始的,相当于 $i=0$ 的情况整体右移了一位,所以要乘上 $x$ 得到 $\frac{2x}{(1-x)^2}$

所以生成函数 $f(x)$ 的封闭式为:

$$f(x) = \frac{2x}{(1-x)^3} - \frac{x}{(1-x)^2} = \frac{x(x+1)}{(1-x)^3}$$

封闭式 $\Rightarrow$ 展开式

已知 $f(x)$ 的封闭式为

$$f(x) = \frac{x(x+1)}{(1-x)^3}$$

我们将其化简为上面 常用表 里面的组合,也就是 裂项

$$f(x) = \frac{x(x+1)}{(1-x)^3} = \frac{2x}{(1-x)^3} - \frac{x}{(1-x)^2}$$

考虑第 $k$ 项的系数,注意到我们可以将分子中的 $x$ 提出来,所以 $f(x)$ 的第 $k$ 项系数 $a_k$ 就等于 $g(x) = (\frac{2}{(1-x)^3} - \frac{1}{(1-x)^2})$ 的第 $(k-1)$ 项系数 $b_{k-1}$。

$$\frac{2}{(1-x)^3} = 2\sum\limits_{i=0}^{\infty}C_{2+i}^{2}x^i, ~ \frac{x}{(1-x)^2} = \sum\limits_{i=0}^{\infty}(i+1)x^i$$

所以 $g(x)$ 的第 $(k-1)$ 项系数为:

$$b_{k-1} = [x^{k-1}]2(\sum\limits_{i=0}^{\infty}C_{2+i}^{2}x^i) - \sum\limits_{i=0}^{\infty}(i+1)x^i = 2C_{k+1}^2 - k = k^2$$

所以 $f(x)$ 的第 $k$ 项系数为 $a_k = b_{k-1} = k^2$。

于是生成函数的展开式为:

$$f(x) = \sum\limits_{i=0}^{\infty}i^2x^i = x + 4x^2 + 9x^3 + 16x^4 + …$$

例2

题意

求斐波那契数列 $$f_0 = 0, f_1 = 1, f_i = f_{i-1} + f_{i-2}$$

的生成函数,分别求出展开式(通项公式)和封闭式。

封闭式

注意到

$$f(x) = f_0 + f_1x^1 + f_2x^2 + f_3x^3 + …$$

$$xf(x) = 0 + f_0x^1 + f_1x^2 + f_2x^3 + …$$

$$x^2f(x) = 0 + 0+ f_0x^2 + f_1x^3 + …$$

由于 $f_i = f_{i-1} + f_{i-2}$,所以:

$$f(x)(1-x-x^2) = f_0 + (f_1-f_0)x^1 = x$$

所以 $$f(x) = \frac{x}{1-x-x^2}$$

封闭式$\Rightarrow$展开式

$$f(x) = \frac{x}{1-x-x^2}$$

我们希望将它转为表格中存在的形式,所以我们设:

$$(1-ax)(1-bx) = 1-x-x^2$$

可得 $a = \frac{1 + \sqrt 5}{2}, b = \frac{1 - \sqrt 5}{2}$

$$g(x) = \frac{f(x)}{x} = \frac{1}{(1-ax)(1-bx)}$$

那么要求 $f(x)$ 的第 $n$ 项系数,只要求 $g(x)$ 的第 $(n-1)$ 项系数即可。

因为

$$g(x) = \frac{1}{(1-ax)(1-bx)}$$ $$= \sum\limits_{i=0}^{\infty}a^ix^i * \sum\limits_{j=0}^{\infty}b^jx^j$$ $$= (1+ax+a^2x^2+a^3x^3+…) * (1+bx+b^2x^2+b^3x^3+…)$$

这是个卷积,那么 $g(x)$ 的第 $(n-1)$ 项系数为:

$$[x^{n-1}]g(x) = \sum\limits_{k=0}^{n-1}a^{k}b^{n-1-k}$$

$$=b^{n-1}\sum\limits_{k=0}^{n-1}a^{k}b^{-k}$$

$$=b^{n-1}\sum\limits_{k=0}^{n-1}(\frac{a}{b})^k$$

右边就是个等比数列求和了,公比为 $\frac{a}{b}$,最后可得

$$[x^n]f(x) = [x^{n-1}]g(x) = \frac{1}{\sqrt 5}((\frac{1+\sqrt 5}{2})^n - (\frac{1-\sqrt 5}{2})^n)$$

那么求出了 $f(x)$ 的通项公式,展开式也就可以写出来了。

参考链接

  1. https://blog.csdn.net/a_forever_dream/article/details/102594411