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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.