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 | | | | | |________|________|________|________| | | | | | |________|________|________|________| | | | | | |________|________|________|________| 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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.