2026-08-04 · 从奇点读出增长

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

起点问题。 前两日已经回答了两个精确问题：怎样把序列编码为生成函数，以及怎样把平面有根树的递归规格

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

翻译成

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

然而，闭式系数

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

仍没有解释：为什么增长中恰好同时出现指数尺度 $4^m$ 与幂律修正 $m^{-3/2}$？为什么许多不同递归树也出现同一个 $-3/2$ 指数？今日的出发点正是这个“精确公式有了，但增长机制尚未显形”的缺口。

对象与量词分为五层：

1. 组合层： 对每个 $n\in \mathbb{N}$，$t_n=[z^n]T(z)$ 是大小为 $n$ 的平面有根树数；
2. 解析层： $T(z)$ 在原点解析，并有收敛半径 $\rho$；
3. 局部层： 令复变量 $z\to \rho$，但须在避开分支割线的 $\mathrm{\Delta }$-domain（$\mathrm{\Delta }$ 域）中趋近；
4. 系数层： 令整数 $n\to \mathrm{\infty }$，研究 $[z^n]T(z)$；
5. 迁移层： 在明确的解析延拓假设下，把 $z\to \rho$ 的局部展开翻译为 $n\to \mathrm{\infty }$ 的系数展开。

先修是幂级数、复解析函数、Cauchy coefficient formula（Cauchy 系数公式）和 Gamma 函数的基本性质。主导 proof engines 是：定位最小模奇点、局部 Puiseux expansion（Puiseux 展开）、围道变形、$1/n$ 尺度缩放，以及标准奇异函数的系数迁移。

本期是 exploration-2026-w31-enumerative-machines 的 Day 3/3，也是弧线收束：Day 1 从序列到形式级数，Day 2 从递归规格到精确系数，今日从主导奇点到渐近增长。至此形成完整链条

$$\text{组合规格}⟶\text{生成函数}⟶\text{局部奇点}⟶\text{系数渐近}.$$

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

1.1 从平面树方程到解析分支

沿用前一期的记号，$T(z)$ 是以顶点数标记的非空平面有根树普通生成函数。方程

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

等价于 $T(z{)}^2-T(z)+z=0$。满足 $T(0)=0$ 的分支是

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

若改用通常从 $C_0=1$ 开始的 Catalan 级数

$$C(z)=\sum _{m\ge 0}{C}_m{z}^m,$$

则

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

这里平方根取在原点值为 $1$ 的解析分支。它在 $|z|<1/4$ 内解析，而在 $z=1/4$ 处出现 branch point（分支点）；故收敛半径正是

$$\rho =\frac{1}{4}.$$

令

$$X=1-\frac{z}{\rho }=1-4z.$$

则两个生成函数在 $z=\rho$ 附近分别有

$$T(z)=\frac{1}{2}-\frac{1}{2}{X}^{1/2},$$

以及

$$C(z)=\frac{2}{1+X^{1/2}}=2-2X^{1/2}+2X-2X^{3/2}+O(X^2).$$

问题因而被压缩为：$X^{1/2}$ 的 Taylor 系数怎样增长？

1.2 为什么必须说明复域：主导奇点与 $\mathrm{\Delta }$ 域

定义（dominant singularity，主导奇点）。 设

$$f(z)=\sum _{n\ge 0}{a}_n{z}^n$$

在原点解析，收敛半径为某个 $\rho \in (0,\mathrm{\infty })$。若 $\zeta \in \mathbb{C}$ 满足 $|\zeta |=\rho$，且 $f$ 不能解析延拓到 $\zeta$ 的任何开邻域，则称 $\zeta$ 为 $f$ 的一个主导奇点。若圆 $|z|=\rho$ 上只有这一个奇点，则称其为唯一主导奇点。

定义（$\mathrm{\Delta }$-domain，$\mathrm{\Delta }$ 域）。 给定 $\rho >0$、$\eta >0$ 与 $0<\varphi <\pi /2$，令

