知识库 · 文字讲解,AI 整理
生成函数
数列 $a_0,a_1,\dots$ 的(普通)生成函数是
LaTeX
$$A(x)=\sum_{n\ge0}a_nx^n.$$
作为形式幂级数,可以先不管 $x$ 取什么值、级数收不收敛,只对系数做加减乘除。最基本的一个是几何级数
LaTeX
$$\sum_{n\ge0}x^n=\frac1{1-x}.$$
乘法就是卷积
LaTeX
$$[x^n]\,A(x)B(x)=\sum_{k=0}^na_kb_{n-k}.$$
这是离散卷积:两个数列的卷积,对应生成函数的乘积——和连续卷积在频域里变成乘法是同一件事。
求导 $xA'(x)=\sum na_nx^n$ 产生 $n$ 的权重。
概率生成函数
把概率放进系数就是概率生成函数 $G_X(z)=\sum P(X=n)z^n$。独立随机变量之和 $G_{X+Y}=G_XG_Y$——还是因为乘法对应卷积,和组合里「把结构拆成两部分」是同一种代数。求导算矩,见 几何级数。
递推变成方程:Fibonacci
$F_0=0,\ F_1=1,\ F_{n+2}=F_{n+1}+F_n$。设 $F(x)=\sum F_nx^n$,把递推乘上 $x^{n+2}$ 求和:
LaTeX
$$F(x)-x=xF(x)+x^2F(x)\quad\Longrightarrow\quad F(x)=\frac{x}{1-x-x^2}.$$
求系数就把右边做 部分分式:分母的根对应特征方程 $r^2-r-1=0$ 的根,得到 $F_n=(\varphi^n-\psi^n)/\sqrt5$。生成函数和常系数线性递推的特征根法本质上是一回事。
三层,不要混
- 解析的级数:关心收敛域,逐项求导、逐项积分合不合法;
- 形式的生成函数:只关心系数恒等式,用在递推和组合计数上;
- 求和算法:关心一项是不是某个东西的差分,见 望远镜求和。
「形式上能算」和「数值上收敛」是两回事,分开想就不会混。
更多例子:Catalan 数、整数分拆的生成函数、调和数 的生成函数。
用到它的地方
- 知识库 二项式定理与组合恒等式
- 知识库 Catalan 数
- 知识库 几何级数及其求导
- 知识库 调和数与欧拉常数
- 知识库 整数分拆的生成函数
- 知识库 常系数线性微分方程
- 知识库 对级数可以做哪些运算
核对
这一条是文字讲解,由 AI 整理,没有可以数值核对的步骤;作者读过后才公开。