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
Math Forum Home || Math Library || Quick Reference || Math Forum Search