2026-08-02 · 把序列挂到函数上

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

起点问题。 枚举组合里常见的答案不是一个数，而是一整列数：$a_0,a_1,a_2,\dots$。如果直接写出 $a_n$ 很困难，我们能否先把整列数压成一个可操作对象，再从这个对象中读回每个系数？Generating function（生成函数）的回答是：把序列挂到一个形式幂级数上，让递推、乘法、分解和奇点成为研究序列的工具。

本期的对象层分为四层：

1. 系数层：一个序列 $(a_n{)}_{n\ge 0}$，通常来自“大小为 $n$ 的对象有多少个”；
2. 形式层：级数 $A(x)=\sum _{n\ge 0}{a}_n{x}^n$，先作为 formal power series（形式幂级数），不要求 $x$ 取任何数值；
3. 代数层：递推、乘积、除法在形式幂级数环中变成方程；
4. 解析层：当级数有收敛半径时，再把 $A(x)$ 看成复函数，用 poles（极点）、singularities（奇点）解释 $a_n$ 的增长。

先修只需要多项式乘法、几何级数、常系数线性递推和一点点组合计数。主导 proof engines 是：coefficient extraction（系数抽取）、Cauchy product（柯西乘积）、index shifting（指标移位）、partial fractions（部分分式）和“每个大小 $n$ 的对象只涉及有限选择”的逐系数论证。

今天是新的 ordinary exploration micro-arc exploration-2026-w31-enumerative-machines 的 Day 1/3。由于本周 roaming issue 已经用过，今天不再漫游，而是开启一条枚举机器弧线：Day 1 建立生成函数的形式语言；后续可进入分拆乘积、符号方法，以及从有理函数到解析组合的增长估计。

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

1.1 普通生成函数：先是形式对象，不是函数图像

定义（formal power series，形式幂级数）。 设 $R$ 是含 $1$ 的交换环。$R[[x]]$ 是所有形式和

$$A(x)=\sum _{n\ge 0}{a}_n{x}^n,a_n\in R,$$

组成的集合。加法逐项定义，乘法由 Cauchy product 定义：若

$$A(x)=\sum _{n\ge 0}{a}_n{x}^n,B(x)=\sum _{n\ge 0}{b}_n{x}^n,$$

则

$$A(x)B(x)=\sum _{n\ge 0}\left(\sum _{i=0}^n{a}_i{b}_{n-i}\right)x^n.$$

这里每个 $x^n$ 的系数只含有限和，所以乘法在形式层是良定义的。

定义（ordinary generating function, OGF，普通生成函数）。 给定序列 $(a_n{)}_{n\ge 0}$，它的普通生成函数是

$$A(x)=\sum _{n\ge 0}{a}_n{x}^n.$$

系数抽取记号定义为

$$[x^n]A(x)=a_n.$$

完整量词是：

$$\mathrm{\forall }n\in {\mathbb{N}}_0,[x^n]\sum _{m\ge 0}{a}_m{x}^m=a_n.$$

RMK. “生成函数”这个名称容易误导。形式层中 $x$ 不是实数或复数，$A(x)$ 也不先是一条曲线；它是一个把所有系数排在一起的代数对象。只有当我们额外讨论收敛半径时，才进入 analytic function（解析函数）的语境。

1.2 常系数递推为何给出有理生成函数

先给出一个可反复使用的定理。

定理（linear recurrence to rational OGF，线性递推到有理生成函数）。 设 $K$ 是域，$d\ge 1$，$c_1,\dots ,c_d\in K$。若序列 $(a_n{)}_{n\ge 0}$ 满足

$$\mathrm{\forall }n\ge d,a_n=c_1{a}_{n-1}+c_2{a}_{n-2}+\cdots +c_d{a}_{n-d},$$

定义

$$A(x)=\sum _{n\ge 0}{a}_n{x}^n,Q(x)=1-c_{1}x-c_2{x}^2-\cdots -c_d{x}^d.$$

再约定 $a_j=0$ for $j<0$，并令

