多元生成函数 | Codeboy's Blog

形式陈述

给定系数族 $(a_{\boldsymbol n})_{\boldsymbol n\in\mathbb N^d}$ ，其多元普通生成函数是形式级数

F(\boldsymbol z) =F(z_1,\ldots,z_d) =\sum_{\boldsymbol n\in\mathbb N^d} a_{\boldsymbol n}\boldsymbol z^{\boldsymbol n}, \qquad \boldsymbol z^{\boldsymbol n}=z_1^{n_1}\cdots z_d^{n_d}.

记号 $[\boldsymbol z^{\boldsymbol n}]F=a_{\boldsymbol n}$ 同时固定全部指标。若变量分别标记可加参数，组合类的不交并仍对应加法，唯一分解且各参数逐项相加仍对应乘法；因此一元符号方法无须另造代数，只需把大小从一个数提升为向量。

当级数在某个多圆盘内绝对收敛时，它成为解析生成函数；Cauchy 公式逐变量应用给出

[\boldsymbol z^{\boldsymbol n}]F =\frac1{(2\pi i)^d} \int_{|z_1|=r_1}\cdots\int_{|z_d|=r_d} \frac{F(\boldsymbol z)} {z_1^{n_1+1}\cdots z_d^{n_d+1}} \,dz_1\cdots dz_d.

这里渐近问题必须连同方向一起说明，例如 $\boldsymbol n=N\boldsymbol r+O(1)$ ；不同的比例向量 $\boldsymbol r$ 可能由不同奇点控制，不能只问“系数在无穷远怎样”。

直觉

一个变量只能给对象贴一把刻度。加入变量相当于保留更多坐标： $x$ 可数水平步， $y$ 可数竖直步， $u$ 可数组件。把某个变量设为 $1$ 会把该参数求和；对它微分后再设为 $1$ ，则能读出总参数量与矩。多元级数因此不是装饰性记号，而是一份不会过早丢失联合信息的账本。

解析上，单变量围道是一条圆，多变量围道则是若干圆的乘积。最优半径向量要在奇异簇附近平衡每个 $z_j^{-n_j}$ ，所以主导对象通常是“给定方向下的极小临界点”，而非一个对所有系数通用的最小模复数。

例子与边界

由向东步 $E$ 与向北步 $N$ 组成的格路是两类原子的任意序列，因此

F(x,y)=\frac1{1-x-y} =\sum_{k\ge0}(x+y)^k.

从 $(0,0)$ 走到 $(m,n)$ 的路径必须在 $m+n$ 个位置中选择 $m$ 个放 $E$ ，于是

[x^my^n]F(x,y)=\binom{m+n}{m}.

沿对角线提取得到

\operatorname{Diag}F(t) =\sum_{n\ge0}[x^ny^n]F\,t^n =\sum_{n\ge0}\binom{2n}{n}t^n =\frac1{\sqrt{1-4t}}.

再由转移定理可得 $[x^ny^n]F\sim4^n/\sqrt{\pi n}$ 。若直接研究方向 $(m,n)$ ，分母 $H=1-x-y$ 上的正临界点满足 $x+y=1$ 与 $x:y=m:n$ ，即

(x_*,y_*)=\left(\frac m{m+n},\frac n{m+n}\right),

它给出的指数因子 $x_*^{-m}y_*^{-n}$ 正好与二项式系数的 Stirling 指数一致。

对角提取绝不等于令 $x=y=t$ 。后者给出 $F(t,t)=1/(1-2t)$ ，其 $t^N$ 系数 $2^N$ 汇总了所有 $m+n=N$ 的路径；对角线只保留 $m=n$ 。类似地，把标记变量设为 $1$ 可能落到收敛域边界之外，形式恒等式与解析代入必须分别检查。

推论与应用

多元生成函数可记录树的顶点数与叶数、图的顶点数与边数、排列的长度与循环数，也能把递推方程转成联合矩和极限定律。对有理函数 $G/H$ ，解析组合学在多个变量中研究奇异簇 $H=0$ 、临界方程、局部几何与 Hessian，从而得到依赖方向的指数、幂次和常数。

边界处可能出现多个同高临界点、奇异簇自交、临界点合并或方向逼近锥边界；此时单个光滑点的高斯近似会失效。系数有符号时还会发生复相位抵消。鞍点法提供局部积分图像，但严格结果仍需证明所选点极小、围道可变形且其他点贡献受控。

参考资料

Robin Pemantle and Mark C. Wilson, Analytic Combinatorics in Several Variables, Cambridge University Press, 2013, Chapters 1–3。
Stephen Melczer, An Invitation to Analytic Combinatorics: From One to Several Variables, Springer, 2021, Chapters 2–5。
Robin Pemantle and Mark C. Wilson, “Asymptotics of Multivariate Sequences, I: Smooth Points of the Singular Variety,” Journal of Combinatorial Theory, Series A 97(1), 2002, pp. 129–161。