Counting Lattice Paths

The number of paths through a lattice given various restrictions—such as in which directions steps are allowed and what boundaries the path may not cross—describe many famous sequences of numbers. Here, the lattice paths start in the leftmost corner and continue to the rightmost corner.

blank lattice

The most familiar is surely the collection of paths from the beginning to end along the lattice lines, with steps (in this orientation) either northeast or southeast. There are two paths through a 1×1 lattice:

1-by-1 lattice

Six paths through a 2×2 lattice:

2-by-2 lattice

20 paths through a 3×3 lattice:

3-by-3 lattice

70 paths through a 4×4 lattice:

4-by-4 lattice

You can count the paths through these lattices by adding together the numbers of paths to each point in the lattice. There’s only one way to start at the leftmost point, so mark that point with a 1. Next, you can take a step northeast or a step southeast, with only one way to get to each of these points, so mark each of those with a 1. After that, you can get to the second point on the dotted line in two ways: NE-then-SE, or SE-then-NE. Continuing this way, you see that each of the points is described by the binomial coefficients, and the sequence of path counts for lattices of different sizes is 1, 2, 6, 20, 70, …, also known as the central binomial coefficients [OEIS A000984].

all paths through 4-by-4 lattice superimposed

Now, if we change the rules so that a path can’t go below the dashed line connecting the start and end points, the path counts change, of course, but they’re not just half of the previous counts. One path through the top half of a 1×1 lattice:

paths through top half of 1x1 lattice

Two paths through the top half of a 2×2 lattice:

top half of 2x2 lattice

Five paths through the top half of a 3×3 lattice:

top half of 3x3 lattice

We can again add the numbers of paths to each point. The sequence of path counts for lattices of different sizes is 1, 1, 2, 5, 14, 42, …, also known as the Catalan numbers [OEIS A000108].

superimposed paths through top half of 5x5 lattice

If we do the same thing as the first lattice except for allowing steps east in addition to northeast and southeast, the path counts increase. For example, there are now three paths through a 1×1 lattice:

Delannoy paths, 1x1

13 paths through a 2×2 lattice:

Delannoy paths, 2x2

And 63 paths through a 3×3 lattice:

Delannoy paths, 3x3

The path counts 1, 3, 13, 63, 321, …, are called the central Delannoy numbers [OEIS A001850].

Delannoy paths, 4x4

Likewise, if we restrict the paths to the upper half of the grid, we see different counts. Two paths through a 1×1 lattice:

Schroeder paths, 1x1

Six paths through a 2×2 lattice:

Schroeder paths, 2x2

22 paths through a 3×3 lattice:

Schroeder paths, 3x3

The path counts for this arrangement, 1, 2, 6, 22, 90, 394, …, are called the Schröder numbers [OEIS A006318].

Schroeder paths, 4x4

You can also extend the general idea to more dimensions—see 3-D, 4-D, and 5-D versions of the same idea—and to different rules—see for example Motzkin numbers.

Copyright © 1998–2014 by Robert Dickau.

[ home ] || [ 2011-05-22 ]


www.robertdickau.com/lattices.html