Number of routes

**chiph588@** · January 11th 2009, 10:53 AM

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.

**Plato** · January 11th 2009, 12:30 PM

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?

**chiph588@** · January 11th 2009, 01:43 PM

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$ ?

**Plato** · January 11th 2009, 01:53 PM

Originally Posted by chiph588@

would it be $mn+1$ ?

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

Thread: Number of routes

LinkBack

Thread Tools

Display

Number of routes

Similar Math Help Forum Discussions

Differentiate with routes

Probability problem involving routes.

choosing possible routes home

Squares and routes

Number Theory type of problem--need help understanding number relationships. yikes.

Search Tags