A001411 Number of n-step self-avoiding walks on square lattice.

1, 4, 12, 36, 100, 284, 780, 2172, 5916, 16268, 44100, 120292, 324932, 881500, 2374444, 6416596, 17245332, 46466676, 124658732, 335116620, 897697164, 2408806028, 6444560484, 17266613812, 46146397316, 123481354908, 329712786220, 881317491628

Offset: 0

Author

N. J. A. Sloane, Anthony Guttmann

Keywords

• nonn
• walk
• nice

References

• B. Bollobas and O. Riordan, Percolation, Cambridge, 2006, see p. 15.
• Steven R. Finch, Mathematical Constants, Cambridge, 2003, section 5.10, pp. 331-338.
• B. D. Hughes, Random Walks and Random Environments, Oxford 1995, vol. 1, p. 461.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• N. J. A. Sloane, Hugo Pfoertner, Table of n, a(n) for n = 0..79 (from the Jensen links below)
• H. Bottomley, Illustration of initial terms
• A. R. Conway et al., Algebraic techniques for enumerating self-avoiding walks on the square lattice, J. Phys A 26 (1993) 1519-1534.
• A. R. Conway et al., Algebraic techniques for enumerating self-avoiding walks on the square lattice, arXiv:hep-lat/9211062, 1992.
• Steven R. Finch, Self-Avoiding-Walk Connective Constants
• M. E. Fisher and M. F. Sykes, Excluded-volume problem and the Ising model of ferromagnetism, Phys. Rev. 114 (1959), 45-58.
• A. J. Guttmann, On the critical behavior of self-avoiding walks, J. Phys. A 20 (1987), 1839-1854.
• A. J. Guttmann and A. R. Conway, Self-Avoiding Walks and Polygons, Annals of Combinatorics 5 (2001) 319-345.
• B. J. Hiley and M. F. Sykes, Probability of initial ring closure in the restricted random-walk model of a macromolecule, J. Chem. Phys., 34 (1961), 1531-1537.
• I. Jensen, Series Expansions for Self-Avoiding Walks
• Iwan Jensen, A new transfer-matrix algorithm for exact enumerations: self-avoiding walks on the square lattice, arXiv:1309.6709 [math-ph], 26 Sep 2013.
• D. Randall, Counting in Lattices: Combinatorial Problems from Statistical Mechanics, PhD Thesis.
• D. Randall, Counting in Lattices: Combinatorial Problems from Statistical Mechanics, PhD Thesis, 1994.
• G. Slade, Self-avoiding walks, Math. Intelligencer, 16 (No. 1, 1994), 29-35.
• M. F. Sykes, Some counting theorems in the theory of the Ising problem and the excluded volume problem, J. Math. Phys., 2 (1961), 52-62.
• M. F. Sykes et al., The asymptotic behavior of selfavoiding walks and returns on a lattice, J. Phys. A 5 (1972), 653-660.

Crossrefs

Twice A002900.

Programs

Maple

noloop:=X->evalb(nops(X)=nops({op(X)})):
extend:=proc(L) local L1,U,X,res:
   U:=[[1,0],[0,1],[-1,0],[0,-1]]:
   res:=NULL:for X in U do L1:=[op(L),L[nops(L)]+X]:
   if noloop(L1) then res:=res,L1 fi od:
   return(res) end:
walks:={[[0,0]]}: A001411:=1:
to 12 do walks:=map(x->extend(x),walks): A001411:=A001411,nops(walks) od:
[A001411];
# Robert FERREOL, Mar 29 2019

Mathematica

mo=Tuples[{-1,1}, 2]; a[0]=1; a[tg_, p_:{{0,0}}] := Block[{e, mv = Complement[Last[p]+# & /@ mo, p]}, If[tg == 1, Length@mv, Sum[a[tg-1, Append[p, e]], {e, mv}]]]; a /@ Range[0, 10] (* Giovanni Resta, May 06 2016 *)

Python

def add(L,x):
    M=[y for y in L];M.append(x)
    return(M)
plus=lambda L,M : [x+y for x,y in zip(L,M)]
mo=[[1,0],[0,1],[-1,0],[0,-1]]
def a(n,P=[[0,0]]):
    if n==0: return(1)
    mv1=[plus(P[-1],x) for x in mo]
    mv2=[x for x in mv1 if x not in P]
    if n==1: return(len(mv2))
    else: return(sum(a(n-1,add(P,x)) for x in mv2))
[a(n) for n in range(11)]
# Robert FERREOL, Nov 30 2018; after the Mathematica program.