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
To go from (0,0) to (n,m), we need to make n moves to the right and m moves up. These moves can be performed in any order and still we reach the point (n,m). So the total number of ways is simply the total number of ways n red balls and m green balls can be arranged in a straight line. This is simply
^{n+m}C
_{m}.
We can print all such paths using recursion. The following code does this.
Function printPath(n, m, path)
if n == 0 and m == 0
print path
return
end
if n > 0
printPath(n1, m, path + "right")
end
if m > 0
printPath(n, m1, path + "up")
end
end
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
Let us first discuss how to print all monotonic paths that do not go above the diagonal. In order for a path to be valid, at all points (x,y) on the path, y should be less than or equal to x. We can simply ensure this constraint while printing paths, using the following code.
Function printPath(x, y, n, m, path)
if x == n and y == m:
print path
return
end
if x < n
printPath(x+1, y, n, m, path + "right")
end
if y < m and y < x
printPath(x, y+1, n, m, path + "up")
end
end
The total number of such paths are [(nm+1)/(n+1)] *
^{n+m}C
_{m}. For n = m, this simplifies to [1/(n+1)] *
^{2n}C
_{n} which is known as
Catalan number. The wiki page also contains other interesting problems that have Catalan number as their solution.
Now, In order to obtain the number of paths, we need to subtract the number of paths that cross the diagonal from the total number of paths
^{n+m}C
_{m}.
Consider a path that crosses the diagonal. Let that path cross the diagonal for the first time at point (x,y). Since this is the first point after crossing the diagonal, so y should be equal to x+1. So the path has taken x right and y up moves. It is yet to take nx right and my up moves to reach (n,m). If we flip the nx right to nx up and my up to right, then starting from point (x,y), we will reach the point (x+my,y+nx). Setting y = x+1, we get that the resulting end point is (m1,n+1). Since m <= n, the resulting end point is above the diagonal. So we can do surgery on all paths that cross the diagonal to make them reach (m1,n+1). So the total number of paths that cross the diagonal must be the total number of paths from (0,0) to (m1,n+1). This is
^{n+m}C
_{m1}.
So the desired number is =
^{n+m}C
_{m} 
^{n+m}C
_{m1 } = [(nm+1)/(n+1)] *
^{n+m}C
_{m}. This is a proof based on
Andre's reflection method.
Alternately:
Andre's reflection method was used to originally solve a very interesting problem called Ballot problem. The ballot problem states that in a two candidate election, candidate A polled p votes and candidate B polled q votes (p > q). What is the probability that candidate A was leading over candidate B throughout the counting.
Well the probability is simply (pq)/(p+q).
We can use the Ballot theorem to find the number of monotonic paths below the diagonal (that do not even touch the diagonal). We can assume right move to be candidate A and up move to be candidate B and the two polled n,m votes respectively. So the probability of number of right leading number of up is (nm)/(n+m). So the number of monotonic paths that are below the diagonal (do not even touch) is [(nm)/(n+m)] *
^{n+m}C
_{m}.
Now since we are allowed to touch the diagonal, we can assume instead going to (n+1,m). This is because the first two moves would be right moves (otherwise we might touch the diagonal). Then we eliminate the first right move and allow a diagonal touch. So the total number of ways is [(n+1m)/(n+1+m)] *
^{n+m+1}C
_{m} = [(nm+1)/(n+1)] *
^{n+m}C
_{m}.
Problem 3: Now let us consider that apart from up and right moves we can take upright (diagonal) moves. Figure 3 shows such a path. How many such paths exist for n x m grid?

Figure 3 
Solution:
show
This problem is similar to problem 1, except that paths can contain diagonal moves. One diagonal move consumes 1 right and 1 up move.
So let us assume that we make r diagonal moves, where r <= min(n,m). In this case, we need to make nr right moves and mr up moves apart from r diagonal moves to reach (n,m). The number of ways, we can do this is = (n+mr)! / [ (nr)! * (mr)! * r! ]. If we set r = 0, then we get the solution to problem 1. But in this case r can go from 0 to min(m,n). So the total number of ways is =
Sum_r (n+mr)! / [(nr)!*(mr)!*r!], where r in [0, min(m,n)]
Alternately, we can derive the recurrence relation for the total number of paths. Let D(n,m) be the total number of paths from (0,0) to (n,m) with up, right and diagonal moves. Clearly, we can reach (n,m) from (n1,m) by a right move, from (n,m1) by a up move, and from (n1,m1) by a diagonal move. These are the only three atomic steps. So, D(n,m) = D(n1,m) + D(n,m1) + D(n1,m1) for n,m > 0. D is called as
Delannoy number.
The code to print all paths has a small addition to the code for problem 1.
Function printPath(n, m, path)
if n == 0 and m == 0
print path
return
end
if n > 0
printPath(n1, m, path + "right")
end
if m > 0
printPath(n, m1, path + "up")
end
if n > 0 and m > 0
printPath(n1, m1, path + "diagonal")
end
end
We can extend this problem further by asking the number of paths that do not cross the diagonal (same constraint as problem 2). The number of paths in this case is called
Schroder number.
Source Code:
grid_paths.py
Quite interesting problems.
ReplyDeleteI 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).
ReplyDeleteBrilliant stuff... great linkages and completely thorough flow of content...feels so good to find such well written material on blogs.
regards from bartender
Solution for case three must be = (n+mr)!/(nr)!(mr)!r! Total moves is not (n+m) as for every diagonal move u take it gets reduced by 1.
ReplyDeleteSuper! Thank you very much!
ReplyDeleteJust one note: the answer for the rectangle grid of 2 x 2 is 2,
so the formula is not (n+m)Cm, but (n+m2)C(m1), correct?
no. (n+m)Cm is correct as the grid starts from (0,0) and not (1,1).
ReplyDeleteOos, sorry, you are right, what I meant by 2x2 (::) is actualy grid 1x1 :)
ReplyDelete