关于终点非0层的Dyck路径计数及特定终点长Dyck路径数量的技术问询

安全阿岳

2026-4-21

先明确问题背景与核心疑问：

标准2n步Dyck路径是从(0,0)到(2n,0)的格路径，每步仅能选择(+1,+1)（上步）或(+1,-1)（下步），且全程不低于x轴。这类路径的数量是广为人知的卡特兰数： $\frac{1}{n+1}\binom{2n}{n}$ 。

现在想请教的是：当m>0时，从(0,0)出发，走(2n+m)步后终点落在(2n+m, m)，且全程不低于x轴的这类路径有多少条？

其实这个问题可以通过组合数学里的反射原理推导得到简洁的公式，下面一步步拆解：

步骤1：计算无限制条件下的总路径数

先不考虑“不低于x轴”的约束，从(0,0)走到(2n+m, m)的路径总数可以通过步数分析得出：
设上步数量为u，下步数量为d，根据终点坐标可得方程组：

解方程组得：u = n + m，d = n。也就是说，我们需要从(2n+m)步中选n步作为下步，剩下的作为上步，总路径数为 $\binom{2n+m}{n}$ 。

非法路径指的是中途走到x轴以下（即y=-1）的路径。对于任意一条非法路径，我们将其从起点到第一次到达y=-1的部分关于直线y=-1做反射，此时原起点(0,0)会被映射到(0,-2)。

现在计算反射后从(0,-2)到(2n+m, m)的路径数：
同样设上步数量为u'，下步数量为d'，可得：

解得：u' = n + m + 1，d' = n - 1。对应的路径数为 $\binom{2n+m}{n-1}$ （当n=0时，非法路径数为0，符合直觉）。

合法路径数 = 总路径数 - 非法路径数，代入上面的结果可得：
$\binom{2n+m}{n} - \binom{2n+m}{n-1}$

我们还可以将这个式子化简，提取公因子后得到更简洁的形式：
$\frac{m+1}{n+m+1}\binom{2n+m}{n}$

这个公式属于广义卡特兰数的范畴，也可以看作是Ballot定理的应用场景：Ballot定理描述的是候选人A得a票、B得b票（a>b）时，A全程领先B的情况数，而我们的场景中，上步对应A的票、下步对应B的票，“全程不低于x轴”等价于A的票数始终不少于B的票数，代入定理变形即可得到上述结果。

比如取n=1，m=1，总步数3，终点(3,1)：
合法路径有2条：「上、上、下」「上、下、上」（「下、上、上」因第一步走到y=-1属于非法路径）。
用公式计算： $\frac{1+1}{1+1+1}\binom{3}{1} = \frac{2}{3} \times 3 = 2$ ，与实际结果一致。

再取n=0，m=2，总步数2，终点(2,2)：
合法路径只有1条「上、上」，公式计算： $\frac{2+1}{0+2+1}\binom{2}{0} = \frac{3}{3} \times 1 = 1$ ，完全正确。

备注：内容来源于stack exchange，提问作者LeafGlowPath