$$P(x)=\sum _{n=0}^{d-1}(a_n-c_1{a}_{n-1}-c_2{a}_{n-2}-\cdots -c_d{a}_{n-d})x^n.$$

则在 $K[[x]]$ 中有

$$Q(x)A(x)=P(x),$$

从而

$$A(x)=\frac{P(x)}{Q(x)}.$$

这里除法合法，因为 $Q(0)=1$，所以 $Q(x)$ 在形式幂级数环中可逆。

证明。 计算 $Q(x)A(x)$ 的 $x^n$ 系数。由 Cauchy product，

$$[x^n]Q(x)A(x)=a_n-c_1{a}_{n-1}-c_2{a}_{n-2}-\cdots -c_d{a}_{n-d},$$

其中 $a_j=0$ for $j<0$。当 $n\ge d$ 时，这个系数由递推式等于 $0$；当 $0\le n<d$ 时，它正是 $P(x)$ 中对应的系数。因此 $Q(x)A(x)$ 只剩前 $d$ 项，等于 $P(x)$。故证。

这个定理的要点不是“有理函数看起来漂亮”，而是：递推关系本来是无限多个方程，乘上 $Q(x)$ 后，它们被一次性压缩为一个有限分子。若 $Q$ 可因式分解，partial fractions 会把系数抽取变成几何级数系数抽取。

例如 Fibonacci sequence（Fibonacci 数列）满足 $F_0=0,F_1=1$，且

$$\mathrm{\forall }n\ge 2,F_n=F_{n-1}+F_{n-2}.$$

按定理得到

$$\sum _{n\ge 0}{F}_n{x}^n=\frac{x}{1-x-x^2}.$$

这已经是一个完整答案：

$$F_n=[x^n]\frac{x}{1-x-x^2}.$$

若再进入解析或代数闭式层，分母根会给出 Binet formula；若只需递推计算，形式恒等式本身已足够。

1.3 乘积如何编码选择：整数分拆的生成函数

递推不是生成函数唯一的入口。另一条主线是：乘法编码独立选择。

定义（integer partition，整数分拆）。 对 $n\in {\mathbb{N}}_0$，$n$ 的一个分拆是一个有限非增正整数列

$$\lambda =({\lambda }_1,\dots ,{\lambda }_r),{\lambda }_1\ge \cdots \ge {\lambda }_r\ge 1,\sum _{i=1}^r{\lambda }_i=n.$$

空列是 $0$ 的唯一分拆。记 $p(n)$ 为 $n$ 的分拆数。

命题（partition product formula，分拆乘积公式）。 在 $\mathbb{Z}[[q]]$ 中，

$$\sum _{n\ge 0}p(n)q^n=\prod _{k\ge 1}\frac{1}{1-q^k}.$$

逐系数证明。 对固定的 $k$，

$$\frac{1}{1-q^k}=1+q^k+q^{2k}+q^{3k}+\cdots$$

表示“部件 $k$ 取 $0,1,2,3,\dots$ 次”。从所有 $k\ge 1$ 的因子中选择一项 $q^{m_{k}k}$，乘积贡献

$$q^{\sum _{k\ge 1}{m}_{k}k}.$$

当我们只看 $q^n$ 的系数时，必有 $m_k=0$ for $k>n$，并且满足 $\sum k{m}_k=n$ 的非负整数列 $(m_1,\dots ,m_n)$ 只有有限种。这样的列与 $n$ 的分拆一一对应：$m_k$ 就是部件 $k$ 出现的次数。因此右边 $q^n$ 的系数正是 $p(n)$。

同理，如果只允许 distinct parts（互异部件），每个部件 $j$ 只能选或不选；若再用 $z$ 标记部件个数，则

$$\sum _{m,n\ge 0}D(m,n)z^m{q}^n=\prod _{j\ge 1}(1+z{q}^j),$$

