|
|
Counting Possible Paths
Date: 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. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/
