格点路径计数（不越过 y=x）

Number of paths from two points

专题: Discrete Math / 离散数学
难度: L4
来源: QuantQuestion

题目详情

只允许向上 $(0,1)$ 或向右 $(1,0)$ 走。求从 $(0,0)$ 到 $(5,3)$ 的格点路径数，要求路径在过程中不穿越直线 $y=x$ （可在其上）。

We allow steps up $(0,1)$ or right $(1,0)$ . Count the lattice paths from $(0,0)$ to $(5,3)$ that do not cross $y=x$ . (Known as the Catalan-type path counting.)

解析

这是 Ballot / Catalan 型计数。对 $m\ge n$ ，从 $(0,0)$ 到 $(m,n)$ 且始终满足 $y\le x$ 的路径数为

\frac{m-n+1}{m+1}\binom{m+n}{n}.

这里 $m=5,n=3$ ，因此

\frac{5-3+1}{5+1}\binom{8}{3}=\frac{3}{6}\cdot 56=28.