Counting Lattice Paths
Combinatorics, Binomial Coefficients, and Pascal's Triangle
Jul 4, 2020
Let's take a taxicab ride through Manhattan in New York City. We're starting from a point in the upper west side down to the lower east side. On this trip, we want to see as much of the city as possible. We want to see all the streets and avenues because we've never been here before. In NYC, streets and avenues intersect and form a grid–The 1811 Commissioner's plan created this almost perfect matrix. To simplify things, let's say we are in a perfect grid–no Broadway or Central Park–and that we can only travel either east or south. If we always start from the same point in the upper west side, these trips will resemble paths known as Lattice Paths.
What is a Lattice, and a Lattice Path?
A lattice is a set of repeating points arranged in a pattern. The following is a square lattice in 2-dimensional space (we can have other arrangements, such as rectangular or hexagonal lattices and in higher dimensions). The points form a mesh of squares.
Then a lattice path is a sequence of steps connecting adjacent lattice points. Also, we restrict the direction in which we can move. In our case, we can only go east or south.
Here's a valid lattice path with only east and south moves. This path starts at the northwest corner and ends at the opposite southeast corner.
Now, imagine that each dot in the lattice is a street intersection, and the lines connecting each dot is a street or avenue. Then each square represents a block. We want to count all possible trips that we need to make to get from the northwest corner, down to the southeast corner. There are a few ways in which we can count these paths.
Counting Lattice Paths
As an example, let's count all possible lattice paths in a 2x2 square lattice–that is, an area of two blocks by two blocks. Six unique paths start from the upper left corner. The figure below illustrates this point.
Now, we're going to see a few methods to count lattice paths. We can use these for lattices of any size.
One way to count lattice paths is just as we did above. We count the paths by adding the number of ways in which we can reach each dot in the lattice–remembering that we can only go east or south and that we always start from the same origin. In the 4x4 lattice below, the blue and red paths indicate two possible ways to get to the first southeast dot. So, we marked it with a 2.
The next figure shows three ways to get to the next dot–indicated by the blue, green, and red paths. We marked it with a 3.
Only by going south, we get to any of the dots along the left side. Similarly, only by going east, we get to any of the dots on the top. That's why we marked them with a 1. Following this process, we count all the paths to the desired endpoint. There are 70 lattice paths to the southeast corner.
Combinatorics
For our next method, let's assign cartesian coordinates to each dot in the lattice. The northwest corner will be the origin, with coordinates $(0,0)$. The southeast corner–in our $4x4$ lattice example–will have coordinates $(-4,-4)$. But, in this case, we don't care about the sign of the coordinates. The result of our counts is symmetric. So, the coordinates for the southeast corner become $(4,4)$. To be more general–and include lattices of any size and either square or rectangular shapes–we'll use variables $(k,n)$ for our coordinates.
It turns out the number of lattice paths from $(0,0)$ to $(k,n)$ is equal to the number of combinations of $k$ objects out of $k+n$ options. Remember that the formula for counting the number of combinations of $k$ out of $n$ objects ("n choose k") is:
$$_nC_k=\frac{n!}{(n-k)!\cdot k!}$$
Going back to our 4x4 lattice (where $n = k = 4$), let's take the northwest corner as our $(0,0)$. If we go south 2 blocks then east 4 blocks–ignoring the sign of the coordinates–we arrive at point $(2,4)$. At this location $k = 2$ and $n = 4$.
Then the number of lattice paths is the combination of $k = 2$ out of $k+n = (2+4) = 6$ options. In other words, it's the number given by "6 choose 2", which is: $\frac{6!}{(6-4)!\cdot 4!} = 15$. That is the number we previously marked at that position. To get the number of paths down to the southeast corner (marked with a 70), we compute $\frac{8!}{(8-4)!\cdot 4!} = 70$.
So, we just found another way to find the number of lattice paths in any $k\times n$ rectangular lattice–where a square lattice is just a rectangular lattice where $n = k$.
Counting with Binomial Coefficients
Our next method uses binomial coefficients. The count at point $(k,n)$ corresponds to the binomial coefficient $\binom{n}{k}$, which is equivalent to the "n choose k" expression from above. One method to obtain the binomial coefficients, such as $\binom{n}{k}$, is with the formula:
$$\binom{n}{k} = \frac{n!}{(n-k)!\cdot k!}$$
That is the same as the combination formula we used above.
The binomial coefficients are the positive integers resulting from the binomial theorem in elementary algebra. According to the binomial theorem, we can expand a polynomial $(x + y)^n$ into a sum of terms of the form $ax^by^c$ where $b$ and $c$ are positive integers and $b+c = n$. The coefficient $a$ is equal to $\binom{n}{k}$–the coefficient of the kth term in the polynomial expansion. For example, let's expand the polynomial $(x + y)^4$:
$(x + y)^4 = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4$
The coefficients in the expansion are 1, 4, 6, 4, 1. Using our formula, we can obtain each of these coefficients by substituting $n$ with 4 and $k$ with the position–starting from zero–of each coefficient. For example, the 2nd coefficient is 6, and we obtain it by computing:
$$\binom{4}{2} = \frac{4!}{(4-2)!\cdot 2!} = 6$$
The count of lattice paths is equal to the number of combinations and equivalent to the binomial coefficients.
Counting with Pascal's Triangle
Similarly, there's yet another way to count the number of lattice paths in a $k\times n$ lattice. We know that Pascal's triangle arranges the binomial coefficients. To construct Pascal's triangle, we start by setting 1's as the outer terms on each row:
Then we fill the inner terms by adding the two terms directly above. For example, the next inner term in row 2 is the sum 1 + 1–these are the two terms directly above–in row 1. We follow this process to fill all the inner terms in the triangle:
Using Pascal's triangle, the binomial coefficient is equal to the term in the $k$th position of the $n$th row. So, to find $\binom{4}{2}$ we go to the 4th row, then to the 2nd position. We get 6.
Notice that if we rotate our 4x4 lattice from before, we get Pascal's triangle (with some missing terms at the bottom):
Also, if we draw a straight line from the top of Pascal's triangle to its base, it will "cross out" all the binomial coefficients corresponding to the number of paths in square lattices of different sizes:
In the triangle above, the line crosses the terms 1, 2, 6, 20, and 70. If we assign an index to these terms–starting from zero–the 4th term is 70. That is the number of lattice paths in a 4x4 lattice. In a 2x2 lattice, the number of paths is equal to the 2nd crossed-out term, which is 6. Just as we found at the beginning, with our 2x2 lattice example.
Finishing Up
We just went through several methods to count lattice paths. If you think about it, they are all equivalent. The combination formula helps us find the binomial coefficients. Pascal's triangle arranges these binomial coefficients. Any of the methods above will give you the correct answer.
There are always different–but equally correct–ways to do things. Just because something is different, it doesn't mean it's wrong. Whether one method is better than the others depends on your specific use case.