• Welcome! The new FreeMathHelp.com forum is live. We've moved from VB4 to Xenforo 2.1 as our underlying software. Hopefully you find the upgrade to be a positive change. Please feel free to reach out as issues arise -- things will be a little different, and minor issues will no doubt crop up.

Routes

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?
 

tkhunny

Moderator
Staff member
Joined
Apr 12, 2005
Messages
9,708
Please don't post a problem with no work. It's hard to see the picture, too.

RBGTHGANH
 

Courtneyb022

New member
Joined
Feb 1, 2011
Messages
10
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...
 

Denis

Senior Member
Joined
Feb 17, 2004
Messages
1,284
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...
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...
 

galactus

Super Moderator
Staff member
Joined
Sep 28, 2005
Messages
7,216
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.
 

Courtneyb022

New member
Joined
Feb 1, 2011
Messages
10
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..........
 

Denis

Senior Member
Joined
Feb 17, 2004
Messages
1,284
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..........
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?
 

Denis

Senior Member
Joined
Feb 17, 2004
Messages
1,284
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.
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?
 

Courtneyb022

New member
Joined
Feb 1, 2011
Messages
10
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.
 

galactus

Super Moderator
Staff member
Joined
Sep 28, 2005
Messages
7,216
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.
 

Courtneyb022

New member
Joined
Feb 1, 2011
Messages
10
No.....You guys are all wrong.............
 
Top