# Routes

#### Courtneyb022

##### New member
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
Please don't post a problem with no work. It's hard to see the picture, too.

RBGTHGANH

#### Courtneyb022

##### New member
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
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
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
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
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
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
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
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
No.....You guys are all wrong.............