Shortest paths on a grid

Text

On a rectangular grid, we want to go from the top-left corner $A$ to the bottom-right corner $B$, moving along the lines and at each step going one unit right or one unit down. If reaching $B$ requires $5$ steps to the right and $3$ steps down, how many different shortest paths are there?

Solution

Each path is a sequence of $8$ steps, of which $5$ are “Right” (R) and $3$ are “Down” (D): a word like $RRDRDRRD$. The number of paths is therefore the number of anagrams of this word, i.e. the number of ways to choose which $3$ of the $8$ steps are “Down”: $N = \binom{8}{3} = \frac{8\cdot 7\cdot 6}{6} = \boxed{56}.$