其中 $D(m,n)$ 是把 $n$ 分拆成 $m$ 个互异正整数的方式数。George Andrews 对 partition theory（分拆理论）的历史梳理中指出，Euler 正是从 Naudé 关于“$50$ 分成 $7$ 个互异部件”的问题出发，引入这类生成函数方法，并得到答案 $522$。

1.4 谱系：Euler 的乘积，Wilf 的桥，Flajolet--Sedgewick 的奇点

Euler Archive 对 Euler 的论文 Observationes analyticae variae de combinationibus 的说明很谨慎：这篇文章“may be where generating functions are first used”。我们不必把“第一次”说死；足够重要的事实是，它把分拆问题转化为级数和无穷乘积，并把具体计算推进到一般方法。

Wilf 的 generatingfunctionology 则把现代教学中的核心态度说得很清楚：生成函数是 discrete mathematics（离散数学）与 continuous analysis（连续分析）之间的桥。形式层负责正确编码，解析层负责解释增长。若只做形式代数，我们能解递推、证恒等式、组织分拆；若再看复平面上的奇点，便能读出系数的渐近。

Flajolet 与 Sedgewick 的 Analytic Combinatorics 把这条路径系统化为三步：

$$\text{combinatorial specification}⟶\text{generating function}⟶\text{coefficient asymptotics}.$$

Graduate / modern extension. 若 $A(x)=P(x)/Q(x)$ 是有理函数，且最靠近原点的奇点是简单极点 $\rho$，许多情况下系数满足

$$a_n\sim C{\rho }^{-n}.$$

这里的 $\rho$ 来自解析层，而非形式层。形式幂级数告诉我们“哪个数是 $[x^n]A(x)$”；复分析进一步告诉我们“当 $n$ 很大时它大约多大”。二者不可混同，却彼此成全。

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

题目

设序列 $(a_n{)}_{n\ge 0}$ 满足

$$a_0=0,a_1=1,$$

且对所有 $n\ge 2$，

$$a_n=3a_{n-1}-2a_{n-2}.$$

1. 求普通生成函数

   $$A(x)=\sum _{n\ge 0}{a}_n{x}^n.$$

2. 用部分分式求 $a_n$ 的闭式公式。

模板识别

看到“常系数线性递推 + 初值 + 求闭式”，可以尝试 rational generating function recurrence template（有理生成函数递推模板）：

$$\text{递推}\Rightarrow \text{乘 }{x}^n\text{ 并求和}\Rightarrow \text{解出 }A(x)\Rightarrow \text{分母因式分解}\Rightarrow \text{抽取系数}.$$

本题的信号是：递推右边只含固定滞后项 $a_{n-1},a_{n-2}$，系数 $3,-2$ 不依赖 $n$。

分级提示

1. 先写出

   $$\sum _{n\ge 2}{a}_n{x}^n=A(x)-a_0-a_{1}x.$$

2. 对右边两项分别移位：

   $$\sum _{n\ge 2}{a}_{n-1}{x}^n=x(A(x)-a_0),\sum _{n\ge 2}{a}_{n-2}{x}^n=x^{2}A(x).$$

3. 你应得到一个形如

   $$A(x)-x=3xA(x)-2x^{2}A(x)$$

   的代数方程。

4. 分母 $1-3x+2x^2$ 可以因式分解为 $(1-x)(1-2x)$。

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

语境。 Leonhard Euler 的 Observationes analyticae variae de combinationibus 于 1741 年 4 月 6 日提交给 St. Petersburg Academy，1751 年发表。今日核验使用 Euler Archive / University of the Pacific 的 E158 条目，以及 Jordan Bell 的英译本 Various analytic observations on combinations。这里引用的是英译文本；原文为 Latin，本期不重构未核验的拉丁原句。

在论文末尾，Euler 写下了一个后来成为 Euler pentagonal number theorem（Euler 五边形数定理）的观察。他没有把观察伪装成已完成证明，而是先标明证明边界：

“At the end of this paper there is a noteworthy observation to make, which however I have not yet been able to demonstrate with geometric rigor.”

中文译意：

