Thread: possibilities

Imagine a city grid that is like a rectangular coordinate system. You are currently at (0,0) and you want to get to corner (3,4). If a path consists of a series of eastward and northward moves, how many shortest paths are possible assuming that all streets and avenues are of the same length?

Help pls, I don't have any idea on how to solve this one. btw the answer is 35 paths.

-tnx

Originally Posted by ihmth

Imagine a city grid that is like a rectangular coordinate system. You are currently at (0,0) and you want to get to corner (3,4). If a path consists of a series of eastward and northward moves, how many shortest paths are possible assuming that all streets and avenues are of the same length?
btw the answer is 35 paths.

How many ways can you rearrange this string "NNNNEEE"?

I suppose this will work. Have you heard of the Catalan numbers?.

The number of ways to go from (0,0) to (n,n) is given by C(2n,n)

The number of ways to go from (0,0) to (n-1,n+1) is C(2n,n-1)

Let n=3, and we have the path from (0,0) to (3,3) and from (0,0) to

(2,4). This is the same as the paths from (0,0) to (3,4)

C(6,3)+C(6,2)=35

The is a 1-1 correspondence for the paths from (0,0) to (n,n) that go above the main diagonal and the paths from (0,0) to (n-1,n+1).