2026-08-03 · 从递归结构到显式系数

0. 导读与元结构 (Orientation & Meta-structure)

起点问题。 前一期从已知序列 $(a_n)$ 出发，把它编码为普通生成函数 $A(z)=\sum _{n\ge 0}{a}_n{z}^n$；常系数线性递推因此变成有理函数方程。但许多组合对象并不是先给出递推再计数，而是由自身递归生成：一棵树由一个根和若干棵更小的树组成。此时怎样把“对象的递归定义”稳定地翻译成“生成函数的隐式方程”，又怎样在不先解出方程的情况下直接抽取系数？

今天的对象与量词分成五层：

1. 对象层： 对每个 $n\ge 0$，有一个有限集合 ${\mathcal{A}}_n$，其元素是大小为 $n$ 的组合对象；
2. 规格层： 用不交并、笛卡尔积与有序序列等 constructors（构造子）描述对象如何由小对象组成；
3. 形式层： 以 $A(z)=\sum _{n\ge 0}|{\mathcal{A}}_n|z^n$ 编码计数，不先要求 $z$ 取数值；
4. 反演层： 对满足 $T(z)=z\varphi (T(z))$ 的形式幂级数，用 Lagrange--Bürmann inversion（Lagrange--Bürmann 反演）直接求 $[z^n]T(z{)}^k$；
5. 解析层： 留到弧线第 3 日，再由隐式方程的临界点和奇点解释系数增长。

先修只需普通生成函数、形式幂级数乘法、二项式展开与复合函数求导。主导 proof engines 是：unique decomposition（唯一分解）、coefficientwise recursion（逐系数递归）、formal residue（形式留数）、compositional inversion（复合反演）和 coefficient extraction（系数抽取）。

本期是 exploration-2026-w31-enumerative-machines 的 Day 2/3，属于有意深化：Day 1 建立“序列到级数”的机器；今天加入“组合规格到隐式方程，再到显式系数”的机器；Day 3 将从 Catalan 生成函数的平方根奇点进入 analytic combinatorics（解析组合）。

1. 核心概念、定理与谱系 (Concept, Theorem & Lineage)

1.1 符号方法：构造子必须忠实记录对象类型

定义（locally finite combinatorial class，局部有限组合类）。 一个带大小函数的组合类是一个不交并

$$\mathcal{A}=\underset{n\ge 0}{⨆}{\mathcal{A}}_n,$$

其中

$$\mathrm{\forall }n\in {\mathbb{N}}_0,0\le |{\mathcal{A}}_n|<\mathrm{\infty }.$$

其 ordinary generating function（普通生成函数）定义为

$$A(z)=\sum _{n\ge 0}|{\mathcal{A}}_n|z^n\in \mathbb{Z}[[z]].$$

设 $\mathcal{A},\mathcal{B}$ 均局部有限，并且每个对象的大小是其原子数。三个基本迁移规则是：

1. 若 $\mathcal{C}=\mathcal{A}\bigsqcup \mathcal{B}$ 是不交并，则 $C(z)=A(z)+B(z)$；
2. 若 $\mathcal{C}=\mathcal{A}\times \mathcal{B}$，且大小相加，则
   $$C(z)=A(z)B(z),$$
   因为大小为 $n$ 的对象按 $n=i+(n-i)$ 唯一分解，系数正是卷积；
3. 若 ${\mathcal{A}}_0=\varnothing$，令
   $$\mathrm{SEQ}(\mathcal{A})=\underset{r\ge 0}{⨆}{\mathcal{A}}^r,$$
   则
   $$\mathrm{SEQ}(A)(z)=1+A(z)+A(z{)}^2+\cdots =\frac{1}{1-A(z)}.$$

第三条中的 ${\mathcal{A}}_0=\varnothing$ 不是装饰：若存在零大小对象，则固定总大小可以插入任意多个零大小分量，局部有限性可能立即失效。

1.2 平面有根树给出一个非线性函数方程

定义（plane rooted tree，平面有根树；亦称 ordered rooted tree，有序有根树）。 它是一棵指定根的有限树，并且对每个顶点 $v$，从 $v$ 向下连接的子树组成一个有限有序列。大小 $|\tau |$ 定义为顶点数。

记 $\mathcal{T}$ 为所有非空平面有根树的类，$\mathcal{Z}$ 为只含一个大小为 $1$ 的原子对象的类。每棵树都能且只能写成“一个根 + 一列有序根子树”，所以有组合规格

$$\mathcal{T}=\mathcal{Z}\times \mathrm{SEQ}(\mathcal{T}).$$

这里“有序”正由 $\mathrm{SEQ}$ 保存。转到普通生成函数，得到

