Associated Topics || Dr. Math Home || Search Dr. Math

### Possible Paths across a Rectangular Grid

```Date: 02/16/2005 at 21:59:13
From: Wenying
Subject: How many different paths from A to B are possible?

Consider a grid that has 3 rows of 4 squares in each row with the
lower left corner named A and upper right corner named B.

Suppose that starting at point A you can go one step up or one step to
the right at each move.  This is continued until the point B is
reached.  How many different paths from A to B are possible?

I thought about using a tree diagram starting from point A.  From
point A there are 2 ways to reach the points up and to the right.  So
I multiply 2 when I reach each point.  I don't know how to continue
from the upper left and lower right corners.

```

```
Date: 02/17/2005 at 14:43:17
From: Doctor Ricky
Subject: Re: How many different paths from A to B are possible?

Hi Wenying,

Thanks for writing Dr. Math!

_____________________________________ B
|        |        |        |        |
|________|________|________|________|
|        |        |        |        |
|________|________|________|________|
|        |        |        |        |
|________|________|________|________|
A

Now let's look at some sample paths we can figure out by inspection.

If we start at A and move towards B, we find we can follow the path

RRRRUUU

(where R = Right one unit, U = Up one unit),

UUURRRR,
RURURUR,
RRUUURR,

and so on.

By analyzing our good routes, we see that every good route consists of
seven moves and we have four R moves and three U moves.  We can use
this to generalize a formula to find the number of possible routes.

Since as we've shown, order does not matter in our paths (we can have
an R in any place of our 7 moves), we can use our combination formula:

n!
C(n,r) = -----------
r!*(n-r)!

The number of how many good routes we have can be found by finding how
many combinations of 4 R's we can have in our 7 moves, so we want to
calculate:

7!
C(7,4) = -----------
4!*(7-4)!

You can see that since there have to be 4 R's, there must be 3 U's, so
you can also use the combination formula to find how many different
combinations of 7 moves with 3 U's there are, and you will end up with
the exact same result.

This is because we only have two choices for moves: right and up.  If
we had more choices, this equality might not hold true.  Since we only
have two possible moves, it does.

I hope this helps!  If you have any more questions or concerns, feel
free to write back.

- Doctor Ricky, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search