The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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 

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 
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- The Math Forum at NCTM. All rights reserved.