生成函数

引入

对于一个长度无限一个随机数列，我们能不能用一个函数表示这个数列呢？

我们把每一项当做多项式的一个系数，得到了用来表示序列的多项式函数。

详见：函数插值

思考了一会，又找到了它的一种用途。假如数列 $a$ 代表一类物品，中 $a_i$ 表示这类物品中选件物品的方案数

例如： $a=\{1,1,1\}$ 表示 $A$ 类物品中可以选 $0$ 件或 $1$ 件或 $2$ 件，但不能选大于 $2$ 件；又例如无限长数列 $b = \{ 1,0,0,1,0,0,1,0,0, \ldots \}$ 表示 $B$ 类物品只能选 $3$ 的倍数件。这时候，把 $f(x) = 1 + x + {x^2}$ 和 $g(x) = 1 + {x^3} + {x^6} + {x^9}...$ 乘起来，得到另一个函数 $h(x) = 1 + x + {x^2} + {x^3} + {x^4} + \ldots$ 。这个函数有什么意义呢？它的第 $i$ 项的系数就是选 $A$ 、 $B$ 两种物品共 $i$ 件的方案数。

大家可能会好奇：这不就是把两个多项式乘起来么？和一次次枚举情况有什么区别？

这里扯得远一点：多项式可以 FFT（快速傅里叶变换）

我们给这个“用函数表示数列”的东西取了个名字——数列的“生成函数”，表示用这个函数能生成一个数列。

一些疑问

现在有个问题：

$f(x) = \frac{1}{ {1 - x} }$ 是否是 $a = \{ 1,1,1,1,1, \ldots \}$ 的生成函数？

估计大家可能会毅然决然地否定，因为它的生成函数是 $1 + x + {x^2} + {x^3} + \cdots$ 。但如果考虑定义域 $x \in ( - 1,1)$ 呢？

这里大家可以停顿一下想一想

根据我们小学学过的等比数列求和公式：

$1 + x + {x^2} + {x^3} + \cdots$ 的前 $n$ 项和等于 $\frac{1 - {x^n} }{1 - x}$ ，

这是个无限长的数列，

且 $\mathop {\lim }\limits_{n \to \infty} \frac{1 - {x^n} }{1 - x} = {x^n} = 0$ ，这不就相等了嘛！

可是好好的一个函数，被我们蹂躏成这个样子，凭空给限定了定义域，这还是原来那个函数嘛？

注意！生成函数中的 $x$ 是没有意义的。

例如，函数 $1 + {x^2} + {x^4} + {x^6}{\text{ + } } \cdots$ 是不是等于 $\frac{1}{1 - {x^2} }$ ？

提示: t -> x^2

那函数 $1 + 2x + 3{x^2} + 4{x^3} \cdots$ 呢？

对等式 $\frac{1}{ {1 - x} } = 1 + x + {x^2} + {x^3} + \cdots$ 两边分别求导，或者把两个 $1 + x + {x^2} + {x^3} + \cdots$ 乘起来就可以了。

进而考虑推广，

$\frac{1}{ { { {(1 - x)}^k} } } = \sum\limits_i^\infty {C_{i + k - 1}^{k - 1}{x^i} }$

$\frac{1}{(1 - x)^k}$ 就是 $k$ 个 $1 + x + {x^2} + {x^3} + \cdots$ 相乘，那么第 $i$ 项系数就是从 $k$ 个 $1 + x + {x^2} + {x^3} + \cdots$ 中每个选出一项，乘起来恰为 ${x^i}$ 的方案数，就是 $i = {x_1} + {x_2} + ... + {x_k}$ 的非负整数解的组数，用组合数学中的隔板法求，是不是有道理？

Example: Fibbonaci 数列

先说结论：生成函数求斐波那契数列的通项

斐波那契数列的生成函数： $f(x) = x + {x^2} + 2{x^3} + 3{x^4} + 5{x^5} + 8{x^6} + \cdots \text{(i)}$ 乘 $x$ ，得： $x \cdot f(x) = {x^2} + {x^3} + 2{x^4} + 3{x^5} + 5{x^6} + 8{x^7} + \cdots \text{(ii)}$ 用 $\text{i}$ 式减去 $\text{ii}$ 式，得到 $f(x) - x \cdot f(x) = x + {x^3} + {x^4} + 2{x^5} + 3{x^6} + 5{x^7} + \cdots = x + {x^2} \cdot f(x)$ 所以 $f(x) = \frac{x}{1 - x - x^2}$

看着非常难受，把它还原成数列来验证：

首先， $1 - x - {x^2}$ 可以被因式分解为：

$(1 - \frac{ {1 - \sqrt 5 } }{2}x)(1 - \frac{ {1 + \sqrt 5 } }{2}x)$ 所以 $\frac{x}{ {1 - x - {x^2} } } = \frac{x}{ {(1 - \frac{ {1 - \sqrt 5 } }{2}x)(1 - \frac{ {1 + \sqrt 5 } }{2}x)} }$ 裂项 $\frac{x}{ {(1 - \frac{ {1 - \sqrt 5 } }{2}x)(1 - \frac{ {1 + \sqrt 5 } }{2}x)} } = - \frac{1}{ {\sqrt 5 } }\frac{1}{ {(1 - \frac{ {1 - \sqrt 5 } }{2}x)} } + \frac{1}{ {\sqrt 5 } }\frac{1}{ {(1 - \frac{ {1 + \sqrt 5 } }{2}x)} }$