A001411 - OEIS

%I M3448 N1402 #84 Aug 05 2024 13:38:20

%S 1,4,12,36,100,284,780,2172,5916,16268,44100,120292,324932,881500,

%T 2374444,6416596,17245332,46466676,124658732,335116620,897697164,

%U 2408806028,6444560484,17266613812,46146397316,123481354908,329712786220,881317491628

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

%D B. Bollobas and O. Riordan, Percolation, Cambridge, 2006, see p. 15.

%D Steven R. Finch, Mathematical Constants, Cambridge, 2003, section 5.10, pp. 331-338.

%D B. D. Hughes, Random Walks and Random Environments, Oxford 1995, vol. 1, p. 461.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H N. J. A. Sloane, Hugo Pfoertner, <a href="/A001411/b001411.txt">Table of n, a(n) for n = 0..79</a> (from the Jensen links below)

%H H. Bottomley, <a href="/A001411/a001411.gif">Illustration of initial terms</a>

%H A. R. Conway et al., <a href="http://dx.doi.org/10.1088/0305-4470/26/7/012">Algebraic techniques for enumerating self-avoiding walks on the square lattice</a>, J. Phys A 26 (1993) 1519-1534.

%H A. R. Conway et al., <a href="http://arxiv.org/abs/hep-lat/9211062">Algebraic techniques for enumerating self-avoiding walks on the square lattice</a>, arXiv:hep-lat/9211062, 1992.

%H Steven R. Finch, <a href="http://web.archive.org/web/20010207195347/http://www.mathsoft.com/asolve/constant/cnntv/cnntv.html">Self-Avoiding-Walk Connective Constants</a>

%H M. E. Fisher and M. F. Sykes, <a href="http://dx.doi.org/10.1103/PhysRev.114.45">Excluded-volume problem and the Ising model of ferromagnetism</a>, Phys. Rev. 114 (1959), 45-58.

%H A. J. Guttmann, <a href="http://dx.doi.org/10.1088/0305-4470/20/7/029">On the critical behavior of self-avoiding walks</a>, J. Phys. A 20 (1987), 1839-1854.

%H A. J. Guttmann and A. R. Conway, <a href="http://dx.doi.org/10.1007/PL00013842">Self-Avoiding Walks and Polygons</a>, Annals of Combinatorics 5 (2001) 319-345.

%H B. J. Hiley and M. F. Sykes, <a href="http://dx.doi.org/10.1063/1.1701041">Probability of initial ring closure in the restricted random-walk model of a macromolecule</a>, J. Chem. Phys., 34 (1961), 1531-1537.

%H I. Jensen, <a href="https://web.archive.org/web/20151222163324/http://www.ms.unimelb.edu.au/~iwan/saw/SAW_ser.html">Series Expansions for Self-Avoiding Walks</a>

%H Iwan Jensen, <a href="https://arxiv.org/abs/1309.6709">A new transfer-matrix algorithm for exact enumerations: self-avoiding walks on the square lattice</a>, arXiv:1309.6709 [math-ph], 26 Sep 2013.

%H D. Randall, <a href="http://citeseerx.ist.psu.edu/pdf/bfc5b51d2ee76c6a7d347b2ac42ef16f040fbeb8">Counting in Lattices: Combinatorial Problems from Statistical Mechanics</a>, PhD Thesis.

%H D. Randall, <a href="http://www.icsi.berkeley.edu/icsi/node/2656">Counting in Lattices: Combinatorial Problems from Statistical Mechanics</a>, PhD Thesis, 1994.

%H G. Slade, <a href="http://dx.doi.org/10.1007/BF03026612">Self-avoiding walks</a>, Math. Intelligencer, 16 (No. 1, 1994), 29-35.

%H M. F. Sykes, <a href="http://dx.doi.org/10.1063/1.1724212">Some counting theorems in the theory of the Ising problem and the excluded volume problem</a>, J. Math. Phys., 2 (1961), 52-62.

%H M. F. Sykes et al., <a href="http://dx.doi.org/10.1088/0305-4470/5/5/007">The asymptotic behavior of selfavoiding walks and returns on a lattice</a>, J. Phys. A 5 (1972), 653-660.

%p noloop:=X->evalb(nops(X)=nops({op(X)})):

%p extend:=proc(L) local L1,U,X,res:

%p    U:=[[1,0],[0,1],[-1,0],[0,-1]]:

%p    res:=NULL:for X in U do L1:=[op(L),L[nops(L)]+X]:

%p    if noloop(L1) then res:=res,L1 fi od:

%p    return(res) end:

%p walks:={[[0,0]]}: A001411:=1:

%p to 12 do walks:=map(x->extend(x),walks): A001411:=A001411,nops(walks) od:

%p [A001411];

%p # _Robert FERREOL_, Mar 29 2019

%t 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 *)

%o (Python)

%o def add(L,x):

%o     M=[y for y in L];M.append(x)

%o     return(M)

%o plus=lambda L,M : [x+y for x,y in zip(L,M)]

%o mo=[[1,0],[0,1],[-1,0],[0,-1]]

%o def a(n,P=[[0,0]]):

%o     if n==0: return(1)

%o     mv1=[plus(P[-1],x) for x in mo]

%o     mv2=[x for x in mv1 if x not in P]

%o     if n==1: return(len(mv2))

%o     else: return(sum(a(n-1,add(P,x)) for x in mv2))

%o [a(n) for n in range(11)]

%o # _Robert FERREOL_, Nov 30 2018; after the Mathematica program.

%Y Twice A002900.

%K nonn,walk,nice

%O 0,2

%A _N. J. A. Sloane_, _Anthony Guttmann_