Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/ 
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-2013 The Math Forum
http://mathforum.org/dr.math/