生成函数

生成函数简介

生成函数（\(\text{generating function}\)），又称母函数，是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。

生成函数有许多不同的种类，但大多可以表示为单一的形式： \[ F(x)=\sum_na_nk_n(x) \] 其中\(k_n(x)\)被称为核函数。不同的核函数会导出不同的生成函数，拥有不同的性质。举个例子：

• 普通生成函数： \(k_n(x)=x^n\)

• 指数生成函数： \(k_n(x)=\frac{x^n}{n!}\)

• 狄利克雷生成函数： \(k_n(x)=\frac1{n^x}\)

另外，对于生成函数\(F(x)\)，我们用\([k_n(x)]F(x)\)来表示它的第\(n\)项的核函数对应的系数，也就是\(a_n\)。

普通生成函数

序列\(a\)的普通生成函数（\(\text{ordinary generating function，OGF}\)）定义为形式幂级数： \[ F(x)=\sum_na_nx^n \] \(a\)既可以是有穷序列，也可以是无穷序列。常见的例子（假设\(a\)以\(0\)为起点）：

• 序列\(a=\langle1,2,3\rangle\)的普通生成函数是\(1+2x+3x^2\)
• 序列\(a=\langle1,1,1,\cdots\rangle\)的普通生成函数是\(\sum_{n\ge0}x^n\)
• 序列\(a=\langle1,2,4,8,16,\cdots\rangle\)的生成函数是\(\sum_{n\ge 0}2^nx^n\)
• 序列\(a=\langle1,3,5,7,9,\cdots\rangle\)的生成函数是\(\sum_{n\ge0}(2n+1)x^n\)

换句话说，如果序列\(a\)有通项公式，那么它的普通生成函数的系数就是通项公式。

基本运算

考虑两个序列\(a,b\)的普通生成函数，分别为\(F(x),G(x)\)。那么有： \[ F(x)\pm G(x)=\sum_n(a_n+b_n)x^n \] 因此\(F(x)\pm G(x)\)是序列\(\langle a_n+b_n\rangle\)的普通生成函数。

考虑乘法运算，也就是卷积： \[ F(x)G(x)=\sum_nx^n\sum_{i=0}^na_ib_{n-i} \] 因此\(F(x)G(x)\)是序列 \[ \langle\sum_{i=0}^na_ib_{n-i}\rangle \] 的普通生成函数。

封闭形式

在运用生成函数的过程中，我们不会一直使用形式幂级数的形式，而会适时地转化为封闭形式以更好地化简。

例如：\(\langle1,1,1,\cdots\rangle\)的普通生成函数\(F(x)=\sum_{n\ge0}x^n\)，我们可以发现： \[ F(x)x+1=F(x) \] 那么解这个方程得到： \[ F(x)=\frac1{1-x} \] 这就是\(\sum_{n\ge0}x^n\)的封闭形式。

证明的话就先鸽着

考虑等比数列\(\langle1,p,p^2,p^3,p^4,\cdots\rangle\)的生成函数\(F(x)=\sum_{n\ge0}p^nx^n\)，有： \[ \begin{align*} F(x)px+1&=F(x) \\F(x)&=\frac1{1-px} \end{align*} \] 等比数列的封闭形式与展开形式是常用的变换手段。

小练习

请求出下列数列的普通生成函数（形式幂级数形式和封闭形式）。难度的循序渐进的。

1. \(a=\langle0,1,1,1,1,\cdots\rangle\)

2. \(a=\langle1,0,1,0,1,\cdots\rangle\)

3. \(a=\langle1,2,3,4,5,\cdots\rangle\)

4. \(a_n=\dbinom{m}{n}\;(m是常数，n\ge0)\)

5. \(a_n=\dbinom{m+n}{n}\)

答案

斐波那契数列的生成函数

接下来我们来推导斐波那契数列的生成函数。

斐波那契数列定义为: \[ a_0=0,a_1=1,a_n=a_{n-1}+a_{n-2}(n>1) \] 设它的普通生成函数是\(F(x)\)，那么根据它的递推式，我们可以类似地列出关于\(F(x)\)的方程： \[ F(x)=xF(x)+x^2F(x)-a_0x+a_1x+a_0 \] 那么解的： \[ F(x)=\frac x{1-x-x^2} \] 接下来的问题是，如何求出他的展开形式？

展开方式一

不妨将\(x+x^2\)当作为一个整体，那么可以得到： \[ \begin{align*} F(x)&=\frac x{1-(x+x^2)} \\&=\sum_{n\ge0}(x+x^2)^n \\&=\sum_{n\ge0}\sum_{i=0}^n\dbinom{n}{i}x^{2i}x^{n-i} \\&=\sum_{n\ge0}\sum_{i=0}^n\dbinom{n}{i}x^{n+i} \\&=\sum_{n\ge0}x^n\sum_{i=0}^n\dbinom{n-i}{i} \end{align*} \] 我们得到了\(a_n\)的通项公式，但那并不是我们熟知的有关黄金分割比的形式。

展开方式二

考虑求解一个待定系数的方程： \[ \frac A{1-ax}+\frac B{1-bx}=\frac x{1-x-x^2} \] 通分得到： \[ \frac {A-Abx+B-aBx}{(1-ax)(1-bx)}=\frac x{1-x-x^2} \] 待定项系数相等，我们得到： \[ \begin{cases} A+B=0\\ -Ab-aB=1\\ a+b=1 ab=-1 \end{cases} \] 解得： \[ \begin{cases} A=\frac1{\sqrt5}\\ B=-\frac1{\sqrt5}\\ a=\frac{1+\sqrt5}2\\ b=\frac{1-\sqrt5}2\\ \end{cases} \] 那么我们根据等比数列的展开式，就可以得到斐波那契数列的通项公式： \[ \frac x{1-x-x^2}=\sum_{n\ge0}x^n\frac 1{\sqrt5}\left(\left(\dfrac{1+\sqrt5}2\right)^n-\left(\dfrac{1-\sqrt5}2\right)^n\right) \] 这也被称为斐波那契数列的另一个封闭形式（\(\frac x{1-x-x^2}\) 是一个封闭形式）。

对于任意多项式 \(P(x), Q(x)\)，生成函数\(\frac{P(X)}{Q(x)}\)的展开式都可以使用上述方法求出。在实际运用的过程中，我们往往先求出\(Q(x)\)的根，把分母表示为\(\prod(1-p_ix)^{d_i}\)的形式，然后再求分子。

鸽~

牛顿二项式定理、卡特兰数的生成函数先鸽一鸽