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/