Lattice Paths and Walks

About

This page on lattice paths and walks is the work of Stefan Hollos and Richard Hollos. Our interest in this subject began with our work on lattice Green functions. We have found that many problems in lattice path/walk counting can be solved using Green functions. We are still in the process of publishing some of our work in this area, especially for the case of finite lattices with arbitrary boundaries.

There is an enormous amount of literature on lattice paths/walks and many people are actively working in this area. Our goal is to try to catalog some of the vast amount of work going on in this area. The plan is to turn this into a reference on the subject that will be useful to ourselves and hopefully to others as well.

Creating such a resource is something that will take time and an enormous amount of effort. We will be adding material as fast as we can. We are also hoping that some of you who are doing work in this area will want to contribute. The website will eventually be set up to allow people to contribute and leave comments, similar to the way Neil Sloane's On-Line Encyclopedia of Integer Sequences is set up. In the meantime, if you are interested in contributing in any way, please send an email to Stefan (stefan at exstrom dot com).

The On-Line Encyclopedia of Integer Sequences (EIS) is another great resource for this subject. Many of the integer sequences related to lattice path/walk counting can be found there. We do not intend to simply reproduce what can be found there but to extend and supplement it. We will have links to lattice path/walk sequences on the EIS whenever they exist. These EIS entries often have additional combinatorial interpretations of the sequences that can be very useful.

Please note that if no reference is given for something it means that we have derived it ourselves. This does not mean however that the result is necessarily original by us and we do not want to imply this in any way. It merely means that we are unaware of the original source. If you know of any references that we have omitted please let us know.

Send any comments or suggestions to Stefan (stefan at exstrom dot com).

• Articles

  • Walks on infinite lattices - this derives some of the formulas for counting the number of walks on infinite lattices. It is far from complete and we will be continually adding to it.
  • First visit lattice walks - this shows how the total number of walks between two points in a lattice and the number of walks where the end point is reached for the first time only at the end, are related.

• Walks in one dimension

  • W10000 - Walks returning to origin

  • W10001 - Walks from origin to first nearest neighbor

  • W10002 - Walks from origin to node (a)

• Walks in two dimensions

  • W20000 - Walks returning to origin

  • W20001 - Walks from origin to first nearest neighbor

  • W20002 - Walks from origin to second nearest neighbor

  • W20003 - Walks from origin to node (a,b)

• Walks in three dimensions

  • W30000 - Walks returning to origin

  • W30001 - Walks from origin to first nearest neighbor

  • W30002 - Walks from origin to second nearest neighbor

  • W30003 - Walks from origin to third nearest neighbor

  • W30004 - Walks from origin to node (a,b,c)

• Glossary

Walks in one dimension

These are walks on the integers i.
Infinite lattice nodes are numbered: i=[-inf,+inf].
Half lattice nodes are numbered: i=[0,+inf].
Size n finite lattice nodes are numbered: i=[0,n-1].

W10000 - Walks returning to origin

Lattice type: linear
Lattice size: infinite
Start node: 0
End node: 0
Steps: +1, -1
Restrictions: none
Walk length: wl = 2n, n = 0,1,2,3,...
Number of walks: nw = binomial(2n,n)
EIS number: A000984

Comments:

• Let 1 denote a step to the right and 0 a step to the left then the number of walks of length 2n is equal to the number of 2n digit binary numbers with equal numbers of 1's and 0's. These numbers are also known as the central binomial coefficients. They can in general be interpreted as the number of ways of forming two sets of n elements from a set of 2n elements. There are many other interpretations - see the EIS entry.
• If the steps to the left are instead interpreted as steps up in a square lattice then these walks are equivalent to the number of walks in a square lattice that begin at the origin (0,0) and end at node (n,n) with steps (+1,0) and (0,+1).

W10001 - Walks from origin to first nearest neighbor

Lattice type: linear
Lattice size: infinite
Start node: 0
End node: 1
Steps: +1, -1
Restrictions: none
Walk length: wl = 2n+1, n = 0,1,2,3,...
Number of walks: nw = binomial(2n+1,n)
EIS number: A001700

Comments:

• Let 1 denote a step to the right and 0 a step to the left then the number of walks of length 2n+1 is equal to the number of 2n+1 digit binary numbers where the difference in the number of 1's and 0's is equal to one.
• If the steps to the left are instead interpreted as steps up in a square lattice then these walks are equivalent to the number of walks in a square lattice that begin at the origin (0,0) and end at node (n+1,n) with steps (+1,0) and (0,+1).

W10002 - Walks from origin to node (a)

Lattice type: linear
Lattice size: infinite
Start node: 0
End node: a
Steps: +1, -1
Restrictions: none
Walk length: wl = 2n + a, n = 0,1,2,3,...
Number of walks: nw = binomial(2n+a,n)
EIS number:

Comments:

• If the steps to the left are instead interpreted as steps up in a square lattice then these walks are equivalent to the number of walks in a square lattice that begin at the origin (0,0) and end at node (n+a,n) with steps (+1,0) and (0,+1).

Walks in two dimensions

For a square lattice, these are walks on ordered pairs of integers (i,j).
Infinite lattice nodes are numbered: i,j=[-inf,+inf].
Half lattice nodes are numbered: i=[0,+inf], j=[-inf,+inf].
Quarter lattice nodes are numbered: i,j=[0,+inf].
Size n by m finite lattice nodes are numbered: i=[0,n-1], j=[0,m-1].

W20000 - Walks returning to origin

