Counting Possible PathsDate: 05/30/2002 at 15:44:10 From: Tracy Subject: Number of pathways How do I find the number of pathways from A to B? I know the answer is supposed to be 200, but I can't figure it out. Please help! What is the formula and how do you use it? A .____.____.____. | | | | | | | | .____.____.____. | | | | | | | | .____.____.____.____.____. | | | | | | | | | | | | .____.____.____.____.____. | | | | | | | | .____.____.____. | | | | | | | | .____.____.____. B Date: 05/30/2002 at 16:49:04 From: Doctor Anthony Subject: Re: Number of pathways Let's add a couple of extra points, C and D: A .____.____.____. | | | | | | | | .____.____.____. | | | | | | | | .____.____.____.C___.____. | | | | | | | | | | | | .____.____.____.____.____. D | | | | | | | .____.____.____. | | | | | | | | .____.____.____. B Let H represent a horizontal step and V a vertical step. To go from A to C requires 3 H's and 2 V's. That is 5 steps, 3 alike of one kind and 2 alike of a second kind. 5! Number of paths A to C = ---- = 10 3!2! Similarly, the number of paths from A to D = 10. Also, 5! Number of paths from C to B = ------ = 10 2!3! Similarly, the number of paths from D to B = 10. Since every path has to go through C or D, paths from A to C to B = 10 x 10 = 100 " A " D " B = 10 x 10 = 100 --- total = 200 - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ Date: 05/30/2002 at 16:58:22 From: Doctor Peterson Subject: Re: Number of pathways Hi, Tracy. I'm assuming you are only allowed to go down and right, not to loop around. One nice way to approach this is to label each vertex with the number of ways to get there from A. A itself has a 1, because you start there; the two next to it each have 1, because you get there only by taking that one step. Any other vertex has the sum of the numbers above and to the left, since it can be reached from either direction, and each . Here's what we get for the left half: A 1____1____1____1 | | | | | | | | 1____2____3____4 | | | | | | | | 1____3____6___10____.____. | | | |D | | | | | | | | 1____4___10____.____.____. |C | | | | | | | .____.____.____. | | | | | | | | .____.____.____. B We could continue; but because of symmetry, you can see that there are likewise 10 ways to get from either of the middle vertices to B. That gives 10*10 ways to get from A to B via C, and 10*10 ways via D. In all: 200 ways! You may recognize the numbers we got as part of Pascal's Triangle. That gives another way to solve this without having to do our own counting. Or, you can use combinations: for example, to get to point C, you need to take 5 paths, of which 2 are right and 3 are down. The number of ways to choose 2 of the 5 (in order) to go right is C(5,2) = 10. For these ideas, see our FAQ: http://mathforum.org/dr.math/faq/faq.pascal.triangle.html http://mathforum.org/dr.math/faq/faq.comb.perm.html These methods are harder once you get past the bottleneck, or if you had a more complicated set of paths; the symmetry I pointed out is then a big help. But the labeling method works for any such problem. - Doctor Peterson, The Math Forum http://mathforum.org/dr.math/ Date: 05/30/2002 at 17:43:23 From: Tracy Subject: Number of pathways What if it isn't pretty and symmetrical like that one? A .____.____.____. | | | | | | | | .____.____.____.____.____. | | | | | | | | | | | | .____.____.____.____.____. | | | | | | | | | | | | .____.____.____.____.____. | | | | | | .____.____.B What if it's like this one? Date: 05/30/2002 at 18:49:19 From: Doctor Anthony Subject: Re: Number of pathways A .____.____.____. | | | | | | | | .____.____.____.C___.F___. | | | | | | | | | | | | .____.____.____.D___.G___. | | | | | | | | | | | | .____.____.____.E___.H___. | | | | | | .____.____.B Work out the paths A->C->F->B A->D->G->B A->E->B and add the three results. - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ Date: 05/31/2002 at 08:34:29 From: Doctor Peterson Subject: Re: Number of pathways Hi, Tracy. Just to supplement Dr. Anthony's answer, here's the work for my labeling method: A 1____1____1____1 | | | | | | | | 1____2____3____4____4____4 | | | | | | | | | | | | 1____3____6___10___14___18 | | | | | | | | | | | | 1____4___10___20___34___52 | | | | | | 20___54___106 B That takes very little thinking, and isn't much slower for small problems like this. - Doctor Peterson, The Math Forum http://mathforum.org/dr.math/ Date: 05/31/2002 at 10:27:51 From: Tracy Subject: Number of pathways A 1____1____1____1 | | | | | | | | 1____2____3____4____4____4 ------ How do you arrive at these last | | | | | | two 4s? The rest I understand. | | | | | | 1____3____6___10___14___18 | | | | | | | | | | | | 1____4___10___20___34___52 | | | | | | 20___54___106 B Date: 05/31/2002 at 10:47:25 From: Doctor Peterson Subject: Re: Number of pathways Hi, Tracy. Each number is the sum of the numbers above and to the left (the two places you can get there from). These two 4's have nothing above them, so they are just copied from the left, like the 1's at the top. Incidentally, the method equivalent to Dr. Anthony's suggestion in this case is to treat the three vertices in the middle (where the two rectangles meet) as a bottleneck, and calculate for each of those both how many ways there are to get there from A, and how many ways there are to get from there to B; then multiply for each and add them up: From A: To B: (adding numbers to right and below) A 1____1____1____1 | | | | | | | | 1____2____3____4 4____4____1 (Note that we don't include any | | | | | | line in both parts, to avoid | | | | | | counting any paths twice) 1____3____6___10 3____3____1 | | | | | | | | | | | | 1____4___10___20 3____2____1 | | | | | | 1____1____1 B Total ways: 4*4 + 10*3 + 20*3 = 16 + 30 + 60 = 106 Dr. Anthony's calculations give these same numbers without actually counting. Obviously you have to be pretty careful! - 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-2013 The Math Forum
http://mathforum.org/dr.math/