cp's OEIS Frontend

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

%I A001411 M3448 N1402 #84 Aug 05 2024 13:38:20
%S A001411 1,4,12,36,100,284,780,2172,5916,16268,44100,120292,324932,881500,
%T A001411 2374444,6416596,17245332,46466676,124658732,335116620,897697164,
%U A001411 2408806028,6444560484,17266613812,46146397316,123481354908,329712786220,881317491628
%N A001411 Number of n-step self-avoiding walks on square lattice.
%D A001411 B. Bollobas and O. Riordan, Percolation, Cambridge, 2006, see p. 15.
%D A001411 Steven R. Finch, Mathematical Constants, Cambridge, 2003, section 5.10, pp. 331-338.
%D A001411 B. D. Hughes, Random Walks and Random Environments, Oxford 1995, vol. 1, p. 461.
%D A001411 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001411 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A001411 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 A001411 H. Bottomley, <a href="/A001411/a001411.gif">Illustration of initial terms</a>
%H A001411 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 A001411 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 A001411 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 A001411 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 A001411 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 A001411 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 A001411 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 A001411 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 A001411 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 A001411 D. Randall, <a href="http://citeseerx.ist.psu.edu/pdf/bfc5b51d2ee76c6a7d347b2ac42ef16f040fbeb8">Counting in Lattices: Combinatorial Problems from Statistical Mechanics</a>, PhD Thesis.
%H A001411 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 A001411 G. Slade, <a href="http://dx.doi.org/10.1007/BF03026612">Self-avoiding walks</a>, Math. Intelligencer, 16 (No. 1, 1994), 29-35.
%H A001411 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 A001411 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 A001411 noloop:=X->evalb(nops(X)=nops({op(X)})):
%p A001411 extend:=proc(L) local L1,U,X,res:
%p A001411    U:=[[1,0],[0,1],[-1,0],[0,-1]]:
%p A001411    res:=NULL:for X in U do L1:=[op(L),L[nops(L)]+X]:
%p A001411    if noloop(L1) then res:=res,L1 fi od:
%p A001411    return(res) end:
%p A001411 walks:={[[0,0]]}: A001411:=1:
%p A001411 to 12 do walks:=map(x->extend(x),walks): A001411:=A001411,nops(walks) od:
%p A001411 [A001411];
%p A001411 # _Robert FERREOL_, Mar 29 2019
%t A001411 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 A001411 (Python)
%o A001411 def add(L,x):
%o A001411     M=[y for y in L];M.append(x)
%o A001411     return(M)
%o A001411 plus=lambda L,M : [x+y for x,y in zip(L,M)]
%o A001411 mo=[[1,0],[0,1],[-1,0],[0,-1]]
%o A001411 def a(n,P=[[0,0]]):
%o A001411     if n==0: return(1)
%o A001411     mv1=[plus(P[-1],x) for x in mo]
%o A001411     mv2=[x for x in mv1 if x not in P]
%o A001411     if n==1: return(len(mv2))
%o A001411     else: return(sum(a(n-1,add(P,x)) for x in mv2))
%o A001411 [a(n) for n in range(11)]
%o A001411 # _Robert FERREOL_, Nov 30 2018; after the Mathematica program.
%Y A001411 Twice A002900.
%K A001411 nonn,walk,nice
%O A001411 0,2
%A A001411 _N. J. A. Sloane_, _Anthony Guttmann_