The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A117633 Number of self-avoiding walks of n steps on a Manhattan square lattice. 6
 1, 2, 4, 8, 14, 26, 48, 88, 154, 278, 500, 900, 1576, 2806, 4996, 8894, 15564, 27538, 48726, 86212, 150792, 265730, 468342, 825462, 1442866, 2535802, 4457332, 7835308, 13687192, 24008300, 42118956, 73895808, 129012260, 225966856, 395842772, 693470658, 1210093142, 2117089488, 3704400974 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,2 COMMENTS It is proved that a(n)^(1/n) has a limit mu called the "connective constant" of the Manhattan lattice; approximate value of mu: 1.733735. It is only conjectured that a(n + 1) ~ mu * a(n). - Robert FERREOL, Dec 08 2018 LINKS M. N. Barber, Asymptotic results for self-avoiding walks on a Manhattan lattice, Physica, Volume 48, Issue 2, (1970), page 240. Robert FERREOL, The a(4)=14 walks in Manhattan lattice Keh-Ying Lin and Yee-Mou Kao, Universal amplitude combinations for self-avoiding walks and polygons on directed lattices, J. Phys. A: Math. Gen. 32 (1999), page 6929. A. Malakis, Self-avoiding walks on oriented square lattices, J. Phys. A: Math. Gen. 8 (1975), no 12, 1885-1898. Wikipedia, Connective constant FORMULA a(n) = 2*A006744(n) for n >= 1. - Robert FERREOL, Dec 08 2018 EXAMPLE On each crossing, the first step may follow a street or an avenue. So a(1)=2. On the next crossing, each of these 2 paths faces again two choices, giving a(2)=4. At n=4, a(4) becomes less than 16 considering the 2 cases of having moved around a block. MAPLE # This program explicitly gives the a(n) walks. walks:=proc(n)    option remember;    local i, father, End, X, walkN, dir, u, x, y;    if n=1 then [[[0, 0]]] else         father:=walks(n-1):         walkN:=NULL:         for i to nops(father) do            u:=father[i]:End:=u[n-1]:x:=End mod 2; y:=End mod 2;              dir:=[[(-1)**y, 0], [0, (-1)**x]]:            for X in dir do             if not(member(End+X, u)) then walkN:=walkN, [op(u), End+X]: fi;             od od:         [walkN] fi end: walks(5); # Robert FERREOL, Dec 08 2018 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     X=P[-1]; x=X%2; y=X%2; mo=[[(-1)**y, 0], [0, (-1)**x]]     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(21)] # Robert FERREOL, Dec 08 2018 CROSSREFS Cf. A006744, A001411 (square lattice), A322419 (L-lattice). Sequence in context: A317884 A054193 A305003 * A308148 A273154 A135491 Adjacent sequences:  A117630 A117631 A117632 * A117634 A117635 A117636 KEYWORD nonn,walk AUTHOR R. J. Mathar, Apr 08 2006 EXTENSIONS Terms from a(29) on by Robert FERREOL, Dec 08 2018 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 18 17:51 EDT 2021. Contains 345120 sequences. (Running on oeis4.)