Rectangular Grid Walk

Grid walking describes a class of problems in which one counts the number of paths across a given grid, subject to certain restrictions. Most commonly, the restriction is that the only valid moves are those that approach the goal; in fact, this is so common that the term "grid-walking problems" almost invariably contains this restriction. Therefore, this restriction will always be assumed in all following sections, including the "No Restrictions" section.

Because of the finite-state nature of grid-walking problems, they are particularly suited to solutions from dynamic programming, and indeed many practical approaches are derived from or equivalent to performing a dynamic programming algorithm by hand.

Grid walking problems are important in their own right, but also because many combinatorical situations can be bijected to a grid-walking problem, thus immediately establishing their solution. For instance, putting \(m\) identical objects into \(n + 1\) distinct bins is equivalent to traversing an \(m \times n\) grid.

Consider the example problem:

Kelvin the Frog lives at the origin, and wishes to visit his friend at \((5,5)\). At any point, Kelvin the Frog can only hop 1 unit up or 1 unit to the right. How many paths are there from Kelvin to his friend?

In this instance, there are no restrictions other than the decreasing-distance condition (in this case that Kelvin can only move up and right).

There are two important ways to approach this problem. The first uses recursion, and the second uses a clever observation that applies to the no-restrictions variant of grid-walking (but not, in general, other cases).

Solution 1: Suppose Kelvin reaches the point \((m,n)\) at some point. Then Kelvin must have come from either \((m-1,n)\) or \((m, n-1)\) (since he can only hop up and right), meaning that

the number of paths to \((m,n)\) is the sum of the number of paths to \((m-1,n)\) and the number of paths to \((m,n-1)\).

Additionally, there is only 1 path to \((x,0)\) and to \((0,y)\) for any \((x,y)\). So we can fill in a table:

\(y=\) 5\(\hspace{10mm}\)	1	6	21	56	126	252
\(y=\) 4	1	5	15	35	70	126
\(y=\) 3	1	4	10	20	35	56
\(y=\) 2	1	3	6	10	15	21
\(y=\) 1	1	2	3	4	5	6
\(y=\) 0	1	1	1	1	1	1
	\(x=\) 0\(\hspace{10mm}\)	\(x=\) 1\(\hspace{10mm}\)	\(x=\) 2\(\hspace{10mm}\)	\(x=\) 3\(\hspace{10mm}\)	\(x=\) 4\(\hspace{10mm}\)	\(x=5\) \(\hspace{10mm}\)

so there are 252 possible paths. \(_\square\)

This strategy is clearly impractical for larger grids, but it has three main advantages:

• This strategy applies even in the face of additional restrictions, as later sections will show.
• It also applies to non-rectangular grids, and also when there are more moves available than just moving up/right (e.g. diagonally).
• It is very easy for computers to perform, using a straightforward dynamic programming algorithm.

Additionally, this strategy reveals something about the combinatorial underpinnings of the problem. Careful examination of the table found above reveals something interesting:

which strongly suggests that grid-walking is strongly related to binomial coefficients. In fact, there is a simple reason why:

Solution 2: To reach \((5,5)\), Kelvin must hop up 5 times and to the right 5 times. There are no other ways Kelvin could reach the destination. However, he may make those moves in any possible order, and each order corresponds to a different grid walk. From the theory of binomial coefficients, it follows that there are \(\binom{5+5}{5}=252\) possible paths. \(_\square\)

Suppose a particle is traveling from the bottom-left corner of an \(m \times n\) grid to the top-right corner, by making steps along the edges of the grid.

There are exactly \(\binom{m+n}{n}\) paths from the bottom-left corner to the top-right corner in an \(m \times n\) grid.

Commonly, a Cartesian plane is superimposed over the grid, so that the problem is equivalent to traveling from \((0, \, 0)\) to \((m, \, n)\).

Consider the alternative problem of creating a "word" (any string of letters) subject to certain constraints:

1. The word must have length \(m + n\).
2. The word must contain only 2 letters: R and U.
3. The word must contain \(m\) R's and \(n\) U's.

The answer to this problem is given by one of the definitions of binomial coefficients: there are \(\binom{m + n}{m} = \binom{m + n}{n}\) valid words.

Now, note that each word describes a grid walk in an \(m \times n\) grid, starting at the bottom-left corner:

