Paths on a Grid

Paths on a Grid

Below is an 8 by 8 grid. Point A is on the square at the top left corner, and point B is on the square of the bottom right corner.

If you can only move down and to the right, how many different paths exist between A and B? Here are three of the possible paths as example;

Let's have a closer look at these paths:

• How many right moves and how many down moves are there in each path?
• Does the order of these right and down moves make any difference for reaching point B?

Try drawing more paths as needed:

In fact, every successful path for an 8x8 grid will involve exactly 7 moves down and 7 moves to the right. The number of decisions to select the right or the down path to go will determine the total number of paths.

A Solution Using Pascal's Triangle

On the other, you may want to study this problem by creating smaller squares.

Let’s start with a 2x2 grid!

There is only one unique path from A to C. Likewise, there is only one path from A to D.

We may indicate this by placing a 1 in those squares.

Now we label B as the square in the second row and second column.

There are two unique paths from A to B, so we write 2 in this square.

We have filled the 2x2 square.

Now we can try a 3x3 square. We already knew about C,D, and F.

You can only form one path to E and H too.

Try to find the number of paths from A to G and A to I.

There are three paths for both and finally, we can look for to bottom left corner.

Let's find the total number of paths from A to B in a 3x3 square.

You may draw different sizes of squares and continue calculating the number of unique paths that lead to each square in the grid.

Use the canvas here to work on the smaller squares;

Fortunately, the pattern is quite familiar to us - Rows of Pascal Triangle!

A Solution Using Counting Techniques

Since all the paths must consist of a total of 14 moves, 7 down and 7 right, our job is to select the right move from the collection of 14 moves. You can draw smaller triangles and count the number of paths as a way to help see this pattern

We can use counting techniques to calculate how many different ways we can select this right move. You may be familiar with the notation $C(14,7).$ This a way to represent the number of ways to select 7 objects from a set of 14.

$C(14,7) = 3432$

14 Choose 7 = 3432

There are 3432 unique paths between A and B.

Extension

• Find out how many possible paths exist between A and B by only going right and down directions in a "n x n" square grid.
• Find out how many possible paths exist between A and B by only going right and down directions in a "n x m" rectangular grid.

Further Reading

Math Classroom by Computational Modelling