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

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+mC_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(n-1, m, path + "right")
   end

   if m > 0
      printPath(n, m-1, 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 [(n-m+1)/(n+1)] * ^n+mC_m. For n = m, this simplifies to [1/(n+1)] * ²ⁿ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+mC_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 n-x right and m-y up moves to reach (n,m). If we flip the n-x right to n-x up and m-y up to right, then starting from point (x,y), we will reach the point (x+m-y,y+n-x). Setting y = x+1, we get that the resulting end point is (m-1,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 (m-1,n+1). So the total number of paths that cross the diagonal must be the total number of paths from (0,0) to (m-1,n+1). This is ^n+mC_m-1.

So the desired number is = ^n+mC_m - ^n+mC_m-1  = [(n-m+1)/(n+1)] * ^n+mC_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 (p-q)/(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 (n-m)/(n+m). So the number of monotonic paths that are below the diagonal (do not even touch) is [(n-m)/(n+m)] * ^n+mC_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+1-m)/(n+1+m)] * ^n+m+1C_m = [(n-m+1)/(n+1)] * ^n+mC_m.

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

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 n-r right moves and m-r up moves apart from r diagonal moves to reach (n,m). The number of ways, we can do this is = (n+m-r)! / [ (n-r)! * (m-r)! * 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+m-r)! / [(n-r)!*(m-r)!*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 (n-1,m) by a right move, from (n,m-1) by a up move, and from (n-1,m-1) by a diagonal move. These are the only three atomic steps. So, D(n,m) = D(n-1,m) + D(n,m-1) + D(n-1,m-1) 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(n-1, m, path + "right")
   end

   if m > 0
      printPath(n, m-1, path + "up")
   end

   if n > 0 and m > 0
      printPath(n-1, m-1, 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