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
_____________________________________________

Finding Pathways


Date: 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/   
    
Associated Topics:
High School Discrete Mathematics

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/