生成函数理论 1

基本定义

定义 1 数列 $\{a_n\}_{n=0}^{\infty}$ 的 普通生成函数 是下面的形式级数: $$ f(x)=\sum_{n=0}^{\infty}a_nx^n. $$ ​ 定义 2 数列 $\{a_n\}_{n=0}^{\infty}$ 的 指数型生成函数 是下面的形式级数: $$ f(x)=\sum_{n=0}^{\infty}\frac{a_n}{n!}x^n. $$ ​ 定义 3 数列 $\{a_n\}_{n=1}^{\infty}$ 的 Dirichlet 生成函数 是下面的形式级数: $$ f(s)=\sum_{n=1}^{\infty}\frac{a_n}{n^s}. $$ ​ 例 4 数列 $\{1\}_{n=0}^{\infty}$ 的普通生成函数是 $$ \sum_{n=0}^{\infty}x^n=\frac{1}{1-x}. $$ 同一个数列 $\{1\}_{n=0}^{\infty}$ 的指数型生成函数是 $$ \sum_{n=0}^{\infty}\frac{x^n}{n!}=e^x. $$ 而数列 $\{1\}_{n=0}^{\infty}$ 的 Dirichlet 生成函数则是 $$ \sum_{n=1}^{\infty}\frac{1}{n^s}:=\zeta(s). $$ 这个函数就是著名的 Riemann-Zeta 函数.

注 5 上面几个公式中的 “=” 的意义是 “形式收敛”。从解析上讲,若级数 $A$ 与另一级数 $B$ 分别在某个区间上收敛到同一形式,则 $A$ 和 $B$ 必定是同一级数,从而可以通过级数 $B$ 的表达形式来找到 $A$。因此,我们一般无须考虑这些生成函数在何处收敛。而利用收敛到的闭形式(即和函数)的最终目的之一也是导出原始级数比较简单的表达形式,例如 $$ \ln(1+x)=\sum_{n=1}^{\infty}\frac{(-1)^n}{n}x^n. $$ ​ 注 6 可以定义形式级数上的运算。下面以普通生成函数为例加以说明。若形式级数的系数在域 $F$ 中,也称其为域 $F$ 上的形式级数。域 $F$ 上的所有形式级数组成的集合记为 $F[[x]]$。对于形式级数 $f(x)=\sum_{n=0}^{\infty}a_nx^n,g(x)=\sum_{n=0}^{\infty}b_nx^n\in F[[x]]$,定义 $$ f(x)+g(x)=\sum_{n=0}^{\infty}(a_n+b_n)x^n $$ 和 $$ f(x)g(x)=\sum_{n=0}^{\infty}c_nx^n, $$ 其中 $c_n=\sum_{k=0}^{\infty}a_kb_{n-k}(n\ge 0)$。容易证明 $F[[x]]$ 在这样的加法和乘法下构成一个环。进一步,对于 $f(x)=\sum_{n=0}^{\infty}a_nx^n$,定义 $$ f'(x)=\sum_{n=1}^{\infty}na_nx^{n-1}=\sum_{n=0}^{\infty}(n+1)a_{n+1}x^n $$ 为 $f(x)$ 的 形式微商形式导数

​ 如果生成函数是有限项的级数,它对应的就是一个有限项的数列(或者说自某一项以后全部为零的数列),这时形式级数就是一个多项式。

定义 7 若形式级数 $f(x)=\sum_{n=0}^{\infty}a_nx^n$ 是多项式,或形式级数 $g(x)=\sum_{n=0}^{\infty}b_nx^n$ 满足 $b_0=0$,则可以定义 $f(x)$ 与 $g(x)$ 的 复合 $$ f(g(x))=\sum_{n=0}^{\infty}a_n(g(x))^n. $$ 当相关的复合存在,且 $f(g(x))=g(f(x))=x$ 时,则称 $g(x)$ 为 $f(x)$ 的 复合逆

​ 有时候,用 $[x^n]f(x)$ 表示 $f(x)$ 中 $x^n$ 的系数,用 $\{a_n\}_{n=0}^{\infty}\leftrightarrow f(x)$ 表示数列 $\{a_n\}^{\infty}_{n=0}$ 的生成函数是 $f(x)$。如果不加注明,则此生成函数为普通生成函数。