返回题库

格点路径计数

Number of paths from two points

专题
Discrete Math / 离散数学
难度
L4

题目详情

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

英文原题

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

解析

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

m−n+1m+1(m+nn).\frac{m-n+1}{m+1}\binom{m+n}{n}.

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

5−3+15+1(83)=36⋅56=28.\frac{5-3+1}{5+1}\binom{8}{3}=\frac{3}{6}\cdot 56=28.

英文解析

This is a Ballot/Catalan type count. For m≥nm\ge n, the number of paths from (0,0)(0,0)to (m,n)(m,n)that always satisfy y≤xy\le xis

m−n+1m+1(m+nn).\frac{m-n+1}{m+1}\binom{m+n}{n}.

Here m=5,n=3m=5,n=3, so

5−3+15+1(83)=36⋅56=28.\frac{5-3+1}{5+1}\binom{8}{3}=\frac{3}{6}\cdot 56=28.