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 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....

I first verified your answer by using the old Pascal's triangle 
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

[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/