第1卷 第7章 卷积

学习目标

• 能按最后一次加法的位置拆分括号结构，并写出卡塔兰数的卷积递推
• 能展开低阶对角线，区分逐项乘积与数列卷积，检查下标和边界项
• 能从生成函数乘法的系数提取卷积方程，并用 C(0)=1 选择合法平方根分支
• 能用格路径的合法前缀与反射原理互证卡塔兰数封闭表达式

从“括号放在哪里”开始

加法满足结合律，怎样加都得到同一个数值；但把每次加法看成一个二元节点后，完整的计算顺序仍然有不同结构。三个操作数有两种：(A+B)+C 与 A+(B+C)；四个操作数有五种。第 1 卷第 7 章从这个括号化问题进入卷积，最终得到 1,1,2,5,14,...。

先预测：为什么不能给每个加号独立选择左括号或右括号？怎样把一个大括号结构分成两个更小结构？递推中“先相乘后相加”为何恰好等于生成函数的平方？解出二次方程后为什么只有一个平方根分支合法？

一、括号结构与递推

加法括号组合与卡塔兰数列

令 C_n 表示用 n 个加号连接 n+1 个操作数时，完整添加括号的方式数。空结构约定为 C_0=1，所以：

$$C_0=1,\qquad C_1=1,\qquad C_2=2,\qquad C_3=5.$$

把操作数看成叶子、加号看成内部节点，每个括号式都对应一棵满二叉树。结合律让不同树的数值相同，却不改变结构计数。卡塔兰数列不是从数字外观猜出的，而是来自一次完整的结构分类。

最后一次加法分类

考虑有 n 个加号的括号式。最后执行的加号是根节点，把整体唯一分成左右两部分。若左侧含 k 个加号，就有 C_k 种；右侧含 n-1-k 个加号，就有 C_{n-1-k} 种。固定切分时左右独立选择，所以相乘；不同 k 互斥，所以相加：

$$C_n=\sum_{k=0}^{n-1}C_kC_{n-1-k}\qquad(n\ge1).$$

把下标平移一格，得到更适合卷积的形式：

$$C_{n+1}=\sum_{k=0}^{n}C_kC_{n-k}.$$

例如：

$$C_4=C_0C_3+C_1C_2+C_2C_1+C_3C_0=5+2+2+5=14.$$

这里乘法代表“左结构和右结构独立组合”，加法代表“不同切分互不重叠”。

二、从二项式定理看到固定总量

二项式定理把 (x+y)^n 展开为按 y 的次数 k 分类的组合公式。

把 (x+y)^n 看成 n 个因子的乘积。要得到 x^{n-k}y^k，必须从 n 个因子中选择 k 个贡献 y，其余贡献 x，选择数是：

$$\binom nk=\frac{n!}{k!(n-k)!}.$$

因此：

$$(x+y)^n=\sum_{k=0}^{n}\binom nkx^{n-k}y^k.$$

公式中的两个指数之和始终为 n，k 从 0 移到 n。这与卡塔兰递推中两个下标之和固定拥有同一张“总量记账表”。

二项式系数与下降阶乘幂记录了二项式展开中的有序选择与去除排列重复。

若用下降阶乘幂 n^{\underline{k}}=n(n-1)\cdots(n-k+1)，则：

$$\binom nk=\frac{n^{\underline{k}}}{k!}.$$

下降阶乘幂先记录有顺序地挑出 k 个位置，再除以 k! 消除选择顺序。代入 x=y=1 得到 Σ binom(n,k)=2^n，因为每个位置只有选或不选两种状态。一般化公式出现许多字母时，先代入小的 n 回验端点，是发现下标错误的有效方法。

三、数列卷积：先相乘后相加

数列卷积

给数列 a={a_n} 与 b={b_n}，定义：

$$(a*b)_n=\sum_{k=0}^{n}a_kb_{n-k}.$$

左下标由 0 增至 n，右下标由 n 减至 0，总和始终为 n。卡塔兰递推右侧就是 C 与自身卷积的第 n 项：

$$C_{n+1}=(C*C)_n.$$

