bijection · 格路 ↔ C(n, k)

双射证明与格路模型

要证两个计数相等，一条路是各算一遍再比数值，另一条路是在两类对象之间造一个一一对应。后者给出的是构造，比代数验算多说明一件事：对象之间到底是怎么对上的。本页以格点上的路线为例，把它先对应到 R/U 串、再对应到位置子集，读出计数 $C(a+b,\, a)$ 。

1 · 一一对应作为证明手段

定义 1.1（双射） 集合 $S$ 到集合 $T$ 的映射 $f$ 若既是单射又是满射，则称 $f$ 为双射（bijection）。有限集之间存在双射时两者元素个数相等，记 $|S| = |T|$ 。

双射证明把「两个数相等」换成「两批对象能配对」。代数验算只能确认等号成立，双射还交出配对规则本身，而这条规则通常可以直接拿去做编码、枚举与等概率抽样：知道第 $i$ 条格路对应哪个子集，就等于知道怎么给全部格路编号。

判断一个映射是不是双射，最省事的办法是把逆映射写出来。写得出逆映射，单射与满射都不必单独验。本页后面的每处双射都按这个办法给出：正向一句，反向一句，两句合起来即证。

2 · 格路模型与位置子集

lattice path · C(a+b, a)

从 $(0, 0)$ 出发，每步向右或向上一格，走到 $(a, b)$ 的路线称为单调格路（monotone lattice path）。任一条这样的路线恰含 $a$ 步向右与 $b$ 步向上，按先后写成一个长为 $a+b$ 的 R/U 串；反过来，任一含 $a$ 个 R 的 R/U 串按字符逐步走，走回一条路线。两个方向互逆，第一重双射成立。

第二重在 R/U 串与位置子集之间：一个串由「哪些位置放 R」完全决定，取 R 的下标集得到 $\{0, 1, \dots, a+b-1\}$ 的一个 $a$ 元子集；取一个 $a$ 元子集反填 R、其余填 U，得到原串。两重合起来给出

\bigl|\,\{\,(0,0) \to (a,b)\ \text{的单调格路}\,\}\,\bigr| = C(a+b,\, a)

图 2-1 · 格点网格与到达各点的路径数。可调

a

、

b

改变终点，点击任一格点把它设为新终点，点击下方任一 R/U 串在网格上高亮对应的那条路线。

把每个格点标上到达它的路径数，得到的是转了 45° 的 Pascal 三角（见 Pascal 三角与二项式定理 §1）。格点 $(x, y)$ 的上一步只能来自左邻 $(x-1, y)$ 或下邻 $(x, y-1)$ ，两类互斥且穷尽，该点计数等于两邻之和，这条就是 Pascal 递推 $C(n, k) = C(n-1, k-1) + C(n-1, k)$ 换了坐标系的写法。

警示 · 递推网格与闭式在大参数下会分家。本系列的 comb 走浮点连乘连除再 Math.round，而 pathGrid 只做整数加法。从 $a + b = 0$ 起逐层比对全部格点，第一处分歧落在 $a + b = 56$ ： $C(56, 23)$ 的精确值是 $3167295784216200$ ，comb 给出 $3167295784216201$ ，差 $1$ 。该值只有 $2^{53}$ 的约三分之一，仍在安全整数范围内，分歧来自中途除法的舍入而非溢出；整数递推自身要到 $a + b = 57$ 才越过 Number.MAX_SAFE_INTEGER。core/paths.test.ts 把这两个数字连同「 $a + b \le 55$ 全部相等」一并锁成断言。

3 · 对称性与隔板法的双射读法

$C(n, k) = C(n, n-k)$ 的双射是取补：把每个 $k$ 元子集换成它在 $\{0, 1, \dots, n-1\}$ 里的补集。取补映射与自身复合是恒等映射，即它是对合，逆映射就是它本身，双射性不必另证。放回格路上读，取补即把每条路线的 R 与 U 全部对调， $(a, b)$ 的路线一一对应到 $(b, a)$ 的路线。

隔板法（stars and bars）本身也是一个双射，可重复选取 §1 已经用过：从 $n$ 种类型里无序可放回地取 $k$ 个，取法由每种类型各取几个完全决定，写成 $k$ 颗星被 $n-1$ 根竖线隔成 $n$ 段的一排记号；反向读这排记号，段内星数即各类型的取数。两端互逆，取法数等于在 $k+n-1$ 个位置里挑竖线位置的数目 $C(n+k-1,\, n-1)$ 。

Catalan 数的反射法是同一手法的加强版：在格路之间再造一个双射，把越过对角线的路线双射到一族容易数的格路，用总数减掉它。组合数本身的定义与它同排列的关系见组合 C(n, k)。

4 · 参考文献

Bijective proof. Wikipedia. 双射证明的思想、判据与若干经典例子。https://en.wikipedia.org/wiki/Bijective_proof
Lattice path. Wikipedia. 格路的定义、单调格路计数与反射法。https://en.wikipedia.org/wiki/Lattice_path
Stars and bars. Wikipedia. 隔板法把无序可放回的取样化归成排星与竖线。https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)