
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

Walks in two dimensions

Walks in three dimensions

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,n1].
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
n  wl  nw 

0  0  1 
1  2  2 
2  4  6 
3  6  20 
4  8  70 
5  10  252 
6  12  924 
7  14  3432 
8  16  12870 
9  18  48620 
10  20  184756 
11  22  705432 
12  24  2704156 
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
n  wl  nw 

0  1  1 
1  3  3 
2  5  10 
3  7  35 
4  9  126 
5  11  462 
6  13  1716 
7  15  6435 
8  17  24310 
9  19  92378 
10  21  352716 
11  23  1352078 
12  25  5200300 
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,n1], j=[0,m1].
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
n  wl  nw 

0  0  1 
1  2  4 
2  4  36 
3  6  400 
4  8  4900 
5  10  63504 
6  12  853776 
7  14  11778624 
8  16  165636900 
9  18  2363904400 
10  20  34134779536 
11  22  497634306624 
12  24  7312459672336 
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
n  wl  nw 

0  1  1 
1  3  9 
2  5  100 
3  7  1225 
4  9  15876 
5  11  213444 
6  13  2944656 
7  15  41409225 
8  17  590976100 
9  19  8533694884 
10  21  124408576656 
11  23  1828114918084 
12  25  27043120090000 
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:
n  wl  nw 

0  2  2 
1  4  24 
2  6  300 
3  8  3920 
4  10  52920 
5  12  731808 
6  14  10306296 
7  16  147232800 
8  18  2127513960 
9  20  31031617760 
10  22  456164781072 
11  24  6749962774464 
12  26  100445874620000 
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,n1], j=[0,m1], k=[0,p1].
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
n  wl  nw 

0  0  1 
1  2  6 
2  4  90 
3  6  1860 
4  8  44730 
5  10  1172556 
6  12  32496156 
7  14  936369720 
8  16  27770358330 
9  18  842090474940 
10  20  25989269017140 
11  22  813689707488840 
12  24  25780447171287900 
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:
n  wl  nw 

0  1  1 
1  3  15 
2  5  310 
3  7  7455 
4  9  195426 
5  11  5416026 
6  13  156061620 
7  15  4628393055 
8  17  140348412490 
9  19  4331544836190 
10  21  135614951248140 
11  23  4296741195214650 
12  25  137507314754659500 
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:
n  wl  nw 

0  2  2 
1  4  48 
2  6  1200 
3  8  31920 
4  10  890820 
5  12  25768512 
6  14  766053288 
7  16  23265871200 
8  18  718834982580 
9  20  22523567008800 
10  22  714044153702880 
11  24  22861678250567520 
12  26  738191825153055000 
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:
n  wl  nw 

0  3  6 
1  5  180 
2  7  5040 
3  9  143640 
4  11  4199580 
5  13  125621496 
6  15  3830266440 
7  17  118655943120 
8  19  3724872182460 
9  21  118248726796200 
10  23  3789926661961440 
11  25  122473276342326000 
12  27  3986235855826497000 
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.