Associated Topics || Dr. Math Home || Search Dr. Math

### 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?

```
Associated Topics:
High School Discrete Mathematics

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search