All Self-Avoiding Paths Through a Lattice

There are 2 self-avoiding (non-self-intersecting) paths from the southwest corner of a 1 × 1 grid to the northeast corner, using only steps north, east, south, or west):

2 paths, 1 x 1 grid: E-N, N-E

(In only this case, it turns out to be the same as the number of shortest paths.)

12 self-avoiding paths through a 2 × 2 grid:

12 paths, 2 x 2 grid: NNEE, NENE, NEEN, ..., EENWWNEE

(Of these 12 paths: the first 6 take 4 steps; the next 4 paths take 6 steps; and the last 2 paths take 8 steps.)

184 paths through a 3 × 3 grid:

184 paths, 3 x 3 grid

(Of these 184 paths: 20 of them take 6 steps; 36 take 8 steps; 48 take 10 steps; 48 take 12 steps; and 32 take 14 steps.)

This 2-D case is sequence A007764 in The On-Line Encyclopedia of Integer Sequences.

While we’re on the subject, there seem to be 18 self-avoiding paths through a 1 × 1 × 1 lattice:

18 paths, 1 x 1 x 1 lattice

(Of these 18 paths: 6 of them take 3 steps; 6 paths take 5 steps; and 6 paths take 7 steps.)

156 paths through a 2 × 1 × 1 lattice:

156 paths, 2 x 1 x 1 lattice

There are 5,698 paths through a 2 × 2 × 1 lattice; here are some of the 30 shortest and 314 longest:

5,698 paths, 2 x 2 x 1 lattice

Copyright © 1998–2017 by Robert Dickau.

[ home ] || [ 2011-02-06 ]


www.robertdickau.com/allpaths.html