1. Read the word normally, one letter at a time and from left to right.
2. Each time an R is read, move right \(1\) unit in the grid.
3. Each time a U is read, move up \(1\) unit in the grid.

Because the word contains \(m\) R's and \(n\) U's, the grid walk will end at the top-right corner when the word is finished. Each grid walk described in such a way is unique, since the first different letter in two words is seen as a fork between two paths. Any grid walk from the bottom-left corner to the top-right corner can be described in such a way, because a valid word may be created by writing R each time a move right is made and U each time a move up is made.

It follows that there are the same number of such grid walks as there are valid words. So there are \(\binom{m + n}{m}\) possible grid walks. \(_\square\)

And so it is true that the table of grid walk "numbers" is equal to a table of binomial coefficients. There are several combinatorial identities that can be derived from this realization, one of which is the hockey stick identity.

Consider a grid walk problem of dimensions \((m + 1) \times n\), starting at the origin and headed to \((m + 1, \, n)\).

Note that such a path must pass along an edge between the line \(x = m\) and the line \(x = m + 1\) at some point in time. Additionally, it must do so precisely once. Once the path reaches the line \(x = m + 1\), there is precisely one way to get to \((m + 1, \, n)\) (up and up and up). It follows that the sum of the grid walking "numbers" for \((m, \, 0)\) through \((m, \, n)\) must be the grid walking "number" for \((m, \, n)\). In other words,

The Hockey Stick Identity

\[\sum_{k = 0}^n \binom{m + k}{m} = \binom{m + n + 1}{m + 1}.\]

Recall the example problem:

Kelvin the Frog lives at the origin, and wishes to visit his friend at \((5,5)\). At any point, Kelvin the Frog can only hop 1 unit up or 1 unit to the right. How many paths are there from Kelvin to his friend?

Computers can solve such a problem in a rather straightforward manner. Here is some Python code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def dp(m, n, arr):
    if m == 0 or n == 0:
        return 1
    if m < 0 or n < 0:
        return 0
    if arr[m][n] != 0:
        return arr[m][n]
    arr[m][n] = dp(m-1, n, arr) + dp(m, n-1, arr)
    return arr[m][n]

m = 5
n = 5
arr = [0] * (m + 1)
for i in range(m + 1):
    arr[i] = [0] * (n + 1)
print(dp(m, n, arr))

But why is it useful to create such a program if it is only necessary to compute a binomial coefficient? Well, sometimes grid walking problems have further constraints, like evil monsters and inconvenient walls, or additional permitted actions, like steps taken diagonally up and to the right.

Kelvin the Frog lives at the origin, and wishes to visit his friend at \((5,5)\). However, an evil monster lives at \((2,2)\), so Kelvin cannot hop there. At any point, Kelvin the Frog can only hop 1 unit up or 1 unit to the right. How many paths are there from Kelvin to his friend?

There is not an immediate tractable mathematical solution, especially when there are many constraints. But for the program, only a minor modification is necessary to solve the problem:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def dp(m, n, arr):
    if m == 0 or n == 0:
        return 1
    if m == 2 and n == 2:
        return 0
    if m < 0 or n < 0:
        return 0
    if arr[m][n] != 0:
        return arr[m][n]
    arr[m][n] = dp(m-1, n, arr) + dp(m, n-1, arr)
    return arr[m][n]

m = 5
n = 5
arr = [0] * (m + 1)
for i in range(m + 1):
    arr[i] = [0] * (n + 1)
print(dp(m, n, arr))

How many paths can a king take from one corner of an \(8 \times 8\) chessboard to the opposite corner?

A king can move 1 square in any direction, including diagonally.

In this instance, the recursion is as follows:

The number of paths to \((m,n)\) is the sum of the number of paths to \((m-1,n)\), the number of paths to \((m,n-1)\), and the number of paths to \((m-1, n-1)\).

Solution.

Slight modification of the above program in accordance with the new recursive formula leads to

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

def dp(m, n, arr): if m == 0 or n == 0: return 1 if m < 0 or n < 0: return 0 if arr[m][n] != 0: return arr[m][n] arr[m][n] = dp(m-1, n, arr) + dp(m, n-1, arr) + dp(m-1, n-1, arr) return arr[m][n] m = 8 n = 8 arr = [0] * (m + 1) for i in range(m + 1): arr[i] = [0] * (n + 1) print(dp(m, n, arr))

The output yields the answer \(\boxed{265729}.\) \(_\square\)