$$T(z)=\frac{z}{1-T(z)}.$$

等价地，

$$T(z)=z\varphi (T(z)),\varphi (u)=\frac{1}{1-u}.$$

这已经比一串初始计数更有结构：树的递归分解、函数方程和系数之间有一条可逆的推理链。

先说明形式解为何存在且唯一。更一般地，设 $K$ 是域，$\varphi (u)\in K[[u]]$ 且 $\varphi (0)\ne 0$。若写

$$T(z)=\sum _{n\ge 1}{t}_n{z}^n,$$

则方程 $T=z\varphi (T)$ 的 $z^n$ 系数满足

$$t_n=[z^{n-1}]\varphi (T(z)).$$

右边只依赖 $t_1,\dots ,t_{n-1}$；从 $t_1=\varphi (0)$ 开始，所有系数依次被唯一决定。因此：

$$\mathrm{\exists }!T(z)\in zK[[z]]\text{使得}T(z)=z\varphi (T(z)).$$

1.3 Lagrange--Bürmann 反演：从隐式方程直接读系数

定理（formal Lagrange--Bürmann inversion，形式 Lagrange--Bürmann 反演）。 设 $K$ 是特征为 $0$ 的域，$\varphi (u)\in K[[u]]$ 且 $\varphi (0)\ne 0$；令唯一的 $T(z)\in zK[[z]]$ 满足

$$T(z)=z\varphi (T(z)).$$

则对每个 $H(u)\in K[[u]]$ 与每个整数 $n\ge 1$，都有

$$[z^n]H(T(z))=\frac{1}{n}[u^{n-1}]H^{\prime }(u)\varphi (u{)}^n.$$

特别地，对所有整数 $n\ge 1$ 及 $1\le k\le n$，取 $H(u)=u^k$ 得

$$[z^n]T(z{)}^k=\frac{k}{n}[u^{n-k}]\varphi (u{)}^n.$$

特征为 $0$ 保证可以除以 $n$；条件 $\varphi (0)\ne 0$ 则保证 $z=u/\varphi (u)$ 在原点有非零线性项，因而存在形式复合逆。

证明架构（形式留数版）。 对 Laurent series（Laurent 级数）定义

$${\mathrm{Res}}_u\sum _{j\in \mathbb{Z}}{a}_j{u}^j=a_{-1}.$$

系数抽取可写成

$$[z^n]H(T(z))={\mathrm{Res}}_{z}H(T(z))z^{-n-1}.$$

令 $u=T(z)$；由 $T=z\varphi (T)$ 得 $z=u/\varphi (u)$。形式留数换元给出

$${\mathrm{Res}}_{z}H(T(z))z^{-n-1}={\mathrm{Res}}_{u}H(u){\left(\frac{u}{\varphi (u)}\right)}^{-n-1}\frac{d}{du}\left(\frac{u}{\varphi (u)}\right).$$

把导数展开，右边成为

$${\mathrm{Res}}_{u}H(u)u^{-n-1}(\varphi (u{)}^n-u\varphi (u{)}^{n-1}{\varphi }^{\prime }(u)).$$

另一方面，任一形式 Laurent 级数的导数留数为 $0$。对

$$H(u)u^{-n}\varphi (u{)}^n$$

求导并取留数，整理即得

$${\mathrm{Res}}_{u}H(u)u^{-n-1}(\varphi (u{)}^n-u\varphi (u{)}^{n-1}{\varphi }^{\prime }(u))=\frac{1}{n}{\mathrm{Res}}_u{H}^{\prime }(u)u^{-n}\varphi (u{)}^n.$$

最后一项正是

$$\frac{1}{n}[u^{n-1}]H^{\prime }(u)\varphi (u{)}^n.$$

这条证明显示了定理的机制：不是先把隐式方程解成根式，而是把“复合逆”变成一次留数换元，再由形式求导把复杂项压成一个系数。

1.4 应用：平面有根树由移位 Catalan 数计数

对平面有根树，$\varphi (u)=(1-u{)}^{-1}$。取 $H(u)=u$，对每个 $n\ge 1$，

$$[z^n]T(z)=\frac{1}{n}[u^{n-1}](1-u{)}^{-n}.$$

由负整数幂的二项式展开，

$$[u^{n-1}](1-u{)}^{-n}=(\genfrac{}{}{0ex}{}{2n-2}{n-1}).$$

因此大小为 $n$ 的平面有根树数为

$$T_n=\frac{1}{n}(\genfrac{}{}{0ex}{}{2n-2}{n-1})=C_{n-1},$$

其中

