TOPICS
Search

Self-Avoiding Walk


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.

SelfAvoidingWalkPositive

Consider a self-avoiding walk on a two-dimensional n×n 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 n=1, 2, ... steps are 1, 2, 5, 12, 30, 73, 183, 456, 1151, ... (OEIS A046170).

SelfAvoidingWalk

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 n=1, 2, ... steps are 1, 2, 5, 13, 36, 98, 272, 740, 2034, ... (OEIS A046171).

SelfAvoidingRookWalks

Self-avoiding rook walks are walks on an m×n grid which start from (0,0), end at (m,n), and are composed of only horizontal and vertical steps. The following table gives the first few numbers R(m,n) of such walks for small m and n. The values for m=n=1, 2, ... are 2, 12, 184, 8512, 1262816, ... (OEIS A007764).

m\n23456
22
3412
4838184
5161259768512
6324145382793841262816

There are a number of known formulas for computing R(m,n) for small m,n. For example,

 R(m,2)=2^(m-1).
(1)

There is a recurrence relation for R(m,3), given by R(1,3)=1, R(2,3)=4, R(3,3)=12, R(4,3)=38, and

 R(m,3)=4R(m-1,3)-3R(m-2,3)+2R(m-3,3)+R(m-3,4)
(2)

for m>=5, as well as the generating function

 R(m,3)=1/((m-1)!)(d^(m-1))/(dx^(m-1))((x-1)(x+1))/((x^2+3x-1)(x^2-x+1))|_(x=0)
(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 n in the plane, where bends are of 0 or +/-90 degrees 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).

SelfAvoidingZigZagWalks

Consider a self-avoiding walk on a two-dimensional n×n square grid from one corner to another such that no two consecutive steps are in the same direction. The number of such paths for n=1, 2, ... are 1, 2, 2, 4, 10, 36, 188, ... (OEIS A034165; counting the number of paths on the 1×1 point "lattice" as 1), and the maximum lengths of these paths are 0, 2, 4, 10, 12, 26, 36, ... (OEIS A034166).


See also

Lattice Path, Random Walk, Self-Avoiding Polygon, Self-Avoiding Walk Connective Constant, Staircase Polygon, Three-Choice Walk

Explore with Wolfram|Alpha

References

Abbott, H. L. and Hanson, D. "A Lattice Path Problem." Ars Combinatoria 6, 163-178, 1978.Alm, S. E. "Upper Bounds for the Connective Constant of Self-Avoiding Walks." Combin. Prob. Comput. 2, 115-136, 1993.Domb, C. "On Multiple Returns in the Random-Walk Problem." Proc. Cambridge Philos. Soc. 50, 586-591, 1954.Domb, C. "Self-Avoiding Walks on Lattices." Adv. Chem. Phys. 15, 229-259, 1969.Finch, S. R. "Self-Avoiding Walk Constants." §5.10 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 331-339, 2003.Hayes, B. "How to Avoid Yourself." Amer. Sci. 86, 314-319, 1998.Kesten, H. "On the Number of Self-Avoiding Walks." J. Math. Phys. 4, 960-969, 1963.Lawler, G. F. Intersections of Random Walks. Boston, MA: Birkhäuser, 1991.Sloane, N. J. A. Sequences A001997/M1206, A007764, A034165, A034166, A046170, and A046171 in "The On-Line Encyclopedia of Integer Sequences."Whittington, S. G. and Guttman, A. J. "Self-Avoiding Walks which Cross a Square." J. Phys. A 23, 5601-5609, 1990.

Referenced on Wolfram|Alpha

Self-Avoiding Walk

Cite this as:

Weisstein, Eric W. "Self-Avoiding Walk." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Self-AvoidingWalk.html

Subject classifications