Routes

C

Courtneyb022

New member
Joined
Feb 1, 2011
Messages
10
Suppose the lines in the square grid below represent streets in a neighborhood of a city and the individual squares represent city blocks. You are at the southwest corner and you need to walk to the northeast corner. You can only walk north or east.

How many different routes are there for you to choose from?

What is the formula for an n x n square grid?
 
Please don't post a problem with no work. It's hard to see the picture, too.

RBGTHGANH
 
Um, Ok.....

I have tried the problem and have only come up with 37 possibilities. A 1x1 square grid has 2 possibilities, a 2x2 square grid has 6 possibilities, and a 3x3 square grid has 20 possibilities. I can't find a formula that would allow me to know that I have the 4x4 square grid answer right...
 
Courtneyb022 said:
I have tried the problem and have only come up with 37 possibilities. A 1x1 square grid has 2 possibilities, a 2x2 square grid has 6 possibilities, and a 3x3 square grid has 20 possibilities. I can't find a formula that would allow me to know that I have the 4x4 square grid answer right...
Click to expand...
Courtney, don't you mean 1x1 = 0, 2x2 = 2, 3x3 = 6 and 4by4 = 20?
A 1x1 only has 1 square, so you can't move!
Label the 2x2 this way:
3 4
1 2
Ways are 1-2-4 and 1-3-4

Am my wrong?
If so, show me your 6 possibilities here...

And what do you mean by 37? You list 2+6+20 = 28...
 
Let the southwest corner be (0,0).

There are \(\displaystyle \binom{2n}{n}=\frac{(2n)!}{(n!)^{2}}\) paths from (0,0) to (n,n).

Google Catalan numbers and you will find something about it.
 
No Denis....
You are starting in the southwest corner and you are wanting to get to the northeast corner, you can either go up north and then east or east first then go north..........
 
Courtneyb022 said:
No Denis....
You are starting in the southwest corner and you are wanting to get to the northeast corner, you can either go up north and then east or east first then go north..........
Click to expand...
3 4
1 2
Ways are 1-2-4 and 1-3-4

BUT isn't that what I'm showing above?
"starting in the southwest corner" means from position 1
go east: that's to position 2
go north: that's to position 4 (northeast corner)
so path is 1-2-4

WHAT am I missing?
 
galactus said:
Let the southwest corner be (0,0).

There are \(\displaystyle \binom{2n}{n}=\frac{(2n)!}{(n!)^{2}}\) paths from (0,0) to (n,n).

Google Catalan numbers and you will find something about it.
Click to expand...
Kinda agree, galactus: and it's sequence A000984 at Sloane's integer sequences site.
BUT n=0 gives 1 and n=1 gives 2 : how can that be? What am I missing?
 
Ok, you have a 1x1 square grid you have 2 possibilities to get to the northeast corner.
You have a 2x2 square grid, you have 6 possibilities to get to the northeast corner.
You have a 3x3 square grid, you have 20 possibilities to get to the northeast corner.
You have a 4x4 square grid, you have ___ possibilities to get to the northeast corner.
I think the 4x4 square grid had 37 possibilities to get the the northeast corner, but I am not exactly sure. I'm thinking it might be more. I know there are at least 20 possibilities allready since the 3x3 square grid fits into the 4x4 square grid.

I think galactus is in the right ballpark on the formula, in my class we are learning about factorials, nCr, nPr, etc.
I still just don't know exactly how to find out if my answer for a 4x4 square grid is correct.
 
n=0, I suppose is the point itself and is a rather 'by defintion' case. Because 0!=1.

n=1 is one square. Go to the right or go to the left for the two ways.

For a 4-by-4: \(\displaystyle \binom{8}{4}=70\) ways.
 
You must log in or register to reply here.
Top