Number of Ways to MoveDate: 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? |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/