# Number of routes

• January 11th 2009, 10:53 AM
chiph588@
Number of routes
How many routes are there from the lower left corner to the upper right corner of an m*n grid if we are restricted to traveling only to the right or up? For example, in a 1*1 grid,
only two routes exist : right,up or up,right.
• January 11th 2009, 12:30 PM
Plato
Quote:

Originally Posted by chiph588@
How many routes are there from the lower left corner to the upper right corner of an m*n grid if we are restricted to traveling only to the right or up? For example, in a 1*1 grid,
only two routes exist : right,up or up,right.

Let U stand for moving up one grid mark and R is right one.
Now to make the trip we must use m R's and n U's.
$\underbrace {RRR \cdots RR}_m\underbrace {UUU \cdots UU}_n$, how many ways can we rearrange that string?
• January 11th 2009, 01:43 PM
chiph588@
Quote:

Originally Posted by Plato
Let U stand for moving up one grid mark and R is right one.
Now to make the trip we must use m R's and n U's.
$\underbrace {RRR \cdots RR}_m\underbrace {UUU \cdots UU}_n$, how many ways can we rearrange that string?

would it be $mn+1$?
• January 11th 2009, 01:53 PM
Plato
Quote:

Originally Posted by chiph588@
would it be $mn+1$?

NO indeed!
It is an arrangement with repetitions.
$\frac{{\left( {m + n} \right)!}}
{{\left( {m!} \right)\left( {n!} \right)}}
$