“在本文末尾，还有一个值得注意的观察；不过我尚未能以几何式的严谨证明它。”

评论。 这句话的数学态度并不是“凭直觉相信模式”，而是把发现、计算、归纳和证明分开安放。紧接着，Euler 记录了乘积

$$(1-q)(1-q^2)(1-q^3)\cdots$$

展开后只在 generalized pentagonal numbers（广义五边形数）处出现非零系数、且符号成对交替的现象。用今天的话说，他已经抓住了分拆生成函数的倒数结构；严格证明后来可以由 Euler 自己和 Franklin 等人的组合论证补上。可贵处在于：生成函数允许人先看见一个大结构，同时又要求人清楚地区分“看见”与“证明”。学问之道，贵在不欺其所未证。

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

4.1 形式恒等式不能随意当作数值恒等式

在形式幂级数环中，

$$\frac{1}{1-2x}=\sum _{n\ge 0}{2}^n{x}^n$$

是完全正确的。检查如下：

$$(1-2x)\sum _{n\ge 0}{2}^n{x}^n=\sum _{n\ge 0}{2}^n{x}^n-\sum _{n\ge 1}{2}^n{x}^n=1.$$

逐系数看，常数项为 $1$；对每个 $n\ge 1$，$x^n$ 的系数是 $2^n-2\cdot 2^{n-1}=0$。所以形式层没有问题。

但若把 $x$ 当作实数并代入 $x=1$，右边变成

$$\sum _{n\ge 0}{2}^n,$$

它发散；左边的有理表达式则给出

$$\frac{1}{1-2}=-1.$$

矛盾不是恒等式错了，而是我们越过了类型边界：形式恒等式允许系数运算；解析恒等式还需要收敛区域。事实上，几何级数作为复函数的展开只在 $|2x|<1$，即 $|x|<1/2$ 内成立。生成函数入门最常见的误用，正是把“形式上可逆”误读成“处处可代值”。

4.2 去掉初值，递推也不决定序列

上一节的定理还提醒我们：递推关系必须带上初始数据。只写

$$a_n=3a_{n-1}-2a_{n-2}(n\ge 2)$$

并不能唯一确定 $(a_n)$。例如

$$a_n=0$$

和

$$a_n=2^n-1$$

都满足同一个递推。逐项检查第二个序列：对 $n\ge 2$，

$$3(2^{n-1}-1)-2(2^{n-2}-1)=3\cdot 2^{n-1}-2^{n-1}-1=2^n-1.$$

它与零序列不同，却同样满足递推。因此“递推式”只是无限约束的一部分；真正的枚举问题还需要边界条件、初值或其他归一化条件。生成函数中的分子 $P(x)$ 正是这些初值的记录。

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

今日一问。 设 $(a_n)$ 是非负序列，普通生成函数 $A(x)=P(x)/Q(x)$ 为有理函数，$Q(0)=1$。假设 $Q$ 在最小模长的零点 $\rho >0$ 处有一个简单零点，并且没有其他零点满足 $|z|=\rho$。为什么这会导致

$$a_n\sim C{\rho }^{-n}$$

对某个常数 $C$ 成立？在这个论证中，哪一步已经不再是形式幂级数代数，而是真正使用了复分析？

一个方向提示：把 $A(x)$ 分解为 $\rho$ 附近的主极点项加上一个在更大圆盘内解析的余项；主极点给出几何级数系数，余项的系数由更大的收敛半径控制。但请先想清楚：为何“最近的奇点”会支配系数？

地图。

$$\text{序列与递推}⟶\text{普通生成函数}⟶\text{有理函数与部分分式}⟶\text{分拆乘积与符号方法}⟶\text{解析组合与奇点渐近}.$$

从 roadmap 看，combinatorics.generating-functions 邻接 algebra.representation-characters：特征标表、cycle index 与 Pólya enumeration 都会把“对象分类”转化为生成函数。向概率与随机结构侧，multivariate generating functions（多变量生成函数）还能标记参数，并导向 limit laws（极限定律）。今天的关键不是掌握所有技巧，而是建立一个原则：先把计数对象编码正确，再决定是否需要解析地读出增长。

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