$$\mathrm{\Delta }(\rho ,\eta ,\varphi )=\{z\in \mathbb{C}:|z|<\rho +\eta ,z\ne \rho ,|\arg (z-\rho )|>\varphi \}.$$

若 $f$ 能解析延拓到某个这样的区域，就说 $f$ 在 $\rho$ 处是 $\mathrm{\Delta }$-analytic（$\mathrm{\Delta }$-解析的）。这个缺口域允许围道越过原收敛圆，却避开从 $\rho$ 发出的分支方向。

对 $T$ 与 $C$，主值平方根在割平面 $\mathbb{C}\setminus [1/4,\mathrm{\infty })$ 上解析。因此二者在 $\rho =1/4$ 附近满足所需的 $\mathrm{\Delta }$-解析性，并且 $1/4$ 是收敛圆上的唯一奇点。

1.3 标准尺度与平方根迁移

先写出标准 singular scale（奇异尺度）。

定理（standard singular-function scale，标准奇异函数尺度）。 对任意 $\rho >0$ 与任意

$$\alpha \in \mathbb{C}\setminus {\mathbb{Z}}_{\ge 0},$$

当 $n\to \mathrm{\infty }$ 时，

$$[z^n]{(1-\frac{z}{\rho })}^{\alpha }={\rho }^{-n}\frac{\mathrm{\Gamma }(n-\alpha )}{\mathrm{\Gamma }(-\alpha )\mathrm{\Gamma }(n+1)}\sim {\rho }^{-n}\frac{n^{-\alpha -1}}{\mathrm{\Gamma }(-\alpha )}.$$

这里排除非负整数，是因为那时左边只是多项式，系数最终为 $0$，而 $1/\mathrm{\Gamma }(-\alpha )$ 也在相应位置消失。

取 $\alpha =1/2$。由

$$\mathrm{\Gamma }(-\frac{1}{2})=-2\sqrt{\pi },$$

得到

$$[z^n]{(1-\frac{z}{\rho })}^{1/2}\sim -\frac{{\rho }^{-n}}{2\sqrt{\pi }{n}^{3/2}}.$$

平方根迁移推论。 设 $f$ 在 $\rho >0$ 处 $\mathrm{\Delta }$-解析，并且当 $z\to \rho$ 于该 $\mathrm{\Delta }$ 域内时，

$$f(z)=A-B{(1-\frac{z}{\rho })}^{1/2}+O(1-\frac{z}{\rho }),B\ne 0.$$

则

$$[z^n]f(z)\sim \frac{B}{2\sqrt{\pi }}{\rho }^{-n}{n}^{-3/2}.$$

证明架构。 Cauchy 系数公式给出

$$[z^n]f(z)=\frac{1}{2\pi i}{\int }_{\gamma }\frac{f(z)}{z^{n+1}}dz.$$

把原点附近的小圆变形成绕过 $\rho$ 的 Hankel-like contour（Hankel 型围道）。在奇点附近作缩放

$$z=\rho (1+\frac{t}{n}).$$

此时三个因子分别产生

$$dz=\frac{\rho }{n}dt,z^{-n-1}\sim {\rho }^{-n-1}{e}^{-t},{(1-\frac{z}{\rho })}^{\alpha }=n^{-\alpha }(-t{)}^{\alpha }.$$

于是围道积分的尺度成为 ${\rho }^{-n}{n}^{-\alpha -1}$，剩下的 Hankel 积分恰给出 $1/\mathrm{\Gamma }(-\alpha )$。$\mathrm{\Delta }$ 域假设保证围道能够这样变形，并使远离主导奇点的部分比主项更小。故“沿实轴看起来像平方根”本身不够；真正执行迁移的是复域中的解析延拓与围道控制。

1.4 应用：$4^n$、$n^{-3/2}$ 与常数各从何而来

对平面有根树生成函数

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

有 $\rho =1/4$、$B=1/2$。平方根迁移给出

