The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
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!

Going from your description, your diagram looks like this:

             _____________________________________ B
             |        |        |        |        |
             |        |        |        |        |
             |        |        |        |        |

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


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


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:

  C(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

  C(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 
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

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.