There is also a mathematical framework for approaching these types of problems.

Kelvin the Frog lives at the origin, and wishes to visit his friend at \((5,5)\). However, an evil monster lives at \((2,2)\), so Kelvin cannot hop there. At any point, Kelvin the Frog can only hop 1 unit up or 1 unit to the right. How many paths are there from Kelvin to his friend?

---

The solution is given by the principle of inclusion-exclusion.

For the moment, ignore the presence of the monster, so that there are 252 paths to \((5,5)\). If the number of paths to \((5,5)\) that go through \((2,2)\) can be calculated, then the number of \((2,2)\)-avoiding paths can be calculated through simple subtraction.

So how many paths go through \((2,2)?\) Well, first Kelvin would have to hop from \((0,0)\) to \((2,2)\) without restrictions, which there are \(\binom{2+2}{2}=6\) ways to do. He would then have to hop from \((2,2)\) to \((5,5)\), which is the same thing as hopping from the origin to \((3,3)\), so there are \(\binom{3+3}{3}=20\) such paths. Thus, there are \(6 \cdot 20 = 120\) paths that go through \((2,2)\), meaning there are \(252-120=132\) paths that do not. \(_\square\)

This allows for another formula:

There are exactly \(\binom{m+n}{n}-\binom{a+b}{b}\binom{(m+n)-(a+b)}{n-b}\) paths from the origin to \((m,n)\) that do not go through the point \((a,\,b)\).

In other words, the number of ways to get from \((0,\, 0)\) to \((m,\, n)\) while avoiding the one restricted point at \((a,\, b)\) is given by the number of ways to get to \((m,\, n)\) with no restrictions, minus the number of ways to get to \((m,\, n)\) that go through \((a,\, b)\).

The following theorem provides a method for more general sets of restricted points.

In general, given restricted points \(S = \{P_1, \, P_2, \, \dots, \, P_k\}\), let \(\text{Path}(T)\) be the number of ways to get from \((0,\,0)\) to \((m,\,n)\) while going through all the points in \(T\). Then,

\[(\text{Number of Paths Avoiding } S) = \sum_{T \subsetneq S} (-1)^{|T|} \text{Path}(T).\]

Note that \(\text{Path}(\emptyset) = \binom{m + n}{n}\) and, if \(P = (a,\,b)\), then \(\text{Path}(\{P\}) = \binom{(m+n)-(a+b)}{n-b}\) .

When \(m = n\), \(k = n - 1\), and \(P_i = (i,\,i)\) for all \(1 \le i \le n-1\), the theorem turns into a formula for (two times) the Catalan numbers.

The theorem follows immediately from the generalized principle of inclusion-exclusion. Intuitively, the theorem formalizes the notion that "the number of ways we can get there is equal to the number of all possible ways to get there, minus the number of ways that look unappealing, plus the number of ways that look unappealing but we can still make work, minus the number of ways that look unappealing but workable that are actually blocked..." In other words, each partial sum is an attempt to calculate the answer, that improves upon a previous partial sum's attempt.

Kelvin the Frog lives at the origin, and wishes to visit his friend at \((5,5)\). However, an evil monster lives at \((2,2)\), so Kelvin cannot hop there. Another evil monster lives at \((3,3)\), so Kelvin cannot walk there either. At any point, Kelvin the Frog can only hop 1 unit up or 1 unit to the right. How many paths are there from Kelvin to his friend?

---

From an above problem, there are 120 paths going through (2,2). Similarly, there are 120 paths going through (3,3), so both are subtracted off from the 252 unrestricted paths. However, this subtracts some paths twice, namely the ones that go through (2,2) and (3,3), so those must be added back. There are \(\binom{2+2}{2} \cdot \binom{1+1}{1} \cdot \binom{2+2}{2}=72\) of these paths, so there are a total of \(252-120-120+72=84\) paths. \(_\square\)

If there are walls (or missing lines) in the grid, meaning that some one-unit moves are illegal, the inclusion-exclusion argument becomes a bit more complicated. For example,

Kelvin the Frog lives at the origin, and wishes to visit his friend at \((5,5)\). However, there is a wall between \((2,2)\) and \((2,3)\), through which Kelvin cannot hop. At any point, Kelvin the Frog can only hop 1 unit up or 1 unit to the right. How many paths are there from Kelvin to his friend?

---