$$t_n=[z^n]T(z)\sim \frac{1}{4\sqrt{\pi }}{4}^n{n}^{-3/2}=\frac{4^{n-1}}{\sqrt{\pi }{n}^{3/2}}.$$

这与 $t_n=C_{n-1}$ 一致。对未移位的 Catalan 级数，局部展开中的平方根系数为 $B=2$，所以

$$\boxed{{\displaystyle C_m\sim \frac{4^m}{\sqrt{\pi }{m}^{3/2}}(m\to \mathrm{\infty }).}}$$

三部分各有明确来源：

• ${\rho }^{-m}=4^m$ 来自主导奇点离原点的距离；
• $m^{-3/2}$ 来自奇异指数 $\alpha =1/2$ 经规则 $\alpha \mapsto -\alpha -1$；
• $1/\sqrt{\pi }$ 来自局部振幅 $B=2$ 与 $1/\mathrm{\Gamma }(-1/2)$。

还可用精确公式作独立核对。Stirling formula（Stirling 公式）给出

$$n!\sim \sqrt{2\pi n}{\left(\frac{n}{e}\right)}^n,$$

故

$$(\genfrac{}{}{0ex}{}{2m}{m})\sim \frac{4^m}{\sqrt{\pi m}},$$

再除以 $m+1\sim m$，同样得到 $C_m\sim 4^m/(\sqrt{\pi }{m}^{3/2})$。Stirling 路线验证了答案；奇点路线则解释了为何局部解析形状能系统地产生答案。

1.5 谱系与现代延伸：从一个公式到一类普适律

Catalan 数的精确枚举可追溯到 Euler、Segner 及十九世纪的相关工作；现代 analytic combinatorics（解析组合）进一步追问：能否把“函数在主导奇点附近的展开”逐项迁移成“Taylor 系数的渐近展开”？Flajolet 与 Odlyzko 1990 年的论文系统发展了基于 Cauchy 公式与 Hankel 型围道的 singularity analysis（奇点分析），并明确指出有限个同模主导奇点也须由复合围道共同处理。

Graduate / modern extension. 考虑隐式方程

$$Y(z)=z\varphi (Y(z)),$$

其中 $\varphi$ 在所需邻域解析、系数非负，并满足适当的非线性、非退化与非周期条件。若存在 $\rho >0,\tau >0$ 使 characteristic system（特征方程组）

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

成立，且 ${\varphi }^{″}(\tau )>0$，那么在标准隐函数模式的其余解析假设下，线性隐函数定理恰在 $(\rho ,\tau )$ 失效，而二阶项接管，产生

$$Y(z)=\tau -c{(1-\frac{z}{\rho })}^{1/2}+O(1-\frac{z}{\rho }),$$

其中

$$c=\sqrt{\frac{2\varphi (\tau )}{{\varphi }^{″}(\tau )}}.$$

随后迁移定理自动给出

$$[z^n]Y(z)\sim \frac{c}{2\sqrt{\pi }}{\rho }^{-n}{n}^{-3/2}.$$

对 $\varphi (u)=(1-u{)}^{-1}$，有 $\tau =1/2$、$\rho =1/4$、$c=1/2$，正好回到平面有根树。这就是 $n^{-3/2}$ 在广泛树模型中出现的机制：并非所有细节都相同，而是临界处同样由一个非退化二次接触产生平方根分支。

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

题目

设 $(Z_n{)}_{n\ge 0}$ 是一个 Galton--Watson branching process（Galton--Watson 分枝过程），从一个祖先开始，即 $Z_0=1$。每个个体独立地产生后代数 $X$，其中

$$\mathbb{P}(X=0)=\frac{1}{4},\mathbb{P}(X=2)=\frac{3}{4}.$$

令

$$q_n=\mathbb{P}(Z_n=0),$$

即过程在第 $n$ 代时已经灭绝的概率。