$$C_m=\frac{1}{m+1}(\genfrac{}{}{0ex}{}{2m}{m})$$

是第 $m$ 个 Catalan number（Catalan 数）。于是

$$T(z)=z+z^2+2z^3+5z^4+14z^5+42z^6+\cdots .$$

这也可由二次方程 $T-T^2=z$ 解出

$$T(z)=\frac{1-\sqrt{1-4z}}{2},$$

但 Lagrange 反演的优势在于：当 $T=z\varphi (T)$ 无法用根式显式解出时，系数公式仍然可用。

1.5 谱系与现代延伸：从规格到奇点

Flajolet 与 Sedgewick 的 symbolic method（符号方法）把组合构造系统化为生成函数运算；平面树是递归规格的原型。其主线不是“记住 Catalan 公式”，而是

$$\text{唯一递归分解}⟶\text{函数方程}⟶\text{Lagrange 系数公式}.$$

Graduate / modern extension. 若 $\varphi$ 具有非负系数并在足够大的复邻域内解析，许多树模型的主导奇点由 characteristic system（特征方程组）定位：

$$\tau =\rho \varphi (\tau ),1=\rho {\varphi }^{\prime }(\tau ).$$

在适当的非退化性和非周期性条件下，$T(z)$ 在 $z=\rho$ 附近出现平方根型展开，继而导向

$$[z^n]T(z)\asymp {\rho }^{-n}{n}^{-3/2}.$$

对 $\varphi (u)=(1-u{)}^{-1}$，方程组给出 $\tau =1/2$、$\rho =1/4$，这正预告 Catalan 数的 $4^n{n}^{-3/2}$ 尺度。这里先把它作为 Day 3 的解析入口；今日已经完成的是严格的形式系数公式。

2. 固定模板习题 (Template Exercise)

题目

对 $x\in (-1,1)$，定义

$$f(x)=\sum _{n=1}^{\mathrm{\infty }}\frac{x^n}{n}.$$

1. 证明该幂级数的收敛半径为 $1$，并证明对每个固定的 $r\in (0,1)$，它在 $[-r,r]$ 上绝对且一致收敛；
2. 严格说明为何可以在 $(-1,1)$ 内逐项求导，并由此求出 $f(x)$；
3. 说明同一套一致收敛论证为何不能直接扩大到 $[0,1)$，并指出 $x\uparrow 1$ 时发生什么。

模板识别

看到“幂级数 + 识别其和函数”，优先使用 power-series termwise differentiation template（幂级数逐项求导模板）：

$$\text{先定收敛半径}⟶\text{在任意紧子区间上一致控制}⟶\text{逐项求导或积分}⟶\text{用一个初值恢复常数}.$$

信号是：原系数 $1/n$ 不容易直接求和，但求导后 $n$ 被消去，出现熟悉的几何级数。

分级提示

1. 对 $|x|<1$，把 $|x{|}^n/n$ 与几何级数比较；对 $|x|>1$，先检查通项是否趋于 $0$。
2. 固定 $0<r<1$。当 $|x|\le r$ 时，用 $r^n/n$ 作 Weierstrass M-test（Weierstrass M 判别）的控制项。
3. 在收敛圆内部，幂级数可以逐项求导；求导后的级数是
   $$\sum _{n=1}^{\mathrm{\infty }}{x}^{n-1}.$$
4. 要检查 $[0,1)$ 上的一致收敛，使用 uniform Cauchy criterion（一致 Cauchy 判据），并让 $x$ 从左侧趋近 $1$。

3. 大家之言 (Mathematician in Their Own Words)

语境。 William P. Thurston 的文章 On Proof and Progress in Mathematics 收稿于 1993 年 10 月 26 日，发表于 Bulletin of the American Mathematical Society, Volume 30, Number 2, April 1994。文章回应当时关于证明、严谨与数学进步的讨论，并把问题从“数学家如何证明定理”转向“数学家究竟推进了什么”。本次引用已在 AMS 原始 PDF 中逐字核验：

“what we are doing is finding ways for people to understand and think about mathematics.”

中文译意：

“我们所做的，是寻找让人们理解数学、思考数学的方式。”

评论。 这不是降低证明标准，而是提醒我们：一个正确答案与一种可迁移的理解并不相同。对于平面树，列出 $1,1,2,5,14,\dots$ 是答案；写出

$$\mathcal{T}=\mathcal{Z}\times \mathrm{SEQ}(\mathcal{T})$$

则提供了一种思考方式：它同时暴露根、子树次序、递归语义与生成函数翻译。再向前一步，Lagrange 反演把许多看似不同的递归类统一到同一个系数机制中。

