反射计数

约 438 字大约 1 分钟

2025-12-6

注意

我们将使用 $\displaystyle\binom{n}{m}$ 而不是 $\mathrm{C}_n^m$ 。

问题引入

Catlan 数问题

长度为 $2n$ 的合法括号序列有多少个？

这是经典的 Catlan 数问题。若把 $1\sim i$ 的左括号个数记作 $x_i$ ，右括号个数记作 $y_i$ ，则可以转化成以下问题：

Catlan 数问题（路径计数版）

每次只能沿坐标轴正方向移动一格，从 $S(0,0)$ 走到 $T(n,n)$ ，不接触 $l: y=x+1$ 的路径有多少？

让我们来研究一个更一般的问题：

有封顶的路径计数问题

每次只能沿坐标轴正方向移动一格，从 $S(0,0)$ 走到 $T(x,y)$ ，不接触 $l: y=x+b \ \ (b>0)$ 的路径有多少？

很容易证明以下结论：

普通路径计数

网格上从 $S(0,0)$ 到 $T(x,y)\ \ (x,y \ge 0)$ 的最短路径有 $\displaystyle\binom{x+y}{x}$ 条。

这很容易证明，相当于从 $(x+y)$ 步里面取 $x$ 步向右， $y$ 步向上。

加上了封顶之后，考虑正难则反：接触了 $l$ 的路径有多少条呢？

记路径第一次接触 $l$ 的点为 $P$ （考虑第一次是去重的常用手法），将 $S$ 到 $P$ 的路径以 $l$ 为轴作对称， $S$ 的对应点为 $S'(-b,b)$ 。

不难证明这样的反射是一一对应的，于是从 $S$ 到 $T$ 经过 $l$ 的路径与 $S'$ 到 $T$ 的路径一一对应，共有 $\displaystyle\binom{x+y}{x+b}$ 条。

于是答案为

\binom{x+y}{x} - \binom{x+y}{x+b}

AFO 了，加上目前流感中，先鸽了，有时间再写。

版权归属：Phantom-Bird