卷积与逐项乘积不同。若 a=(1,1,1,...)、b=(1,1,1,...)，则卷积第 n 项是 n+1，因为有 n+1 种下标分解；逐项乘积却永远只得到 1。

先展开对角线，再写总公式

$$\begin{aligned} c_0&=a_0b_0,\\ c_1&=a_0b_1+a_1b_0,\\ c_2&=a_0b_2+a_1b_1+a_2b_0,\\ c_3&=a_0b_3+a_1b_2+a_2b_1+a_3b_0. \end{aligned}$$

每一行从 a_0b_n 走到 a_nb_0，项数是 n+1。交换 a,b 只反转每行次序，所以卷积可交换；序列 δ=(1,0,0,...) 与任何序列卷积仍得到原序列，它对应生成函数 1。

四、生成函数乘法为何自动执行卷积

生成函数乘法

令：

$$A(x)=\sum_{i\ge0}a_ix^i,\qquad B(x)=\sum_{j\ge0}b_jx^j.$$

相乘时 a_ix^i 与 b_jx^j 产生 a_ib_jx^{i+j}。收集 x^n 的系数，就必须遍历 i+j=n 的所有配对：

$$[x^n]A(x)B(x)=\sum_{k=0}^{n}a_kb_{n-k}=(a*b)_n.$$

数列世界中的“先相乘后相加”，在函数世界中被普通乘法自动完成。对形式幂级数而言，每个固定 n 只涉及有限个配对，不需要先讨论收敛。

五、把递推压成一个代数方程

定义 C(x)=Σ_{n≥0}C_nx^n。因为 C(x)^2 的 x^n 系数是 Σ C_kC_{n-k}=C_{n+1}，乘以 x 对齐下一项：

$$xC(x)^2=\sum_{n\ge0}C_{n+1}x^{n+1}=C(x)-C_0.$$

代入 C_0=1 得到：

C(x)=1+xC(x)^2 $$C(x)=1+xC(x)^2.$$

组合解释很直接：一个结构要么是空结构，贡献 1；要么有一个根节点，根的左右各挂一棵独立卡塔兰结构，贡献 xC(x)^2。

六、初值筛选平方根分支

把方程写成 xC(x)^2-C(x)+1=0，二次公式给出：

$$C(x)=\frac{1\pm\sqrt{1-4x}}{2x}.$$

但生成函数已经规定常数项：

C(0)=1与平方根分支决定二次方程中哪个候选符合生成函数的常数项。

正号分支在 x 趋近 0 时分子趋近 2，整体发散；负号分支分子与 x 同阶，极限为 1。因此合法分支是：

$$C(x)=\frac{1-\sqrt{1-4x}}{2x}.$$

分式在 x=0 表面是 0/0，但有理化为 2/(1+√{1-4x}) 后就能看出极限为 1。代数求解产生了两个候选，初值和幂级数常数项负责把错误分支筛掉。

七、格路径与反射原理

把括号结构编码为路径：左括号走一步向上，右括号走一步向右。合法前缀要求任意时刻右括号数不超过左括号数，路径不能越过对角边界。总共 n 步上、n 步右且不受限制的路径有 binom(2n,n) 条。

格路径与反射原理

对首次越过边界的坏路径，从第一次越界点开始交换上、右方向，得到一条终点偏移的路径；这个操作可逆。坏路径因此与含 n+1 个某方向步的路径一一对应，共 binom(2n,n+1) 条。于是：

$$C_n=\binom{2n}{n}-\binom{2n}{n+1} =\frac1{n+1}\binom{2n}{n}.$$

右侧就是卡塔兰数封闭表达式。生成函数证明强调递推和系数，反射证明强调路径边界；两种独立证据到达同一结果，互相验收。封闭式还暗示增长约为 4^n 除以多项式因子，而本章更重要的收获是：合法性约束可以通过反射转成一次计数相减。

官方概念锚点回收如下：加法括号组合与卡塔兰数列、最后一次加法分类、一般化、二项式定理、二项式系数与下降阶乘幂、数列卷积、生成函数乘法、C(x)=1+xC(x)^2、C(0)=1与平方根分支、格路径与反射原理和卡塔兰数封闭表达式，都已经在结构分类、低阶对角线、系数提取、分支筛选或路径反射中落到可复查证据上。

交互实验：把卷积的每一项算出来

n=0n=1n=2n=3n=4n=5重置实验

第 3 条卷积对角线

C₀ × C₃ = 5

C₁ × C₂ = 2

C₂ × C₁ = 2

C₃ × C₀ = 5

审计结果

Σ = 14

C₄ = 14

✓ 左右切分相乘，所有切分相加

选择 n 后，实验会显示 Σ C_kC_{n-k} 的每个配对与和，并把结果与 C_{n+1} 对照。切换阶数不是为了制造动画，而是让“左右独立相乘、切分互斥相加”在不同规模上保持可观察。

分步验收：从结构到封闭式

⚡分步1 / 4

1. 1
2. 2
3. 3
4. 4

重置

1. 分类：找到最后一次加法

固定最后一个根节点，把左侧的 k 和右侧的 n-1-k 写出来；解释为什么固定切分时相乘、遍历切分时相加。

上一步播放下一步

本章回顾：卷积把切分装进乘法

• 括号结构按最后一次加法唯一切分，左右独立选择相乘，不同切分相加。
• 数列卷积收集下标和固定的项对，不能与逐项乘积混淆。
• 生成函数乘法的系数自动完成卷积，递推因此压缩成 C(x)=1+xC(x)^2。
• C(0)=1 负责筛掉二次方程的错误平方根分支。
• 格路径的合法前缀与反射原理给出 C_n=1/(n+1) binom(2n,n)，与生成函数结论互证。

练习与答案

练习

1. 问题 1：完成最后一次加法分类。 说明 C_3 为什么等于 C_0C_2+C_1C_1+C_2C_0，并解释每个乘积的左右含义。

查看答案

有 3 个加号时，最后一次加法左侧可以含 0、1、2 个加号。对应右侧含 2、1、0 个加号；每个固定切分的左右结构独立选择，所以分别贡献 C_0C_2、C_1C_1、C_2C_0，三种切分互斥后相加得到 2+1+2=5。

2. 问题 2：检查卷积边界。 展开 (a*b)_2 和 (a*b)_3，说明为什么右下标必须是 n-k。

查看答案

(a*b)_2=a_0b_2+a_1b_1+a_2b_0，(a*b)_3=a_0b_3+a_1b_2+a_2b_1+a_3b_0。每一项的两个下标之和都等于目标 n；写成 b_k 会改变这条对角线，漏掉或重复配对。

3. 问题 3：改 Demo 代码。 给卡塔兰卷积实验增加“逐项乘积”错误模式，显示它与卷积和的差别，并保留重置按钮；说明错误模式为什么只得到 C_n² 而不是 Σ C_kC_{n-k}。

查看答案

错误模式可以显示 C_n×C_n，而正确模式逐个累加 C_0C_n 到 C_nC_0。前者只取一个输入对，后者遍历固定下标和的整条对角线；重置按钮应恢复正确卷积模式和默认阶数。

4. 问题 4：筛选平方根分支。 从 C(x)=(1±√(1-4x))/(2x) 出发，用 C(0)=1 解释为什么选择负号。

查看答案

正号分子的常数项是 2，除以趋近 0 的 2x 会发散；负号分子与 x 同阶，有理化后极限为 1。因此只有负号分支符合生成函数的常数项 C_0=1。

名词解释

本章出现的专业名词，用大白话再讲一遍。

加法括号组合与卡塔兰数列

完整括号化的数量形成 1,1,2,5,14,... 的卡塔兰数列。

最后一次加法分类

以根节点最后执行的加法为切分点，枚举左右子结构。

C(x)=1+xC(x)^2

卡塔兰生成函数的代数方程，常数项和平方项分别记录空结构与左右子结构。

数列卷积

对所有下标和为 n 的配对相乘并求和。

生成函数乘法

乘积的 x^n 系数自动收集卷积的第 n 项。

格路径与反射原理

用反射把坏路径与终点偏移路径建立一一对应。