Thurston 在同文中还强调，人可以用多种方式理解同一数学对象。这里恰有三种互补表征：树的图形、组合规格、形式幂级数。证明的任务不仅是确认三者给出同一计数，也要说明每次翻译保留了什么数据、可能丢失什么数据。下节的“有序/无序”边界正说明：若构造子选错，漂亮方程也会精确地回答另一个问题。

4. 反例与边界 (Counterexample & Boundary)

把无序子树误写成有序列，会从 $4$ 数到 $5$

邻近的错误命题是：

“所有无标号有根树都满足 $\mathcal{T}=\mathcal{Z}\times \mathrm{SEQ}(\mathcal{T})$，所以有 $n$ 个顶点时共有 $C_{n-1}$ 棵。”

错处不在代数，而在对象类型。$\mathrm{SEQ}$ 会记录根子树的左右次序；一般的 non-plane rooted tree（非平面有根树）不记录该次序。

以 $4$ 个顶点为例，逐一清点无标号、无序的有根树。共有四种形状：

1. 长度为 $4$ 的有根链；
2. 根直接连接三个叶子；
3. 根只有一个孩子，而该孩子连接两个叶子；
4. 根有两个孩子：一个是叶子，另一个再连接一个叶子。

前三种在每个顶点处，要么只有一个孩子，要么所有孩子彼此同构，所以各只产生一个平面有根树。第四种的两个根子树不同：记叶子为 $L$，二顶点链为 $P$，则有两个不同的有序列

$$(L,P)\text{与}(P,L).$$

因此

