Counting Paths on a Grid

Date: 08/21/2006 at 16:57:54
From: Luis
Subject: How many paths are possible on a grid containing 4 X 5 rows

On a 4 x 5 grid that contains 20 squares, how many possible routes are
there to go from one corner (A) to the opposite corner (B)?

Date: 08/21/2006 at 17:40:48
From: Doctor Philip
Subject: Re: How many paths are possible on a grid containing 4 X 5 rows

Hi, Luis.

This problem is made considerably easier if you know some
combinatorics.  If you aren't familiar with that idea, you can read an
introduction here:

  Combinations and Permutations 
    http://mathforum.org/dr.math/faq/faq.comb.perm.html 

I will assume corner A is at the bottom left and corner B is at the
top right, and that you can only walk east (right) and north (up).

Every route from A to B covers 9 blocks of which 5 MUST be east.  The
number of ways to choose which 5 of the 9 blocks are to be east is 
9C5 = 126.  You can also reason that 4 of the blocks MUST be north,
and you will get the same answer: 9C4 = 126.  The reason this is a
combination as opposed to a permutation is because the order does NOT
matter (i.e., it doesn't matter which of the 5 east routes you choose
first--as long as you set the 5 and then use north routes for the
remaining roads).

Another way to approach the problem is to write out one possible
route: EEEEENNNN. Where E means you go east, and N means you go north.
Other routes can be symbolized by other 9-letter "words" having 5
E's and 4 N's.  The total number of these "words" is 9!/(5!*4!) = 126.

Either way, you get a possible 126 routes.

If you need any more help with this problem, please feel free to write
back and I will try to offer some more suggestions.

- Doctor Philip, The Math Forum
  http://mathforum.org/dr.math/