Finding PathwaysDate: 04/08/99 at 04:33:07 From: Sarah Gillen Subject: Finding pathways How do you find how many pathways there are on a square when there are three lines going across each way; from point A to point B (from top to bottom)? Thank you. Date: 04/08/99 at 13:17:48 From: Doctor Peterson Subject: Re: geogmetry; finding pathways Hi, Sarah. I'll fill in some details you left out, and assume that you are given a picture like this: A o----o----o | | | | | | o----o----o | | | | | | o----o----o B and you want to know how many ways there are to get from A to B, always going left to right or top to bottom. Let's number the points to make it easier to discuss: A 1----2----3 | | | | | | 4----5----6 | | | | | | 7----8----9 B Starting at A=1, you have two choices, 2 or 4, so the possible paths so far are: 1-2 1-4 From 2, there are two choices, 3 or 5; from 4, there are two choices, 5 or 7: 1-2-3 1-2-5 1-4-5 1-4-7 From 3 or 7, there are no more choices; you're forced to go one way. From 5, you have two choices. So here are all the possible paths: 1-2-3-6-9 1-2-5-6-9 1-2-5-8-9 1-4-5-6-9 1-4-5-8-9 1-4-7-8-9 If I got the constraints wrong, and you need all possible paths that don't cross, or something like that, then you can use the same basic idea to solve the real problem. Another method that can be useful in problems like this is to write at each point the number of ways to get to it. If there are two places from which you can get to the same point, this number will be the sum of the number of ways to get to each of those points. Here's what it looks like for this problem: A 1----1----1 | | | | | | 1----2----3 | | | | | | 1----3----6 B Can you follow that? The 3 at what I called point 8 is the sum of the 1 at point 7 and the 2 at point 5, for example. - Doctor Peterson, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/