This site is supported by donations to The OEIS Foundation.
Selfavoiding walks
A selfavoiding walk (SAW) is a lattice path (sequence of moves between adjacent lattice nodes) that does not visit any lattice node more than once.
From Wikipedia:Selfavoiding walk:
SAWs were first introduced by the chemist Paul Flory in order to model the reallife behavior of chainlike entities such as solvents and polymers, whose physical volume prohibits multiple occupation of the same spatial point. Very little is known rigorously about the selfavoiding walk from a mathematical perspective, although physicists have provided numerous conjectures that are believed to be true and are strongly supported by numerical simulations.
A selfavoiding polygon (SAP) is a selfavoiding cycle (closed selfavoiding walk).
Contents
 1 Hamiltonian lattice walks
 2 Lattice graphs vs grid graphs
 3 Selfavoiding walks on a 0dimensional lattice
 4 Selfavoiding walks on a 1dimensional lattice
 5 Selfavoiding walks on a 2dimensional lattice
 5.1 Selfavoiding walks on a 2dimensional square lattice
 5.2 Selfavoiding walks on a 2dimensional equilateral triangular lattice
 6 Selfavoiding walks on a 3dimensional lattice
 7 Selfavoiding walks on a 4dimensional lattice
 8 See also
 9 External links
Hamiltonian lattice walks
A Hamiltonian lattice walk is a Hamiltonian path on a lattice that visits each lattice node exactly once.
A Hamiltonian lattice cycle is a Hamiltonian cycle (or Hamiltonian circuit) on a lattice, i.e. a closed Hamiltonian lattice walk.
Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem, which is NPcomplete.
Lattice graphs vs grid graphs
Lattice graphs have their values located at the corners of grid cells. Lattice graph edges join the corners of grid cells.
Grid graphs have their values located at the centers of grid cells. Grid graph edges join the centers of grid cells.
An (m+1) X (n+1) square lattice constitutes the cell corners (coordinates (0,0) to (m,n)) of an m X n square grid.
Selfavoiding walks on a 0dimensional lattice
Trivial, the point lattice (a single node) has only the null walk (staying put on that single node).
Selfavoiding walks on a 1dimensional lattice
Trivial, a path lattice of length n has only one walk from nodes (0) to (n1).
Selfavoiding walks on a 2dimensional lattice
Selfavoiding walks on a 2dimensional square lattice
Selfavoiding walks of length n on a 2dimensional square lattice
Selfavoiding walks of length  

1 
 
2 
 
3 

A046170 Number of selfavoiding walks on a 2D lattice of length which start at the origin, take first step in the {+1,0} direction and whose vertices are always nonnegative in x and y.
 {1, 2, 5, 12, 30, 73, 183, 456, 1151, 2900, 7361, 18684, 47652, 121584, 311259, 797311, 2047384, 5260692, 13542718, 34884239, 89991344, 232282110, 600281932, 1552096361, 4017128206, 10401997092, 26957667445, 69892976538, ...}
Selfavoiding walks on an (m+1) X (n+1) square lattice starting from (0,0) and ending at (m,n)
The apex of the triangle () corresponds to the 0dimensional lattice with only the null walk.
The first column () corresponds to 1dimensional lattices (path lattice of length ) with only one walk from nodes (0) to (m).
R(m,n), the number of selfavoiding walks on an (m+1) X (n+1) square lattice starting from (0,0) and ending at (m,n) = 0 1 1 1 2 2 1 4 12 3 1 8 38 184 4 1 16 125 976 8512 5 1 32 414 5382 79384 1262816 6 1 64 ? ? ? ? 575780564 7 1 128 ? ? ? ? ? 789360053252 8 1 256 ? ? ? ? ? ? 3266598486981642 9 1 512 ? ? ? ? ? ? ? 41044208702632496804 10 1 1024 ? ? ? ? ? ? ? ? 1568758030464750013214100 = 0 1 2 3 4 5 6 7 8 9 10
Selfavoiding walks on an (n+1) X (n+1) square lattice starting from (0,0) and ending at (n,n)
Selfavoiding walks starting from (0,0) and ending at (n,n)  

1 
 
2 

A007764 Number of selfavoiding walks from (0,0) to (n,n), n ≥ 0, of a (n+1) X (n+1) square lattice. Number of nonintersecting (or selfavoiding) rook paths joining opposite corner cells of an n X n grid. (should it be (n+1) X (n+1) grid, since rooks move from center to center of adjacent grid cells? — Daniel Forgues 06:06, 3 January 2012 (UTC))
 {1, 2, 12, 184, 8512, 1262816, 575780564, 789360053252, 3266598486981642, 41044208702632496804, 1568758030464750013214100, 182413291514248049241470885236, 64528039343270018963357185158482118, ...}
Hamiltonian selfavoiding walks on a 2dimensional square lattice
Example of a Hamiltonian selfavoiding walk on a 9 X 9 square lattice (corners of cells of an 8 X 8 square grid)
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪  ⦁ 
⎪  
⎪  
⎪  
⎪  
⎪  
⎪  
⎪  
⎪  ⎪  
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪  ⦁ 
⎪  
⎪  
⎪  
⎪  
⎪  
⎪  
⎪  
⎪  ⎪  
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪  ⦁ 
⎪  
⎪  
⎪  
⎪  
⎪  
⎪  
⎪  
⎪  ⎪  
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪  ⦁ 
⎪  
⎪  
⎪  
⎪  
⎪  
⎪  
⎪  
⎪  ⎪  
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪  ⦁ 
⎪  
⎪  
⎪  
⎪  
⎪  
⎪  
⎪  
⎪  ⎪  
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪  ⦁ 
⎪  
⎪  
⎪  
⎪  
⎪  
⎪  
⎪  
⎪  ⎪  
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪  ⦁ 
⎪  
⎪  
⎪  
⎪  
⎪  
⎪  
⎪  
⎪  ⎪  
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪  ⦁ 
⎪  
⎪  
⎪  
⎪  
⎪  
⎪  
⎪  
⎪  ⎪  
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪ 
⦁ 
⎪  ⦁ 
Example of a Hamiltonian selfavoiding walk on a 15 X 15 square lattice (corners of cells of a 14 X 14 square grid)
Selfavoiding walks on a 2dimensional equilateral triangular lattice
Selfavoiding walks of length n on a 2dimensional equilateral triangular lattice
(...)
Selfavoiding walks on an equilateral triangular lattice starting from (0,0) and ending at (n,0)
(...)
Selfavoiding walks on a 3dimensional lattice
Selfavoiding walks on a 3dimensional cubic lattice
(...)
Selfavoiding walks of length n on a 3dimensional cubic lattice
(...)
Selfavoiding walks on an (l+1) X (m+1) X (n+1) cubic lattice starting from (0,0,0) and ending at (l,m,n)
(...)
Selfavoiding walks on an (n+1) X (n+1) X (n+1) cubic lattice starting from (0,0,0) and ending at (n,n,n)
(...)
Selfavoiding walks on a 4dimensional lattice
Selfavoiding walks on a 4dimensional hypercubic lattice
(...)
Selfavoiding walks of length n on a 4dimensional hypercubic lattice
(...)
Selfavoiding walks on a (k+1) X (l+1) X (m+1) X (n+1) cubic lattice starting from (0,0,0,0) and ending at (k,l,m,n)
(...)
Selfavoiding walks on an (n+1) X (n+1) X (n+1) X (n+1) hypercubic lattice starting from (0,0,0,0) and ending at (n,n,n,n)
(...)
See also
 Template:Tlxb graphic template