展开完整解答

可复用模板：常系数递推 $\to$ 有理生成函数 $\to$ 部分分式 $\to$ 系数抽取。

令

$$A(x)=\sum _{n\ge 0}{a}_n{x}^n.$$

由 $a_0=0,a_1=1$，左边求和为

$$\sum _{n\ge 2}{a}_n{x}^n=A(x)-x.$$

对递推式两边乘 $x^n$ 并对 $n\ge 2$ 求和，得到

$$\sum _{n\ge 2}{a}_n{x}^n=3\sum _{n\ge 2}{a}_{n-1}{x}^n-2\sum _{n\ge 2}{a}_{n-2}{x}^n.$$

右边两项分别移位：

$$\sum _{n\ge 2}{a}_{n-1}{x}^n=x\sum _{m\ge 1}{a}_m{x}^m=xA(x),$$

因为 $a_0=0$；并且

$$\sum _{n\ge 2}{a}_{n-2}{x}^n=x^2\sum _{m\ge 0}{a}_m{x}^m=x^{2}A(x).$$

所以

$$A(x)-x=3xA(x)-2x^{2}A(x).$$

移项得

$$(1-3x+2x^2)A(x)=x,$$

即

$$A(x)=\frac{x}{1-3x+2x^2}=\frac{x}{(1-x)(1-2x)}.$$

设

$$\frac{x}{(1-x)(1-2x)}=\frac{B}{1-x}+\frac{C}{1-2x}.$$

则

$$x=B(1-2x)+C(1-x).$$

比较常数项与 $x$ 项：

$$B+C=0,-2B-C=1.$$

解得 $B=-1,C=1$。因此

$$A(x)=-\frac{1}{1-x}+\frac{1}{1-2x}.$$

在形式幂级数中展开：

$$\frac{1}{1-x}=\sum _{n\ge 0}{x}^n,\frac{1}{1-2x}=\sum _{n\ge 0}{2}^n{x}^n.$$

于是

$$A(x)=\sum _{n\ge 0}(2^n-1)x^n.$$

所以

$$\boxed{{\displaystyle a_n=2^n-1(n\ge 0).}}$$

检查初值：$a_0=0$，$a_1=1$；并且正文第 4 节已经逐项验证该闭式满足递推。

资料与来源 (Sources)

1. Herbert S. Wilf, generatingfunctionology, Internet Edition, University of Pennsylvania PDF. 本期用于普通生成函数、递推转有理函数、系数抽取与“离散/连续双声道”背景；引用页在本次运行中已打开核验。URL: https://www2.math.upenn.edu/~wilf/gfology2.pdf
2. Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, official Princeton booksite and full PDF. 本期用于解析组合的 formal specification $\to$ generating functions $\to$ singularity/asymptotics 谱系。URL: https://ac.cs.princeton.edu/home/ ，PDF: https://ac.cs.princeton.edu/home/AC.pdf
3. George E. Andrews, “Partitions”, chapter PDF. 本期用于 Euler、Naudé 问题、互异分拆生成函数、$D(7,50)=522$ 与五边形数定理的历史谱系。URL: https://personal.science.psu.edu/lxv1/alg/antheory/preprint/andrews/chapter.pdf
4. Euler Archive / University of the Pacific Scholarly Commons, E158, Leonhard Euler, Observationes analyticae variae de combinationibus. 本期用于核验题名、Eneström 编号、原文语言、提交/发表信息与 Euler 分拆论文来源。URL: https://scholarlycommons.pacific.edu/euler-works/158
5. Leonhard Euler, Various analytic observations on combinations, translated from Latin by Jordan Bell, arXiv:0711.3656. 本期 Section 3 的英译引文来自该 PDF；原文为 Latin，本期只引用已核验英译句子并给出中文译意。URL: https://arxiv.org/pdf/0711.3656