A city has 4 roads running east-west and 4 running north-south, forming a grid. A person at the north-west corner A walks to the south-east corner B, at each intersection moving only east or south. How many different routes are there?

Step-by-step solution

1. 1

   Count the moves each route must make. With $4$ roads in each direction there are $3$ blocks in each direction, so every route consists of exactly

   $3\ \text{east moves}\quad\text{and}\quad 3\ \text{south moves}$

   for a total of $6$ moves — and this is the same for every route, which is what makes the count a pure combinatorial one.

2. 2

   Turn a route into a word. A route is completely described by the order of its moves, i.e. by a string of $6$ letters, three E's and three S's, such as $EESESS$. Different strings give different routes and every route gives a string, so counting routes = counting strings.

3. 3

   Choose the positions of the east moves. Once you decide which $3$ of the $6$ positions carry an E, the S's fill the rest. The number of ways is

   $\binom{6}{3}$

4. 4

   Evaluate the binomial coefficient.

   $\binom{6}{3}=\frac{6!}{3!\,3!}=\frac{6\cdot 5\cdot 4}{3\cdot 2\cdot 1}=20$

   $\boxed{20\ \text{routes}}$

5. 5

   Cross-check with Pascal's triangle on the grid. Label each intersection with the number of routes reaching it from $A$: the top row and left column are all $1$, and every other node is the sum of the node above and the node to its left. This builds the rows $1,1,1,1$ / $1,2,3,4$ / $1,3,6,10$ / $1,4,10,20$ — and the corner $B$ carries $20$ ✓, matching the binomial count.