$$\mathrm{\#}\{\text{四顶点非平面有根树}\}=4,$$

而

$$\mathrm{\#}\{\text{四顶点平面有根树}\}=1+1+1+2=5=C_3.$$

每个性质都可核对：两类对象都无标号、连通、无环且有根；差异只在于同一顶点的孩子是否带线性次序。这个最小附近反例说明，生成函数翻译之前必须先固定 combinatorial equality（组合等同关系）。

对非平面有根树，应使用 multiset（多重集）而不是 sequence（序列）。若 $U(z)$ 是其普通生成函数，Pólya 理论给出的方程是

$$U(z)=z\exp \left(\sum _{m\ge 1}\frac{U(z^m)}{m}\right),$$

其开头为

$$U(z)=z+z^2+2z^3+4z^4+9z^5+\cdots ,$$

而不是 $z+z^2+2z^3+5z^4+\cdots$。构造子非记号之便，而是对象类型本身；名不正，则数不准。

5. 今日一问与数学地图 (Question & Map)

今日一问。 令 $T(z)$ 是平面有根树的普通生成函数，满足

$$T(z)=\frac{z}{1-T(z)}.$$

对固定整数 $k\ge 1$，$T(z{)}^k$ 计数由 $k$ 棵平面有根树组成的有序森林。Lagrange--Bürmann 公式给出：对每个 $n\ge k$，

$$[z^n]T(z{)}^k=\frac{k}{n}[u^{n-k}](1-u{)}^{-n}=\frac{k}{n}(\genfrac{}{}{0ex}{}{2n-k-1}{n-k}).$$

能否不使用形式留数，直接构造一个 ballot path（投票路径）或 Łukasiewicz word（Łukasiewicz 词）的解释，说明为什么恰好出现因子 $k/n$？换言之，某个长度为 $n$ 的循环词族中，为什么正好有 $k$ 个循环移位编码合法的 $k$ 森林？

方向提示：把每个顶点的出度 $d$ 编码为步长 $d-1$；森林的总和应为 $-k$，而合法性还要求所有适当的前缀满足相应的高度约束。请保留最后一步的 cycle lemma（循环引理）计数空间，不要只把二项式公式重新代数变形。

数学地图。

$$\text{组合对象的唯一分解}⟶\text{符号规格}⟶\text{隐式生成函数}⟶\text{Lagrange 反演}⟶\text{Catalan 树与森林}⟶\text{循环引理与投票数}.$$

向另一侧，若把有序孩子改成无序多重集，就进入 Pólya enumeration（Pólya 枚举）与无标号结构；若把精确系数改问大尺度增长，则进入隐函数奇点、平方根展开与 singularity analysis（奇点分析）。明日可沿

$$T(z)=\frac{1-\sqrt{1-4z}}{2}$$

在 $z=1/4$ 的局部行为，解释为什么 Catalan 系数带有 $4^n$ 的指数项与 $n^{-3/2}$ 的普适修正。

附录 A：习题完整解答 (Full Solution)

展开完整解答

可复用模板：收敛半径 $\to$ 紧子区间一致控制 $\to$ 逐项求导 $\to$ 初值定常数 $\to$ 单独检查端点。

令

$$f(x)=\sum _{n=1}^{\mathrm{\infty }}\frac{x^n}{n}.$$

A.1 收敛半径与紧子区间上的一致收敛

若 $|x|<1$，则

$$0\le \sum _{n=1}^{\mathrm{\infty }}\left|\frac{x^n}{n}\right|\le \sum _{n=1}^{\mathrm{\infty }}|x{|}^n<\mathrm{\infty },$$

所以级数绝对收敛。若 $|x|>1$，则 $|x{|}^n/n$ 不趋于 $0$，级数发散。故收敛半径为 $1$。

现在固定任意 $r\in (0,1)$。对每个 $x\in [-r,r]$ 与每个 $n\ge 1$，

$$\left|\frac{x^n}{n}\right|\le \frac{r^n}{n}\le r^n.$$

而 $\sum _{n\ge 1}{r}^n$ 收敛。由 Weierstrass M 判别，原级数在 $[-r,r]$ 上绝对且一致收敛。

完整量词是：

$$\mathrm{\forall }r\in (0,1),\mathrm{\forall }\epsilon >0,\mathrm{\exists }{N}_0=N_0(r,\epsilon )\in \mathbb{N},\mathrm{\forall }M>N\ge N_0,\mathrm{\forall }x\in [-r,r],$$

都有

$$\left|\sum _{n=N+1}^M\frac{x^n}{n}\right|<\epsilon .$$

A.2 逐项求导并识别和函数

幂级数在其收敛圆内部可以逐项求导，且导数级数有同一收敛半径。因此对每个 $x\in (-1,1)$，

$$f^{\prime }(x)=\sum _{n=1}^{\mathrm{\infty }}{x}^{n-1}=\frac{1}{1-x}.$$

于是存在常数 $C$ 使

$$f(x)=-\log (1-x)+C.$$

由原级数直接得到 $f(0)=0$，故 $C=0$。因此

$$\boxed{{\displaystyle \sum _{n=1}^{\mathrm{\infty }}\frac{x^n}{n}=-\log (1-x),-1<x<1.}}$$

A.3 为什么不能把紧区间论证直接扩大到 $[0,1)$

区间 $[0,1)$ 不是收敛圆内的紧子区间；不存在统一的 $r<1$ 使所有 $x\in [0,1)$ 都满足 $x\le r$。

更强地，原级数在 $[0,1)$ 上并不一致收敛。使用一致 Cauchy 判据：对任意 $N\ge 1$，取 $M=2N+2$。当 $x\uparrow 1$ 时，有限尾和满足

$$\sum _{n=N+1}^M\frac{x^n}{n}⟶\sum _{n=N+1}^{2N+2}\frac{1}{n}.$$

右边共有 $N+2$ 项，每项至少为 $1/(2N+2)$，所以

$$\sum _{n=N+1}^{2N+2}\frac{1}{n}\ge \frac{N+2}{2N+2}>\frac{1}{2}.$$

因此对每个 $N$，都能选取足够接近 $1$ 的 $x<1$，使相应有限尾和大于 $1/2$；一致 Cauchy 条件失败。

由已求出的和函数，

$$\underset{x\uparrow 1}{lim}f(x)=\underset{x\uparrow 1}{lim}-\log (1-x)=+\mathrm{\infty }.$$

这与端点 $x=1$ 处的调和级数发散完全一致。故“收敛圆内可逐项求导”是局部于每个紧子圆盘的结论，不能未经检查越过边界。

资料与来源 (Sources)

1. Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009；官方 Princeton booksite 与完整 PDF。本期核验并使用 Chapter I 的 symbolic method、plane trees、$T=z\varphi (T)$、Lagrange inversion coefficient formula，以及 non-plane rooted trees 的 Pólya 方程；Appendix A.6 给出 Lagrange inversion。Booksite: https://ac.cs.princeton.edu/home/ ，PDF: https://ac.cs.princeton.edu/home/AC.pdf
2. NIST Digital Library of Mathematical Functions, §1.9(vi), “Power Series”。本期用于核验收敛圆内部的绝对/紧子圆盘上一致收敛及逐项求导结论。URL: https://dlmf.nist.gov/1.9#vi
3. William P. Thurston, “On Proof and Progress in Mathematics”, Bulletin of the American Mathematical Society 30(2), April 1994, pp. 161–177；received October 26, 1993。本期 Section 3 的引文及语境均由 AMS 原始 PDF 核验。URL: https://www.ams.org/journals/bull/1994-30-02/S0273-0979-1994-00502-6/S0273-0979-1994-00502-6.pdf