For a path to go from \((2,2)\) to \((2,3)\), it must travel from the origin to \((2,2)\), move right, then travel to \((5,5)\). There are \(\binom{2+2}{2} \cdot \binom{3+2}{3} = 6 \cdot 10 = 60\) such paths, so there are \(252-60=192\) paths that avoid the wall. \(_\square\)

There are exactly \(\binom{a+b}{a} \cdot \binom{(m+n)-(a+b+1)}{n-b}\) paths that travel from \((0,\,0)\) to \((m,\,n)\) while using the path between \((a,\,b)\) and \((a+1,\,b)\). Therefore, there are exactly \(\binom{m+n}{n} - \binom{a+b}{a} \cdot \binom{(m+n)-(a+b+1)}{n-b}\) paths that travel from \((0,\,0)\) to \((m,\,n)\) while avoiding a wall between \((a,\,b)\) and \((a+1,\,b).\)

Any path that goes through the wall must at some point (immediately before crossing the wall) reach \((a,\,b)\). There are \(\binom{a+b}{a}\) ways to get from \((0,\,0)\) to \((a,\,b)\). From that point, there is one way to get to \((a+1,\,b)\), and that requires going over the wall. From \((a+1,\,b)\), there are \(\binom{m + n - a - b - 1}{m - a - 1} = \binom{m + n - a - b - 1}{n - b}\) paths to \((m,\,n)\). Since the wall must be avoided, there are \(\boxed{\binom{m+n}{n} - \binom{a+b}{a} \cdot \binom{(m+n)-(a+b+1)}{n-b}}\) possible paths.

From the formula in the above theorem, a similar approach may be taken for problems with multiple walls. In particular, if \(S = \{W_1, \, W_2, \, \dots, \, W_k\}\) is a set of walls and \(\text{Path}_2(T)\) is the number of ways from \((0,\,0)\) to \((m,\,n)\) while going through the walls in \(T\), then

\[(\text{Number of Paths Avoiding } S) = \sum_{T \subsetneq S} (-1)^{|T|} \text{Path}_2(T).\]

Kelvin the Frog lives at the origin, and wishes to visit his friend at \((5,5)\). However, there is a wall between \((2,2)\) and \((2,3)\) and a wall between \((3,3)\) and \((3,4)\), through which Kelvin cannot hop. At any point, Kelvin the Frog can only hop 1 unit up or 1 unit to the right. How many paths are there from Kelvin to his friend?

---

From an above problem, there are \(60\) paths going through the first wall. Similarly, there are \(\binom{3 + 3}{3} \cdot \binom{2 + 1}{2} = 60\) paths going through the second wall. However, there are \(\binom{2 + 2}{2} \cdot \binom{1 + 0}{1} \cdot \binom{2 + 1}{2} = 18\) paths going through both walls. Therefore, there are \(252 - 60 - 60 + 18 = 150\) paths. \(_\square\)

When moves other than the standard ones (right and up) are available, the recursion approach usually becomes superior to the bijective one. Even when a simple bijection does exist, discovering it usually involves analyzing the recursion. For example,

How many paths can a king take from one corner of an \(8 \times 8\) chessboard to the opposite corner?

A king can move 1 square in any direction, including diagonally.

---

It is possible to solve the general case of these movements, called king-walks, on an \(n \times n\) grid. However, there is not a closed form, and the expression is not as when there are only two possible move types.

In short, the number of king-walks to \((n,n)\) is

\[\sum_{k=0}^n\binom{n}{k}\cdot\binom{n+k}{k}.\]

Note that if we know how many right moves there are, we know how many up moves there are as well; there must be the same number. Additionally, the number of right moves plus the number of diagonal moves must be \(n\). So if there are \(k\) right moves, then we can calculate the number of moves with the combination, knowing there are \(n+k\) moves total: \(n-k\) diagonal moves, \(k\) right moves, and \(k\) up moves. So, summing over all possible values of \(k\), the number of king-walks should be

\[\sum_{k=0}^n \frac{(n+k)!}{(n-k)!k!k!} = \sum_{k=0}^n \frac{n!}{(n-k)!k!} \cdot \frac{(n+k)!}{n!k!} = \sum_{k=0}^n\binom{n}{k}\cdot\binom{n+k}{k}.\ _\square\]

• Dynamic Programming
• Identical Objects into Distinct Bins
• Principle of Inclusion and Exclusion
• Recursion