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).

This page may contain MathML. If you're using Firefox, you're ready to go. If you're using Internet Explorer, you need to install the Mathplayer plugin. Some browsers may also need additional fonts.

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

nwlnw
001
122
246
3620
4870
510252
612924
7143432
81612870
91848620
1020184756
1122705432
12242704156

Comments:

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

nwlnw
011
133
2510
3735
49126
511462
6131716
7156435
81724310
91992378
1021352716
11231352078
12255200300

Comments:

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:


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

nwlnw
001
124
2436
36400
484900
51063504
612853776
71411778624
816165636900
9182363904400
102034134779536
1122497634306624
12247312459672336

Comments:

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

nwlnw
011
139
25100
371225
4915876
511213444
6132944656
71541409225
817590976100
9198533694884
1021124408576656
11231828114918084
122527043120090000

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:

nwlnw
022
1424
26300
383920
41052920
512731808
61410306296
716147232800
8182127513960
92031031617760
1022456164781072
11246749962774464
1226100445874620000

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

nwlnw
001
126
2490
361860
4844730
5101172556
61232496156
714936369720
81627770358330
918842090474940
102025989269017140
1122813689707488840
122425780447171287900

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:

nwlnw
011
1315
25310
377455
49195426
5115416026
613156061620
7154628393055
817140348412490
9194331544836190
1021135614951248140
11234296741195214650
1225137507314754659500

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:

nwlnw
022
1448
261200
3831920
410890820
51225768512
614766053288
71623265871200
818718834982580
92022523567008800
1022714044153702880
112422861678250567520
1226738191825153055000

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:

nwlnw
036
15180
275040
39143640
4114199580
513125621496
6153830266440
717118655943120
8193724872182460
921118248726796200
10233789926661961440
1125122473276342326000
12273986235855826497000

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.