1. 写出后代概率生成函数 $f(s)=\mathbb{E}[s^X]$，并证明
   $$q_{n+1}=f(q_n),q_0=0.$$
2. 证明 $(q_n)$ 单调递增且收敛，其极限 $q$ 是 $[0,1]$ 中 $f$ 的最小不动点；
3. 求最终灭绝概率 $q$ 与最终存活概率 $1-q$。

模板识别

看到“独立分枝 + 最终灭绝概率”，识别 branching-process extinction fixed-point template（分枝过程灭绝不动点模板）：

$$\text{后代分布}⟶\text{概率生成函数 }f⟶q_{n+1}=f(q_n)⟶\text{单调极限}⟶\text{最小不动点}.$$

关键不是直接求解 $q=f(q)$；不动点可能不止一个，必须由从 $q_0=0$ 开始的概率迭代说明应选哪一个。

分级提示

1. 若祖先有 $k$ 个孩子，那么“第 $n+1$ 代时已经灭绝”等价于这 $k$ 条独立后代线都在再过 $n$ 代时灭绝。
2. 先算
   $$f(s)=\frac{1}{4}+\frac{3}{4}{s}^2.$$
3. 事件 $\{Z_n=0\}$ 随 $n$ 增大而递增；一旦达到 $0$，以后永远为 $0$。
4. 若 $r\in [0,1]$ 满足 $f(r)=r$，从 $q_0=0\le r$ 出发，用归纳证明 $q_n\le r$。

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

语境。 Henri Poincaré 在 Science and Hypothesis 的 Chapter I, “On the Nature of Mathematical Reasoning” 中分析 proof by recurrence（递推证明）如何从有限步骤抵达关于所有自然数的一般命题。本期核验采用 W. J. Greenstreet 的 1905 年英译本。Poincaré 写道：

“The essential characteristic of reasoning by recurrence is that it contains, condensed, so to speak, in a single formula, an infinite number of syllogisms.”

中文译意：

“递推推理的本质特征，在于它把无穷多个三段论凝缩在一个公式之中。”

评论。 Poincaré 讨论的是数学归纳法的逻辑机制，不是生成函数；两者不可混同。但他指出的“凝缩”动作恰可帮助我们理解本弧线为何反复寻找统一对象：树的逐项递推包含无穷多条系数关系，而

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

把整个系数族凝缩成一个函数方程。奇点分析再作第二次凝缩：主导点附近的一个局部指数 $1/2$，控制无穷系数共同具有的 $n^{-3/2}$ 修正。这里显出的数学态度不是“公式越短越好”，而是寻找能忠实保存无限族关系的有限表达；压缩若不保真，只是省略，压缩若保留推理结构，才成为方法。

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

一个正实主导点不一定足够：$C(z^2)$ 还有 $-1/2$

邻近的错误命题是：

“只要找到正实轴上离原点最近的平方根奇点，就可以忽略同一圆上的其他点，直接得到所有系数的渐近。”

令

$$G(z)=C(z^2)=\sum _{m\ge 0}{C}_m{z}^{2m}.$$

逐项先检查其系数支撑：

