Exercise 1622Combinatorics › Counting principlesOlympiadAdded 3 Nov 2026

Lattice paths

#lattice paths#binomial coefficient#monotone paths

Statement

How many monotone paths (only right and up moves) are there from $(0,0)$ to $(m,n)$ ?

Hint

The path has $m+n$ steps, $m$ of which are right.

Show solutionHide solution

Choose moves. Total steps: $m+n$ . Choose which $m$ are "right": $\binom{m+n}{m}=\binom{m+n}{n}$ .

Conclusion. There are $\binom{m+n}{m}$ lattice paths.

Example. $(0,0)$ to $(2,2)$ : $\binom{4}{2}=6$ paths.