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/