数列的生成函数

\[ \newcommand{\xfrac}{\displaystyle \frac} \newcommand{\xint}{\displaystyle \int} \newcommand{\xsqrt}{\displaystyle \sqrt} \newcommand{\xsum}{\displaystyle \sum} \newcommand{\xlim}{\displaystyle \lim} \newcommand{\limsup}[1]{\mathop{\overline{\text{lim}}}\limits_{#1}} \newcommand{\liminf}[1]{\mathop{\underline{\text{lim}}}\limits_{#1}} \newcommand{\seq}[1]{\{#1\}} \newcommand{\series}[1][n=1]{\displaystyle \sum_{#1}^{\infty}} \def\d{\mathrm{d}} \def\i{\mathrm{i}} \def\R{\mathbb{R}} \def\Z{\mathbb{Z}} \def\phi{\varphi} \def\Beta{\mathrm{B}} \def\e{\mathrm{e}} \def\N{\mathbb{N}} \def\implies{\Rightarrow} \]

一个数列的母函数或者生成函数(generating function)，指的是将这个数列作为系数，构造出的一个多项式或者幂级数。生成函数在很多方面有应用，包括排列组合计算、解差分方程、计算离散概率等等。

对于一个数列 \(\seq{a_n}_{n=0}^{\infty}\) （这个符号表示数列 \(\seq{a_n}\) 是从 \(n=0\) 开始的无限数列），它的（普通）生成函数被定义为：

\[ G(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n + \cdots ; \]

而有限数列 \(\seq{a_k}_{k=0}^n\) 的生成函数则定义为一个有限项的多项式：

\[ G(x) = a_0 + a_1 x + \cdots + a_n x^n . \]

其他生成函数

除了普通生成函数（幂级数），生成函数还有其他的定义方法，不过最常用的就是普通生成函数。这一节里所有的生成函数都是指普通生成函数。

生成函数的求解

求生成函数

对于一个无限数列 \(\seq{a_n}\) ，求生成函数，就是计算对应级数 \(\xsum_{k=0}^\infty a_n x^n\) 的和函数。

Example

全1数列 \(1, 1, 1, \dots\) 的生成函数为：

\[ G(x) = 1 + x + x^2 + \cdots; \]

这是一个等比级数，容易知道这个级数收敛到 \(1/(1-x)\)，所以我们可以说：

\[ G(x) = \frac{1}{1-x}. \]

通常，计算无限数列对应的幂级数的时候，我们还会借助各种已知的公式，例如常见基本初等函数的Taylor级数，以及广义二项式定理：

\[ (1 + x)^{\alpha} = 1 + \alpha x + \frac{\alpha (\alpha - 1)}{2} x^2 + \cdots \]

对于有限数列，我们则可以直接写出多项式；而对于涉及组合的数列，有时候我们会利用二项式定理等组合公式进行进一步化简。

而如果已知生成函数求对应的级数，则本质上就是求函数在 \(x=0\) 处的Taylor系数，也就是在 \(x=0\) 处做Taylor展开。

Example

数列 \(\seq{a_n}\) 对应的生成函数为 \(G(x) = \xfrac{1}{a - x}\)

生成函数的运算

加法：两个数列之和的生成函数，等于其对应的生成函数之和。

如果我们用 \(\mathscr{G}(a_n)\) 表示数列 \(\seq{a_n}\) 的生成函数，那么有：

\[ \mathscr{G}(a_n + b_n) = \mathscr{G} (a_n) + \mathscr{G} (b_n). \]

乘法：两个数列的卷积的生成函数，等于其对应的生成函数的乘积。

\[ \mathscr{G}(a_n * b_n) = \mathscr{G} (a_n) \mathscr{G} (b_n). \]

利用这个性质，可以将数列的卷积的计算转化为生成函数的乘积。

生成函数的应用

求解差分方程

一些差分方程的求解可以通过生成函数进行。

Example

求递推关系式 \(a_{n + 1} = 2a_n + n\) 的在初值条件 \(a_0 = 1\) 的通项公式。

Solution

构造 \(\seq{a_n}\) 的生成函数 \(G(x) = a_0 + a_1 x + a_2 x^2 + \cdots\) ，则 \(a_{n+1}\) 的生成函数为

\[ a_1 + a_2 x + a_3 x^2 + \cdots = \frac{G(x) - a_0}{x}; \]

而 \(\seq{n}\) 的生成函数为 \(H(x) = x + 2x^2 +3x^3 + \cdots\) ，我们求解它的和函数，得：

\[ \begin{align} H(x) & = x(1 + 2 x + 3 x^2 + \cdots) \\ & = x (x + x^2 + x^3 + \cdots)' \\ & = x \left( \frac{1}{1 - x} \right)' \\ & = \frac{x}{(1-x)^2} \end{align} \]

于是我们得到了：

\[ \frac{G(x) - a_0}{x} = 2 G(x) + \frac{x}{(1-x)^2} \]

解得

\[ G(x) = \frac{1 - 2x + 2x^2}{(1 - x)^2 (1 - 2x)} = -\frac{1}{(1-x)^2} + 2 \frac{1}{1 - 2x}; \]

再利用等比级数的公式展开，可以得到原函数

求解排列组合问题

生成函数可以用于求解某些排列组合问题。

求解概率问题

对于整值（取值非负）随机变量 \(X\) ，我们设它的分布律为 \(P(X=k)=p_k， k \in \Z\) ，则我们可以定义它的母函数为

\[ P(s) = \sum_{k=0}^\infty p_k s^k. \]

也就是，概率分布的母函数指的就是其分布列的母函数。

常见概率分布的母函数

概率分布	分布律	母函数
二项分布\(B(n, p)\)	\(p_k = \mathrm{C}_n^k p^k q^{n-k}, q = 1 - p\)	\(P(s)=(q + ps)^n\)
Poisson分布\(P(\lambda)\)	\(p_k = \xfrac{\lambda^k}{k!} \e^{-\lambda}\)	\(P(s) = \e^{-\lambda(s-1)}\)
几何分布\(G(p)\)	\(p_k = pq^{k-1}\)	\(P(s) = \xfrac{ps}{1-qs}\)
负二项分布\(Nb(r, p)\)	\(p_k = \pmatrix{k-1 \\ r-1} q^{k-r}p^r, q=1-p\)	\(P(s) = \left( \xfrac{ps}{1-qs} \right)^r\)

求数学期望和方差

若 \(X\) 的数学期望存在，则 \(E(X) = \sum_{k=0}^\infty k p_k\) ；对应地，我们对生成函数求导，利用逐项可导的性质有：

\[ P'(s) = \sum_{k=0} k p_k s^{k-1}; \]

代入 \(s = 1\) 容易得到：

\[ P'(1) = E(X). \]

因此，我们可以用母函数来计算随机变量的数学期望。

同样地还有：

\[ D(X) = E(X^2) - E^2(X) = P''(1) + P'(1) - [P'(1)]^2. \]

两个独立随机变量之和

因为母函数可以将卷积转化为乘积，而两个独立随机变量之和正是用卷积定义的，于是我们可以得到一个推论：两个随机变量之和的母函数，等于这两个随机变量的母函数的乘积。

利用这个推论可以计算两个独立随机变量之和，也可以验证随机变量的再生性。

二项分布的可加性（再生性）

二项分布的可加性可以借助母函数来证明。设 \(X \sim B(m, p)\) ， \(Y \sim B(n, p)\) ，且 \(X\) 和 \(Y\) 相互独立，则有 \(P_X(s) = (q + ps)^n\) ， \(P_Y(s) = (q + ps)^m\) ，则显然有：

\[ P_{X + Y}(s) = P_X(s) P_Y(s) = (q + ps)^{m + n}. \]

于是得到 \(X + Y \sim B(m + n, p)\)。

同样地，可以验证Poisson分布、负二项分布的规范性。

*Z变换

与生成函数十分相似，Z变换是针对双边数列的一种变换，十分常见于信号系统。

双边数列和双边级数

一个正、负整数都有取值的数列 \(\seq{a_n}_{n \in \Z}\) 称为双边数列。

双边数列与正常的数列大多数性质一致，只不过取值变为两边。

相应于双边数列，我们还可以定义双边级数：

\[ \sum_{n = - \infty}^{+ \infty} a_n \]

这个级数只需在某点断开，然后看作两个单边级数之和即可，也就是说，这个级数可以定义为：

\[ \begin{align} \sum_{n = - \infty}^{+ \infty} a_n &= \sum_{n = - \infty}^{k - 1} a_n + \sum_{n = k}^{\infty} a_n\\ &= \sum_{m = - k + 1}^{\infty} a_{-m} + \sum_{n = k}^{\infty} a_n \end{align} \]

当以上两个级数 \(\displaystyle \sum_{m = - k + 1}^{\infty} a_{-m}\) 和 \(\displaystyle \sum_{n = k}^{\infty} a_n\) 都收敛时，双边级数 \(\displaystyle \sum_{n = - \infty}^{+ \infty} a_n\) 也收敛。

还可以引入双边级数的Cauchy主值，当双边级数不收敛时，如果

\[ \lim_{N \to \infty} \sum_{n = -N}^N a_n \]

收敛，则称该极限的值为双边级数的Cauchy主值。工程上对于一些不收敛的双边级数，常用Cauchy主值作为它的极限值。

\(z\) 变换

同样地，我们可以将双边数列变换为一个幂级数，只不过这里的级数是双边幂级数，它对应的是某个函数的Laurent级数。

借助工程上常用的定义方法，\(z\)变换定义为：

\[ \mathscr{Z}[x_n] = \series[n=-\infty] x_n z^{-n}. \]

注意这里 \(z\) 的系数为 \(-n\)，这样定义是遵循工程习惯。

一般来说，这里的 \(z\) 视为复数，根据复变函数理论，其收敛域是复平面上一个以原点为圆心的圆环： \(R^- < | z | < R^+\)，该圆环的内径可以为0（此时为圆面，或挖去圆心的圆面），外径可以取无穷大。 \(z\) 变换的许多理论都类似于生成函数，大家可以类比推导，也可以查阅相关资料。

根据Cauchy积分公式，我们还可以导出Z反变换的公式：

\[ \mathscr{Z}^{-1}[X(z)] = \frac{1}{2 \pi \i} \oint_C X(w)(w-z)^{n - 1} \d w \]

求解 \(z\) 反变换可以直接按上述公式计算，也可以先将函数分解为若干个已知的函数再展开。