CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 生成函数理论 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)$。如果不加注明，则此生成函数为普通生成函数。
CVBB ACM Team

用户工具

站点工具

页面工具
