A self-avoiding walk is a path from one point to another which never intersects itself. Such paths are usually considered to occur on lattices, so that steps are only allowed in a discrete number of directions and of certain lengths.
Consider a self-avoiding walk on a two-dimensional 
square grid (i.e., a lattice path which never visits
the same lattice point twice) which starts at the origin, takes first step in the
positive horizontal direction, and is restricted to nonnegative grid points only.
The number of such paths of 
, 2, ... steps are 1, 2, 5, 12, 30, 73, 183, 456, 1151, ...
(OEIS A046170).
Similarly, consider a self-avoiding walk which starts at the origin, takes first step in the positive horizontal direction, is not restricted to nonnegative
grid points only, but which is restricted to take an up step before taking
the first down step. The number of such paths of 
, 2, ... steps are 1, 2, 5, 13, 36, 98, 272, 740, 2034, ...
(OEIS A046171).
Self-avoiding rook walks are walks on an 
grid which start from 
, end at 
, and are composed of only horizontal and vertical steps.
The following table gives the first few numbers 
of such walks for small 
and 
. The values for 
, 2, ... are 2, 12, 184, 8512, 1262816, ... (OEIS A007764).
 | 2 | 3 | 4 | 5 | 6 |
| 2 | 2 | ||||
| 3 | 4 | 12 | |||
| 4 | 8 | 38 | 184 | ||
| 5 | 16 | 125 | 976 | 8512 | |
| 6 | 32 | 414 | 5382 | 79384 | 1262816 |
There are a number of known formulas for computing 
for small 
. For example,
 |
(1)
|
There is a recurrence relation for 
, given by 
, 
, 
, 
, and
 |
(2)
|
for 
,
as well as the generating function
 |
(3)
|
(Abbott and Hanson 1978, Finch 2003).
A related sequence is the number of shapes which can be formed by bending a piece of wire of length 
in the plane, where bends are of 0 or 
and the wire may cross itself at right angles
but not pass over itself. The number of shapes for wires of length 1, 2, ... are
1, 2, 4, 10, 24, 66, 176, 493, ... (OEIS A001997).
Consider a self-avoiding walk on a two-dimensional 
square grid from one corner to another such that no
two consecutive steps are in the same direction. The number of such paths for 
, 2, ... are 1, 2, 2, 4, 10, 36, 188,
... (OEIS A034165; counting the number of paths
on the 
point "lattice" as 1), and the maximum lengths of these paths are 0, 2,
4, 10, 12, 26, 36, ... (OEIS A034166).
