Lattice path

Summary

A lattice path is a finite sequence of points of the integer lattice $\mathbb{Z}^2$. Each step between consecutive points is from a given finite set of steps. The most common case uses the steps $E = (1, 0)$ and $N = (0, 1)$. These are North-East lattice paths.

A North-East path from $(0, 0)$ to $(a, b)$, with $a, b \in \mathbb{N}$, has $a$ steps $E$ and $b$ steps $N$. It is a word of length $a + b$ in $E$ and $N$. Thus the number of such paths is the binomial coefficient $\binom{a + b}{a}$.

Remarks

The number of North-East paths from $(0, 0)$ to $(n, n)$ is the central binomial coefficient $\binom{2n}{n}$. The paths of this type that never go above the diagonal $y = x$ are counted by the Catalan numbers. They correspond to Dyck words.

Explanations

L1 human

Think of a city grid where you may only walk east or north. To go 3 blocks east and 2 blocks north, you choose which 2 of your 5 steps go north, so there are $\binom{5}{2} = 10$ routes.