Associated Topics || Dr. Math Home || Search Dr. Math

### Counting Paths With Factorials

```Date: 07/24/2002 at 21:51:04
From: Jeremy Lau
Subject: Number of ways to move from point A to B using factorials

Hi,

I want to solve a problem using factorials instead of labelling using
Pascal's Triangle.

The question:

How many possible ways are there to get from point A to point B.

A  ___________
|  |  |  |  |
|__|__|__|__|
|  |  |  |  |
|__|__|__|__|________
|  |  |  |  |  |  |  |
|__|__|__|__|__|__|__|
|  |  |  |  |  |  |  |
|__|__|__|__|__|__|__|
|  |  |  |  |  |
|__|__|__|__|__|
B

I've solved it using Pascal's Triangle (the number of possible routes
moving from point A to point B is 690). I want to solve it with
factorials, i.e. x!/y!...  I think I am stuck with splitting the
figures up because if you do so, there will be too many squares that
share a side.

I've been told that it is possible to solve it using factorials.
Thanks!

-Jeremy Lau
```

```
Date: 07/25/2002 at 02:40:51
From: Doctor Greenie
Subject: Re: Number of ways to move from point A to B using Factorials

Hello, Jeremy --

I'm not sure what you mean by solving this using factorials.  It can
be solved with repeated use of the concept of 'n choose r', which
involves factorials....

method. Then I tried several different ways to come up with that same
answer; most of these ways involved starting with the total number of
ways to make the trip if the missing corner squares were NOT missing
(C(12,5) and counting the number of paths that can't be used because
they ARE missing. All of these approaches proved too awkward.

Then I finally hit upon a relatively simple solution using C(n,r).

If you analyze your figure carefully, you will see that every
solution path must go through exactly one of the three points which I
have labeled in the diagram below as X, Y, and Z:

A  ___________
|  |  |  |  |
|__|__|__|__|
|  |  |  |  |
|__|__|__|__|________
|  |  |  | X|  |  |  |
|__|__|__|__|__|__|__|
|  |  | Y|  |  |  |  |
|__|__|__|__|__|__|__|
Z|  |  |  |  |  |
|__|__|__|__|__|
B

This fact makes counting the paths relatively easy:

The number of paths through X is the number of paths from A to X
times the number of paths from X to B:

C(6,2)*C(6,3) = 15*20 = 300

The number of paths through Y is the number of paths from A to Y
times the number of paths from Y to B:

C(6,3)*C(6,2) = 20*15 = 300

The number of paths through Z is the number of paths from A to Z
times the number of paths from Z to B:

C(6,2)*C(6,1) = 15*6 = 90

The total number of paths is 300+300+90 = 690.

Perhaps this is something like what you had in mind...?  If not, you
might want to take a look at this answer from the Dr. Math archives:

Counting Possible Paths
http://mathforum.org/library/drmath/view/60784.html

which shows other approaches to this kind of problem.

- Doctor Greenie, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 07/25/2002 at 21:49:10
From: Jeremy Lau
Subject: Thank you

Wow! That's what I was looking for! The concept seemed pretty
straightforward once I realized what you did. Thanks for your help!

-Jeremy Lau
```

```
Date: 07/26/2002 at 01:31:01
From: Doctor Greenie
Subject: Re: Thank you

You are most welcome, Jeremy.

Thanks for taking the time to send your note of thanks, and thanks for
sending an interesting problem that gave me some good and enjoyable
mental exercise!

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