生成函数

引入

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

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

详见：函数插值

思考了一会，又找到了它的一种用途。假如数列 \(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)} } \]

这就是斐波那契数列通项公式了

这种方法也可以应用到各种线性齐次递推中