Starting at the top-left corner of a grid, you may move only one step right or one step down at a time.

There are 6 such routes through a $2\times 2$ grid.

How many routes are there through a $20\times 20$ grid?

Hints

Open one at a time

Every route uses the same number of right and down moves.

Choose which positions in the move sequence are right moves.

Solution

Best opened after a real attempt

Encode a path as a word

Every valid route consists of exactly 20 right moves and 20 down moves, in some order. So each route is a length-40 word containing 20 copies of $R$ and 20 copies of $D$.

Choose the 20 positions occupied by the right moves:

$$(\genfrac{}{}{0ex}{}{40}{20})=\frac{40!}{20!20!}=\mathrm{137,846,528,820.}$$

The picture suggests exploration; the move sequence reveals a standard combinatorial object.