Possible Paths across a Rectangular Grid

Problem:
Consider a rectangular grid of 4×3 with lower  left corner named as A and upper right corner named B. Suppose that starting point is A and you can move one step up(U) or one step right(R) only. This is continued until B is reached. How many different paths from A to B possible ?

Rectangular Grid

Now let’s look at some sample paths we can figure out by inspection.

If we start at A and move towards B, we find we can follow the path

RRRUU

(where R = Right one unit, U = Up one unit),

UURRR,
RURUR,
RRUUR,

and so on.

By analyzing our good routes, we see that every good route consists of 5 moves and we have 3 R moves and 2 U moves. We canuse this to generalize a formula to find the number of possible routes.

Since as we’ve shown, order does not matter in our paths (we can have an R in any place of our 5 moves), we can use our combination formula:

C(N,R) = N!/(N-R)! * R!

The number of how many good routes we have can be found by finding how many combinations of 3 R’s we can have in our 5 moves, so we want to calculate:

C(5,3) = 5!/(5-3)! * 2! = 10

If you want programming solution of above problem, see this.

2 Thoughts on “Possible Paths across a Rectangular Grid

  1. Fabio Strada on February 5, 2015 at 7:34 am said:

    C(5,3) = 5!/ ( (5-3)! * 3! ) = 10

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation