n×n网格中对角线下方从(0,0)到(n,n)的路径数求解

嘿，这个问题其实是**卡特兰数（Catalan Number）**的经典应用场景，我来给你掰扯清楚：

首先明确你的问题条件：

• 给定$n\times n$正方形网格，起点是$(0,0)$，终点是$(n,n)$
• 每次只能向右（记为R）或向上（记为U）移动一步
• 路径全程必须在主对角线下方（可以经过$(i,i)$这类对角线上的点，但绝对不能经过$(i,i+1)$这类$y > x$的点）

核心结论 #

符合条件的路径数量，正好等于第$n$个卡特兰数，公式如下：
$$C_n = \frac{1}{n+1}\binom{2n}{n}$$

为什么是卡特兰数？ #

咱们从两个角度来理解：

1. 直接匹配经典模型：卡特兰数最经典的应用之一，就是计算从$(0,0)$到$(n,n)$、不越过主对角线（$y=x$）的单调路径数——这和你的要求完全契合：你要的路径不能进入$y > x$的区域（也就是不能经过$(i,i+1)$），只能在对角线及下方移动。

2. 用排除法推导：

   • 第一步，计算无限制的总路径数：从$(0,0)$到$(n,n)$需要走$n$步右和$n$步上，总共有$\binom{2n}{n}$种路径（本质是从$2n$步里选$n$步走右，剩下的走向上）。
   • 第二步，减去非法路径：那些越过对角线的路径，也就是第一次走到$y = x + 1$的路径。根据反射原理，每一条这样的非法路径，都能通过反射变换对应到一条从$(0,0)$到$(n-1, n+1)$的路径，这类路径的数量是$\binom{2n}{n-1}$。
   • 最后，合法路径数就是总路径数减去非法路径数：$\binom{2n}{n} - \binom{2n}{n-1} = \frac{1}{n+1}\binom{2n}{n}$，这就是卡特兰数的标准公式。

举个小例子验证 #

比如当$n=2$时：

• 无限制总路径数是$\binom{4}{2}=6$
• 非法路径有4条（分别是UURR、URUR、URRU、RUUR），这些路径都会进入$y > x$的区域
• 合法路径数为$6-4=2$，正好对应卡特兰数$C_2=2$，和公式计算结果一致。

内容的提问来源于stack exchange，提问作者user488460