Number of Ways to Move

Date: 1/30/96 at 21:33:23
From: Anonymous
Subject: Permutations?

I have a group of squares which together form a larger square, i.e. a 
square that is 8 squares by 8 squares.

In how many ways can you travel from the upper left corner of the 
large square to the lower right corner by only going down or to the 
right? 

Also, in how many ways can you do the same thing with a square 
that is N x N, where N is any whole number? Thanks in advance.

             Doug Seaman

Date: 6/17/96 at 9:51:48
From: Doctor Robert
Subject: Re: Permutations?

In order to solve this problem, you need to start with a simple 
problem and then work your way to a harder one.  

Let's start with a 2 by 2  matrix, that is, a square made up of 4 unit 
squares.  Now to get from  the upper left square to the bottom right 
is going to require one move  to the right and one move down.  The 
question is, "How many ways can I  do that?"  

Let us represent a move to the right by x and a move down by  y.  
Then there are two ways to complete the process: either xy or yx. 

What about a 3 by 3 arrangment?  You will need two horizontal 
moves and  two vertical moves, that is, you need 2 x's and 2 y's.  
Let's list the  number of ways you could complete the problem:

xxyy  xyxy  xyyx  yxyx  yxxy  yyxx   - a total of six ways.

Now this problem is very similar to the one where you arrange 
letters in  a word and have repeating letters.  For the 3 by 3 
arrangment you have a  total of 4 letters (2 x's and 2 y's) but each of 
these is repeated, so that the number of ways they can be arranged is 
4!/(2!2!) = 6  where the "!" stands for factorial.  

In a 4 by 4 arrangement, the number of  possible moves would be 
6!/(3!3!) = 20.  

In the 8 by 8 arrangement (a  checkerboard) you asked about, the 
number of moves would be 14!(7!7!) = 3432.  In general, for an 
n x n arrangement there would be  [(n-1)+ (n-1)]!/[(n-1)!(n-1)!].  
This can be simplified a bit to give  [2n-2]!/[(n-1)!]^2.

-Doctor Robert,  The Math Forum

Date: Tue, 9 Sep 1997 23:53:04 -0400 (EDT)
From: Wallace Jordan
Subject: Comment about different number of paths

This isn't really a question... just a comment. 

Draw the grid, and write at each intersection the number of ways to 
get to that intersection. For example, you would write a "1" at the 
upper left corner, a 1 at the points below and to the right of it, etc. 
When you're done, you'll see the pattern: it's Pascal's Triangle! 
If you rotate the grid to the right, then the numbers you have 
written will form Pascal's Triangle; from this fact, it is easy to 
use the binomial theorem to determine a formula for an N X N 
grid. The number of possible paths is thus:

      (2n)!
      -----
      (n!)^2

Pretty cool, eh?