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
_____________________________________________

Path Possibilities


Date: 10/24/1999 at 14:06:20
From: Roger
Subject: Path Possibilities

I have counted and calculated so many times and I'm still baffled. How 
many combinations of moves are there to get from point A to point B 
in the figure below, assuming that you can only move right and up? 
Also assume you are on the corners and not the lines. Point A is the 
very lower left corner, and B is the very upper right corner.

        _ _ _ _ B
       |_|_|_|_|
       |_|_|_|_|
       |_|_|_|_|
    _ _|_|_|_|_|
   |_|_|
  _|_|_|
 |_|
A

I know that if you take the number of possibilities of each set of 
squares and multiply them, then you get the solution. The small square 
has 2 possibilities. The second set of squares I think has 6. That is 
where I get lost. Thanks for your time!

Roger


Date: 10/24/1999 at 16:22:23
From: Doctor Anthony
Subject: Re: Path Possibilities

Call a horizontal step H and a vertical step V.

For the first stage you must take one of each, and you can arrange 
the letters H, V in two ways.

For the second stage you must do 2 H's and 2 V's. You can arrange 
these four letters in

       4!
     ----- = C(4,2) = 6 ways
     2! 2!

For the third stage you must do 4 H's and 4 V's. These eight letters 
can be arranged in

       8!
     ----- = C(8,4) = 70 ways
     4! 4!

Therefore the total number of different paths is 

     2 x 6 x 70 = 840

- Doctor Anthony, 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/