Counting Lattice Paths

Photo by Armand Khoury on Unsplash

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.

How many trips do we have to make to see all the streets in this simplified version of Manhattan? To answer this, we need to count all paths that we can take in the grid. So, let’s find out.

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.

Square lattice.

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.

A lattice path.

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 2×2 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.

There are six paths in a 2×2 lattice.

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 4×4 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 4×4 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:

Going back to our 4×4 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: 6! / (6–4)! * 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 8! / (8–4)! * 4! = 70.

So, we just found another way to find the number of lattice paths in any k x 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 (n k), which is equivalent to the “ n choose k” expression from above. One method to obtain the binomial coefficients, such as (n k), is with the formula:

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^b*y^c where b and c are positive integers and b+c = n. The coefficient a is equal to (n k)–the coefficient of the kth term in the polynomial expansion. For example, let’s expand the polynomial (x + y)⁴ :

(x + y)⁴ = x⁴ + 4x³y + 6x²y² + 4xy³ + y⁴

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:

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 x 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:

Outer terms in Pascal’s triangle.

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:

Pascal’s triangle.

Using Pascal’s triangle, the binomial coefficient is equal to the term in the kth position of the nth row. So, to find (4 2) we go to the 4th row, then to the 2nd position. We get 6.

Notice that if we rotate our 4×4 lattice from before, we get Pascal’s triangle (with some missing terms at the bottom):

Rotated 4×4 lattice.

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:

Straight-line crossing the central binomial coefficients in Pascal’s triangle.

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 4×4 lattice. In a 2×2 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 2×2 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.

Originally published at https://stemhash.com on July 4, 2020.

--

--

--

Software Engineer. Endurance sports enthusiast. Blog: stemhash.com

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Median and MAE

The Magic of Fibonacci numbers!!

Saving the Japanese From Evil Mathematicians

CHAOS THEORY

From logic and math to code. For dummies. Part I: Basics

Little bit of Likelihoods

The maths of COVID-19, Part 1. Real World is not normal

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Iram Lee

Iram Lee

Software Engineer. Endurance sports enthusiast. Blog: stemhash.com

More from Medium

Control Theory: Separation principle and the Symbiosis between Controller and Plant

Adding the Dunning-Kruger variable in the mathematics classroom

Different Factorial in Math.

Probability Theory