$$[z^n]G(z)=\{\begin{array}{ll}{C}_{n/2},& n\text{ 为偶数},\\ 0,& n\text{ 为奇数}.\end{array}$$

由于 $C(w)$ 在 $w=1/4$ 处奇异，复合条件 $z^2=1/4$ 给出两个同模主导奇点

$${\zeta }_{+}=\frac{1}{2},{\zeta }_{-}=-\frac{1}{2}.$$

它们都不可忽略。先在 $z=1/2$ 附近令 $X_{+}=1-2z$。因为

$$1-4z^2=(1-2z)(1+2z)=2X_{+}+O(X_{+}^2),$$

所以

$$G(z)=2-2\sqrt{2}{X}_{+}^{1/2}+O(X_{+}).$$

该点贡献

$$\frac{\sqrt{2}}{\sqrt{\pi }}{2}^n{n}^{-3/2}.$$

同理，在 $z=-1/2$ 附近令 $X_{-}=1+2z$，局部平方根振幅相同，但 ${\zeta }_{-}^{-n}=(-2{)}^n$，故该点贡献

$$\frac{\sqrt{2}}{\sqrt{\pi }}(-2{)}^n{n}^{-3/2}.$$

两点相加才得到正确主项：

$$[z^n]G(z)\sim \frac{\sqrt{2}}{\sqrt{\pi }}{2}^n{n}^{-3/2}(1+(-1{)}^n).$$

逐项核对：

• 若 $n$ 为奇数，两项严格抵消，与 $[z^n]G(z)=0$ 一致；
• 若 $n=2m$，两项相加为
  $$\frac{2\sqrt{2}}{\sqrt{\pi }}{2}^n{n}^{-3/2}=\frac{4^m}{\sqrt{\pi }{m}^{3/2}},$$
  正是 $C_m$ 的渐近。

因此，“唯一主导奇点”或相应的 aperiodicity（非周期性）条件并非技术装饰。系数只落在偶数指标上，会在复平面上表现为旋转对称的多个主导奇点；忽略其中任何一个，便会预言出本应严格为零的奇次系数。

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

今日一问。 设 $Y(z)\in z\mathbb{R}[[z]]$ 是方程

$$Y(z)=z(1+Y(z){)}^3$$

的唯一形式幂级数解，且其系数非负。请尝试完成以下任务：

1. 由特征方程组求临界对 $(\rho ,\tau )$；
2. 从隐式方程在 $(\rho ,\tau )$ 附近的二阶展开求平方根振幅 $c$；
3. 推出 $[z^n]Y(z)$ 的完整首项渐近，包括常数；
4. 说明为什么本题的系数支撑是非周期的，从而不会出现像 $C(z^2)$ 那样的同模奇点抵消。

方向提示：取 $\varphi (u)=(1+u{)}^3$，先解

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

再检查 ${\varphi }^{″}(\tau )>0$。不要只用 Lagrange 反演先求闭式系数再套 Stirling；问题的思考空间在于从临界几何直接读出渐近。

数学地图。

$$\text{唯一递归分解}⟶\text{隐式生成函数}⟶\text{特征临界方程组}⟶\text{Puiseux 平方根展开}⟶\text{奇点迁移}⟶{\rho }^{-n}{n}^{-3/2}.$$

向组合侧，这条链通往树、路径、上下文无关结构与代数生成函数；向概率侧，它邻接 Galton--Watson 树、随机树参数与极限定律；向算法侧，它进入平均复杂度和随机数据结构分析。今日完成的是“枚举机器”弧线的解析出口：精确计数与渐近计数不是两套互不相干的技巧，而是同一生成函数在形式层与复解析层的两种读法。

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

展开完整解答

可复用模板：后代 PGF $\to$ 灭绝概率迭代 $\to$ 单调极限 $\to$ 最小不动点。

后代数 $X$ 的 probability generating function（概率生成函数）是

$$f(s)=\mathbb{E}[s^X]=\frac{1}{4}{s}^0+\frac{3}{4}{s}^2=\frac{1}{4}+\frac{3}{4}{s}^2,0\le s\le 1.$$

A.1 证明迭代关系

因为 $Z_0=1$，所以

$$q_0=\mathbb{P}(Z_0=0)=0.$$

固定 $n\ge 0$。条件于祖先的后代数 $X=k$。到第 $n+1$ 代时已经灭绝，当且仅当这 $k$ 个孩子各自开启的独立分枝过程都在再过 $n$ 代时灭绝。每一条后代线发生该事件的概率都是 $q_n$，故条件概率为 $q_n^k$。由全概率公式，

$$q_{n+1}=\sum _{k\ge 0}\mathbb{P}(X=k)q_n^k=\mathbb{E}[q_n^X]=f(q_n).$$

在本题中即

$$q_{n+1}=\frac{1}{4}+\frac{3}{4}{q}_n^2.$$

A.2 单调收敛与最小不动点

令

$$E_n=\{Z_n=0\}.$$

一旦过程灭绝，以后的种群数始终为 $0$，所以

$$E_n\subseteq E_{n+1}.$$

因此

$$0=q_0\le q_1\le q_2\le \cdots \le 1.$$

由实数完备性，存在 $q\in [0,1]$ 使

$$q_n\uparrow q.$$

函数 $f(s)=1/4+3s^2/4$ 在 $[0,1]$ 上连续，于是对迭代式取极限：

$$q=\underset{n\to \mathrm{\infty }}{lim}{q}_{n+1}=\underset{n\to \mathrm{\infty }}{lim}f(q_n)=f(q).$$

故 $q$ 是一个不动点。

还需证明它是最小不动点。任取 $r\in [0,1]$，假设 $f(r)=r$。由于 $q_0=0\le r$，并且 $f$ 在 $[0,1]$ 上单调递增，若 $q_n\le r$，则

$$q_{n+1}=f(q_n)\le f(r)=r.$$

归纳得到

$$\mathrm{\forall }n\ge 0,q_n\le r.$$

令 $n\to \mathrm{\infty }$，得 $q\le r$。因此 $q$ 是 $f$ 在 $[0,1]$ 中的最小不动点。

A.3 求灭绝与存活概率

解不动点方程：

$$q=\frac{1}{4}+\frac{3}{4}{q}^2.$$

等价于

$$3q^2-4q+1=0,$$

即

$$(3q-1)(q-1)=0.$$

两个 $[0,1]$ 中的不动点为

$$q=\frac{1}{3}\text{与}q=1.$$

由最小不动点原则，最终灭绝概率是

$$\boxed{{\displaystyle q=\frac{1}{3}}}.$$

因此最终存活概率为

$$\boxed{{\displaystyle 1-q=\frac{2}{3}}}.$$

作为一致性检查，平均后代数为

$$\mathbb{E}[X]=0\cdot \frac{1}{4}+2\cdot \frac{3}{4}=\frac{3}{2}>1,$$

所以过程是 supercritical（超临界）的，存在正的存活概率；这与 $1-q=2/3>0$ 相符。

资料与来源 (Sources)

1. Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009. 本期核验并使用开篇 Catalan 例、Chapter VI 的 standard function scale、$\mathrm{\Delta }$ 域、Cauchy--Hankel 证明架构与 transfer theorems，以及 Chapter VII 的隐函数平方根模式。官方 Princeton booksite: https://ac.cs.princeton.edu/home/ ，完整 PDF: https://ac.cs.princeton.edu/home/AC.pdf ，Chapter VI 页面: https://ac.cs.princeton.edu/60singularity/
2. Philippe Flajolet and Andrew M. Odlyzko, “Singularity Analysis of Generating Functions”, SIAM Journal on Discrete Mathematics 3(2), May 1990, pp. 216--240. 本期用于核验该方法的论文谱系、Cauchy/Hankel 围道机制、解析延拓条件，以及有限个主导奇点需合并处理的边界。作者资料页所载论文 PDF: https://algo.inria.fr/flajolet/Publications/FlOd90b.pdf
3. Henri Poincaré, Science and Hypothesis, translated by W. J. Greenstreet, Walter Scott Publishing Co., 1905, Chapter I, “On the Nature of Mathematical Reasoning”. Section 3 的英译引文与版本信息均由 Project Gutenberg EBook #37157 核验。Item page: https://www.gutenberg.org/ebooks/37157 ，PDF: https://www.gutenberg.org/files/37157/37157-pdf.pdf
4. NIST Digital Library of Mathematical Functions, §5.11, “Asymptotic Expansions”, Gamma Function chapter. 本期用于独立核验 Stirling 公式及 Gamma 渐近背景。URL: https://dlmf.nist.gov/5.11