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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.