Lattice type: square
Lattice size: infinite
Start node: (0,0)
End node: (0,0)
Steps: (+1,0), (-1,0), (0,+1), (0,-1)
Restrictions: none
Walk length: wl = 2n, n = 0,1,2,3,...
Number of walks: nw = binomial(2n,n)^2
EIS number: A002894

Comments:

• These are squares of the central binomial coefficients

W20001 - Walks from origin to first nearest neighbor

Lattice type: square
Lattice size: infinite
Start node: (0,0)
End node: (1,0)
Steps: (+1,0), (-1,0), (0,+1), (0,-1)
Restrictions: none
Walk length: wl = 2n+1, n = 0,1,2,3,...
Number of walks: nw = binomial(2n+1,n)^2
EIS number: A060150

Comments:

W20002 - Walks from origin to second nearest neighbor

Lattice type: square
Lattice size: infinite
Start node: (0,0)
End node: (1,1)
Steps: (+1,0), (-1,0), (0,+1), (0,-1)
Restrictions: none
Walk length: wl = 2n+2, n = 0,1,2,3,...
Number of walks: nw = binomial(2n+2,n) * binomial(2n+2,n+1)
EIS number:

Comments:

W20003 - Walks from origin to node (a,b)

Lattice type: square
Lattice size: infinite
Start node: (0,0)
End node: (a,b)
Steps: (+1,0), (-1,0), (0,+1), (0,-1)
Restrictions: none
Walk length: wl = 2n+a+b, n = 0,1,2,3,...
Number of walks: nw = binomial(2n+a+b,n) * binomial(2n+a+b,n+a)
EIS number:

Comments:

Walks in three dimensions

For a cubic lattice, these are walks on ordered triplets of integers (i,j,k).
Infinite lattice nodes are numbered: i,j,k=[-inf,+inf].
Half lattice nodes are numbered: i=[0,+inf], j,k=[-inf,+inf].
Quarter lattice nodes are numbered: i,j=[0,+inf], k=[-inf,+inf].
Eighth lattice nodes are numbered: i,j,k=[0,+inf].
Size n by m by p finite lattice nodes are numbered: i=[0,n-1], j=[0,m-1], k=[0,p-1].

W30000 - Walks returning to origin

Lattice type: cubic
Lattice size: infinite
Start node: (0,0,0)
End node: (0,0,0)
Steps: (+1,0,0), (-1,0,0), (0,+1,0), (0,-1,0,), (0,0,+1), (0,0,-1)
Restrictions: none
Walk length: wl = 2n, n = 0,1,2,3,...
Number of walks: nw = binomial(2n,n) * sum( binomial(n,k)^2 * binomial(2k,k), k, 0, n )
EIS number: A002896

Comments:

W30001 - Walks from origin to first nearest neighbor

Lattice type: cubic
Lattice size: infinite
Start node: (0,0,0)
End node: (1,0,0)
Steps: (+1,0,0), (-1,0,0), (0,+1,0), (0,-1,0,), (0,0,+1), (0,0,-1)
Restrictions: none
Walk length: wl = 2n+1, n = 0,1,2,3,...
Number of walks: nw = binomial(2n+1,n) * sum( binomial(n,k) * binomial(n+1,k) * binomial(2k,k), k, 0, n )
EIS number:

Comments:

W30002 - Walks from origin to second nearest neighbor

Lattice type: cubic
Lattice size: infinite
Start node: (0,0,0)
End node: (1,1,0)
Steps: (+1,0,0), (-1,0,0), (0,+1,0), (0,-1,0,), (0,0,+1), (0,0,-1)
Restrictions: none
Walk length: wl = 2n+2, n = 0,1,2,3,...
Number of walks: nw = binomial(2n+2,n) * sum( binomial(n,k) * binomial(n+2,k+1) * binomial(2k+1,k), k, 0, n )
EIS number:

Comments:

W30003 - Walks from origin to third nearest neighbor

Lattice type: cubic
Lattice size: infinite
Start node: (0,0,0)
End node: (1,1,1)
Steps: (+1,0,0), (-1,0,0), (0,+1,0), (0,-1,0,), (0,0,+1), (0,0,-1)
Restrictions: none
Walk length: wl = 2n+3, n = 0,1,2,3,...
Number of walks: nw = binomial(2n+3,n) * sum( binomial(n,k) * binomial(n+3,k+2) * binomial(2k+2,k+1), k, 0, n )
EIS number:

Comments:

W30004 - Walks from origin to node (a,b,c)

Lattice type: cubic
Lattice size: infinite
Start node: (0,0,0)
End node: (a,b,c)
Steps: (+1,0,0), (-1,0,0), (0,+1,0), (0,-1,0,), (0,0,+1), (0,0,-1)
Restrictions: none
Walk length: wl = 2n+a+b+c, n = 0,1,2,3,...
Number of walks: nw = binomial(2n+a+b+c,n) * sum( binomial(n,k) * binomial(n+a+b+c,k+b+c) * binomial(2k+b+c,k+b), k, 0, n )
EIS number:

Comments:

Glossary

Lattice Walk

A lattice walk is a sequence of steps that move from one lattice node to another. There is a designated starting node and there may or may not be a designated ending node. The type of steps allowed is limited. In a square lattice for example, the steps may be limited to those that can reach a nearest neighbor node: (1,0), (-1,0), (0,1), (0,-1). In an unrestricted walk any node may be visited any number of times and the walk may retrace part or all of itself.

Lattice Path

A path differs from a walk in that no node may be visited more than once. For the same set of allowable steps and a given length (number of steps taken), the set of all possible paths between two given nodes will be a subset of the set of all possible walks.

Copyright 2007 by Exstrom Laboratories LLC

email: stefan[AT]exstrom DOT com