July 21, 2012

Number of Paths in a Rectangular Grid

Problem 1: Consider a rectangular grid of n x m rectangular cells. The problem is to find the number of shortest (or monotonic in this case) paths along the edges of the cell that start at (0,0) and end at (n,m). How do we print all such paths?

A monotonic path consists of moving up or right but not down or left. Figure 1 illustrates such a path for a grid of size 5 x 3.

Figure 1
Solution: show

Problem 2: Now we need to print all monotonic paths that do not go above the diagonal y = x. Figure 2 shows such a path. Note that the path in figure 1 goes above the diagonal, hence not desirable in this case. How many such paths exist for n x m grid (n >= m)?

Figure 2
Solution: show

Problem 3: Now let us consider that apart from up and right moves we can take up-right (diagonal) moves. Figure 3 shows such a path. How many such paths exist for n x m grid?

Figure 3
Solution: show

6 comments:

  1. Quite interesting problems.
    I was trying to solve a little variation of problem 2 here, what if we cut off a rectangular portion say of size a*b from top left corner. Then how many ways are there to go to (m,n) from (0,0).

    ReplyDelete

  2. Brilliant stuff... great linkages and completely thorough flow of content...feels so good to find such well written material on blogs.

    regards from bartender

    ReplyDelete
  3. Solution for case three must be = (n+m-r)!/(n-r)!(m-r)!r! Total moves is not (n+m) as for every diagonal move u take it gets reduced by 1.

    ReplyDelete
  4. Super! Thank you very much!
    Just one note: the answer for the rectangle grid of 2 x 2 is 2,
    so the formula is not (n+m)Cm, but (n+m-2)C(m-1), correct?

    ReplyDelete
  5. no. (n+m)Cm is correct as the grid starts from (0,0) and not (1,1).

    ReplyDelete
  6. O-os, sorry, you are right, what I meant by 2x2 (::) is actualy grid 1x1 :-)

    ReplyDelete