跨卷导读：组合、路径、卷积与分拆

先问：究竟在数什么

从 5 个人中选 3 个人，答案是 10 还是 60？如果只是组成无职务小组，顺序不重要，答案是 10；如果要分配主席、秘书和财务三个职位，顺序改变了角色，答案是 60。

这不是算术熟练度问题，而是对象定义问题。计数前必须写清楚：什么算一个结果，哪些表示被视为同一个，是否允许重复，边界如何限制，以及每个合法对象是否恰好被计数一次。

先预测：若把 AB 和 BA 看成同一组，为什么要除以重复次数？一条路径越过边界后，为什么不能继续套无约束组合数？一个递推和一个生成函数乘法，怎样证明它们数的是同一批对象？

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

加法括号组合与卡塔兰数列是跨卷导读的主线：许多看起来不同的对象，都可以按最后一次组合动作拆成左、右两个子对象。合法括号串、满二叉树、凸多边形三角剖分和不过界路径因此共享同一递推结构。

不是“几个数字放在一起”这么宽泛；它必须带有合法性条件和同一性标准。只有先确定拆分后仍能唯一恢复原对象，乘法与求和才有证明依据。

例如卡特兰数从 $C_0=1$ 开始。大小为 $n+1$ 的对象若在最后一步分成大小 $i$ 与 $n-i$ 的两部分，就得到 $C_iC_{n-i}$ 种组合；对所有合法的 $i$ 求和，才得到下一项。

最后一次加法分类

最后一次加法分类把“一个大对象”变成互不重叠的分支。对每个对象，记录最后一次加法左侧子对象的大小 $i$；不同的 $i$ 不会同时描述同一棵拆分树，而每个合法对象都能回读出唯一的最后一次加法。

于是

这个式子在说：先选左子对象，再选右子对象，得到乘积；再对所有可能的分割位置相加，得到完整而不重复的计数。若漏掉某个 $i$，对象会丢失；若同一个对象在两个分支出现，计数会膨胀。

括号的例子很直观：合法串必须保持任意前缀左括号不少于右括号，并且总数相等。最外层匹配的一对括号把中间与右侧拆开，正好暴露两个独立子对象。

一般化

一般化不是把公式里的数字换成字母，而是找出递推真正依赖的结构。若每次组合动作允许三种子对象，递推会出现三重卷积；若子对象有颜色、权重或边界状态，系数也要同步携带这些信息。

从“加法括号组合与卡塔兰数列”到格路径、树和解析表达式，稳定的部分是“最后一次动作 + 左右独立”；变化的部分是对象合法性、边界和权重。先识别稳定骨架，再决定是否能够套用卡特兰闭式。

这也是跨卷导读的目的：第 1 卷的卷积、第 4 卷的路径概率和随机算法，都在处理“一个总规模如何分配给局部选择”。相同的符号不保证相同的对象，但相同的分解证明常能迁移。

二项式定理

二项式定理把代数展开与逐次选择连接起来：

这个式子在说：展开 $n$ 个因子时，恰好从其中 $k$ 个选择 $b$，其余选择 $a$；每一种位置选择贡献同一个 $a^{n-k}b^k$，因此系数就是这些位置组合的数量。

令 $a=b=1$，就得到所有子集数量为 $2^n$；令 $a=1,b=x$，则 $x^k$ 的系数统计恰好选择 $k$ 个位置的对象。代数、集合和位模式是同一计数对象的三种表示。

二项式系数与下降阶乘幂

二项式系数 与下降阶乘幂的关系来自先排列、再除去内部顺序：

这个式子在说：先把 $k$ 个有位置的对象排出来，再把同一组的 $k!$ 种内部排列视为同一个结果。若职位有区别，不应除以 $k!$；若只关心子集，除法才是去重。

固定一个特别元素 $e$，所有 $k$ 子集分成包含 $e$ 与不包含 $e$ 两类，得到帕斯卡递推：

这个式子在说：分类既覆盖全部结果，又保证两个分支互斥；递推不是另一个孤立公式，而是对象分类的压缩记录。

数列卷积

卷积 把总规模 $n$ 拆成 $i$ 与 $n-i$：

这个式子在说：先选择左侧规模 $i$ 的对象，再选择右侧规模 $n-i$ 的对象；如果两个选择彼此独立，组合数相乘，再对所有拆分位置求和。

卡特兰递推就是一种数列卷积，卷积的关键不在符号，而在“总量如何分配”和“左右对象是否独立”。若右侧选择数依赖左侧的细节，必须把状态扩展，不能机械使用一个固定卷积。

生成函数乘法

生成函数 乘法把数列卷积编码成一个系数操作。设

则

