|
|
A001411
|
|
Number of n-step self-avoiding walks on square lattice.
(Formerly M3448 N1402)
|
|
87
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
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
|
|
|
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:
to 12 do walks:=map(x->extend(x), walks): A001411:=A001411, nops(walks) od:
|
|
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 *)
|
|
PROG
|
(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)]
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,walk,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|