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 "gridwalking 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 finitestate nature of gridwalking 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 gridwalking 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.
Contents
Motivation
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 decreasingdistance 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 norestrictions variant of gridwalking (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 \((m1,n)\) or \((m, n1)\) (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 \((m1,n)\) and the number of paths to \((m,n1)\).
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 nonrectangular 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:
\(y = 5\)  \(\binom{ 5 }{ 0 }\)  \(\binom{ 6 }{ 1 }\)  \(\binom{ 7 }{ 2 }\)  \(\binom{ 8 }{ 3 }\)  \(\binom{ 9 }{ 4 }\)  \(\binom{ 10 }{ 5 }\) 
\(y = 4\)  \(\binom{ 4 }{ 0 }\)  \(\binom{ 5 }{ 1 }\)  \(\binom{ 6 }{ 2 }\)  \(\binom{ 7 }{ 3 }\)  \(\binom{ 8 }{ 4 }\)  \(\binom{ 9 }{ 5 }\) 
\(y = 3\)  \(\binom{ 3 }{ 0 }\)  \(\binom{ 4 }{ 1 }\)  \(\binom{ 5 }{ 2 }\)  \(\binom{ 6 }{ 3 }\)  \(\binom{ 7 }{ 4 }\)  \(\binom{ 8 }{ 5 }\) 
\(y = 2\)  \(\binom{ 2 }{ 0 }\)  \(\binom{ 3 }{ 1 }\)  \(\binom{ 4 }{ 2 }\)  \(\binom{ 5 }{ 3 }\)  \(\binom{ 6 }{ 4 }\)  \(\binom{ 7 }{ 5 }\) 
\(y = 1\)  \(\binom{ 1 }{ 0 }\)  \(\binom{ 2 }{ 1 }\)  \(\binom{ 3 }{ 2 }\)  \(\binom{ 4 }{ 3 }\)  \(\binom{ 5 }{ 4 }\)  \(\binom{ 6 }{ 5 }\) 
\(y = 0\)\(\hspace{10mm}\)  \(\binom{ 0 }{ 0 }\)  \(\binom{ 1 }{ 1 }\)  \(\binom{ 2 }{ 2 }\)  \(\binom{ 3 }{ 3 }\)  \(\binom{ 4 }{ 4 }\)  \(\binom{ 5 }{ 5 }\) 
\(x=0\)\(\hspace{10mm}\)  \(x=1\)\(\hspace{10mm}\)  \(x=2\)\(\hspace{10mm}\)  \(x=3\)\(\hspace{10mm}\)  \(x=4\)\(\hspace{10mm}\)  \(x=5\) \(\hspace{10mm}\) 
which strongly suggests that gridwalking 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\)
No Restrictions
Suppose a particle is traveling from the bottomleft corner of an \(m \times n\) grid to the topright corner, by making steps along the edges of the grid.
There are exactly \(\binom{m+n}{n}\) paths from the bottomleft corner to the topright 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:
 The word must have length \(m + n\).
 The word must contain only 2 letters: R and U.
 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 bottomleft corner:
 Read the word normally, one letter at a time and from left to right.
 Each time an R is read, move right \(1\) unit in the grid.
 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 topright 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 bottomleft corner to the topright 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}.\]
Suppose that the board is clear of any piece, except for the king, which you place at the lowest left corner (the red square A1). You goal is to move around the king to get to the upper right corner (the red square H8). But there are rules: you are only allowed to move either to the right or up (and hence, never diagonally or to the left or down).
How many different paths are there that satisfy those constraints and travel from A1 to H8?
Bonus : Can you generalize to an \(m \times n\) chessboard?
Willy lives in the Cartesian coordinate plane. Willy's house lies at \( (0,0) \), while his school, Takoma Park, lies at \( (10,12) \). Willy needs to walk to school in the shortest way possible, or else he will be late to school and receive three warnings from Mr. Siddique. How many ways are there to get from the origin to \( (10,12) \) moving only up and to the right?
(Note that Willy must walk on the roads, or parallel to the \(x\) or \(y\)axis. If he is caught not doing so, he will receive three warnings.)
The Algorithmic Approach
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 

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 

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 \((m1,n)\), the number of paths to \((m,n1)\), and the number of paths to \((m1, n1)\).
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 16def 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(m1, n, arr) + dp(m, n1, arr) + dp(m1, n1, 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\)
Restricted Points
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 inclusionexclusion.
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 \(252120=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)}{nb}\) 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)}{nb}\) .
When \(m = n\), \(k = n  1\), and \(P_i = (i,\,i)\) for all \(1 \le i \le n1\), the theorem turns into a formula for (two times) the Catalan numbers.
The theorem follows immediately from the generalized principle of inclusionexclusion. 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 \(252120120+72=84\) paths. \(_\square\)
Mr. Siddique has left Takoma Park to go to Bangladesh, and because of that, Willy has transferred to Robert Frost, which lies at \( (5,5) \). Willy still lives at the origin.
Willy again wishes to walk to school. However, Arman owns a square plot of land with vertices at \( M=(2,2), E=(2,3), A=(3,3), N=(3,2) \), and he commands Willy to never ever walk along the boundary of his land: that is, Willy cannot touch any four vertices of Arman's land or walk along any side of his square plot of land.
Now, how many ways can Willy walk to school? (Willy can only walk up and right.)
(See here for details.)
Walls
If there are walls (or missing lines) in the grid, meaning that some oneunit moves are illegal, the inclusionexclusion 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 \(25260=192\) paths that avoid the wall. \(_\square\)
There are exactly \(\binom{a+b}{a} \cdot \binom{(m+n)(a+b+1)}{nb}\) 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)}{nb}\) 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)}{nb}}\) 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\)
Willy lives at the origin and is trying to go to school at Maya Angelou Elementary, which is located at \((6,\,4)\). He needs to get to school by making successive movements one unit to the right or one unit up.
Unfortunately, the evil businessman Rockefeller Tycoon has put up fences between \((1,\,1)\) and \((2,\,1)\) and between \((3,\,4)\) and \((4,\,4)\). Willy can no longer move along those paths.
In how many ways can Willy get to school?
Other Legal Moves
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 kingwalks, 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 kingwalks 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: \(nk\) diagonal moves, \(k\) right moves, and \(k\) up moves. So, summing over all possible values of \(k\), the number of kingwalks should be
\[\sum_{k=0}^n \frac{(n+k)!}{(nk)!k!k!} = \sum_{k=0}^n \frac{n!}{(nk)!k!} \cdot \frac{(n+k)!}{n!k!} = \sum_{k=0}^n\binom{n}{k}\cdot\binom{n+k}{k}.\ _\square\]
The diagram above shows a tiling of 7 squares with \(A\) and \(B\) denoting the initial point and destination point, respectively. The arrow signs indicate the direction that you're able to travel to (east, south, northeast). Find the total number of ways to reach point \(B\) from point \(A\).
Bonus: Generalize this for \(n\) squares.