这个式子在说：乘法展开的每一条路径都选择一对指数 $i,n-i$，合并同次项后，系数正好是数列卷积。生成函数不是跳过组合证明，而是把证明后的分解结构变成代数乘法。

当对象可以分成多个独立部件时，每个部件的生成函数相乘；当对象是“若干互斥类别之一”时，生成函数相加。加法、乘法和系数提取对应对象层面的分类、独立选择和总规模筛选。

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

卡特兰对象的生成函数满足 $C(x)=\sum_{n\ge0}C_nx^n$。按最后一次加法分类，空对象贡献 1，非空对象贡献一个根节点的 $x$ 和左右两个独立子对象的 $C(x)^2$，所以

这个式子在说：递推的每个分支都被生成函数乘法保留下来；$x$ 标记根节点，平方表示左右两个子对象各自选择一次。

如果只写下方程而不说明对象拆分，就可能选到一个不对应计数序列的代数分支。生成函数方程的正确性来自双向编码：每个合法对象能拆出一对子对象，每对合法子对象又能唯一组合回对象。

C(0)=1与平方根分支

把 $C(x)=1+xC(x)^2$ 看成关于 $C$ 的二次方程，形式求解得到

这个式子在说：代数方程有两个形式分支，但计数生成函数必须满足常数项条件。将 $x$ 视为趋近 0 的形式对象时，负号分支的分子也从 0 开始，能够消掉分母的 $x$；正号分支会出现不符合计数语义的奇异项。

是分支选择的语义条件，不是事后装饰。先用 $C(0)=1$ 选出正确分支，再通过二项式级数展开验证每个系数非负且与递推一致。

格路径与反射原理

格路径与反射原理把受限路径计数转成无约束路径减去坏路径。没有边界时，从 $(0,0)$ 到 $(r,u)$ 的路径只需在 $r+u$ 个位置选择 $r$ 个右步：

这个式子在说：步的顺序就是一个二进制选择串，右步的位置确定后，上步也确定。若路径不能越过对角线，简单组合数把坏路径也算进来了。

在首次越界处反射路径前缀，把坏路径送到一个容易计数的目标集合。映射必须可逆；否则“减去坏数”可能把不同坏路径混在一起。

卡塔兰数封闭表达式

卡塔兰数封闭表达式为

这个式子在说：从所有长度为 $2n$ 的右/上步路径中，扣除越过边界的那一批后，剩下的合法路径正好是中心二项式系数除以 $n+1$。

闭式和递推必须对应同一个对象。可以用最后一次加法分类证明递推，用反射原理证明闭式，再检查两者的初值和前几项一致；“公式看起来相同”不等于完成了双射或反射证明。

容斥与随机权重的延伸

当多个条件重叠时，容斥修正重复：

这个式子在说：先把两类都加上，再减掉被算了两次的交集。对路径、子集或随机算法候选空间，交集条件必须先定义，不能看到重叠就凭直觉减一个数。

在概率问题中，计数还要乘路径权重。有限等可能样本空间可以用有利对象数除以总数；非均匀随机过程则要对每条路径的概率相乘后求和。计数对象相同，任务从“多少”变成“总权重”时，公式需要升级。

验证：公式、递推、程序互相检查

组合公式应留下第二条证据。动态规划可以用帕斯卡递推计算二项式系数，小规模位掩码可以枚举子集；两者都应满足对称性和系数和恒等式：

下面的实现用大整数保存结果，并保持上一行状态不被当前行覆盖：

export function choose(n: number, k: number): bigint {
  if (!Number.isInteger(n) || !Number.isInteger(k) || n < 0 || k < 0 || k > n)
    return 0n;
  const width = Math.min(k, n - k);
  const dp = Array<bigint>(width + 1).fill(0n);
  dp[0] = 1n;
 
  for (let row = 1; row <= n; row += 1) {
    for (let column = Math.min(row, width); column >= 1; column -= 1) {
      dp[column] += dp[column - 1];
    }
  }
  return dp[width];
}

倒序更新防止同一行的新值被再次使用。程序通过后仍要回到对象定义，确认每个合法对象只出现一次；代码正确不替代组合证明。

分步实验：从对象到卷积

小结：先定义，再分解，再验证

• 计数对象的同一性标准决定使用加法、乘法、排列还是组合。
• 最后一次加法分类把卡塔兰对象拆成左右子对象，产生卷积递推。
• 生成函数乘法把数列卷积编码为系数提取，分支要满足 $C(0)=1$。
• 格路径的边界需要反射原理或动态规划，不能直接套无约束组合数。
• 闭式、递推、程序和枚举应互相检查，而不是互相冒充。

练习与答案