## Random Routes

#### Problem

Starting in the top left corner and moving right and down, there are exactly six routes to the bottom right corner of a 2 × 2 grid.

How many different routes can you find through a 4 × 4 grid?

#### Solution

Consider the diagram.

Each number on the grid represents the number of routes to that node (intersection point on the grid).

For example, consider the node which has 15 routes to it on the bottom row. As there are 10 routes to the node above it and 5 routes to the node on its the right, there are 10 + 5 = 15 routes to it in total. In the same way, each of the other values have been calculated and it becomes apparent that the total number of different routes through a 4 4 grid is 70.

How many routes are there through a 10 10 grid?

What about an `n` `n` grid?

Problem ID: 172 (May 2004) Difficulty: 2 Star