cp's OEIS Frontend

A117633 Number of self-avoiding walks of n steps on a Manhattan square lattice.

%I A117633 #17 May 17 2021 04:54:30
%S A117633 1,2,4,8,14,26,48,88,154,278,500,900,1576,2806,4996,8894,15564,27538,
%T A117633 48726,86212,150792,265730,468342,825462,1442866,2535802,4457332,
%U A117633 7835308,13687192,24008300,42118956,73895808,129012260,225966856,395842772,693470658,1210093142,2117089488,3704400974
%N A117633 Number of self-avoiding walks of n steps on a Manhattan square lattice.
%C A117633 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
%H A117633 M. N. Barber, <a href="https://doi.org/10.1016/0031-8914(70)90024-8">Asymptotic results for self-avoiding walks on a Manhattan lattice</a>, Physica, Volume 48, Issue 2, (1970), page 240.
%H A117633 Robert FERREOL, <a href="/A117633/a117633.gif">The a(4)=14 walks in Manhattan lattice</a>
%H A117633 Keh-Ying Lin and Yee-Mou Kao, <a href="https://doi.org/10.1088/0305-4470/32/40/303">Universal amplitude combinations for self-avoiding walks and polygons on directed lattices</a>, J. Phys. A: Math. Gen. 32 (1999), page 6929.
%H A117633 A. Malakis, <a href="https://doi.org/10.1088/0305-4470/8/12/007">Self-avoiding walks on oriented square lattices</a>, J. Phys. A: Math. Gen. 8 (1975), no 12, 1885-1898.
%H A117633 Wikipedia, <a href="https://en.wikipedia.org/wiki/Connective_constant">Connective constant</a>
%F A117633 a(n) = 2*A006744(n) for n >= 1. - _Robert FERREOL_, Dec 08 2018
%e A117633 On each crossing, the first step may follow a street or an avenue. So a(1)=2.
%e A117633 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.
%p A117633 # This program explicitly gives the a(n) walks.
%p A117633 walks:=proc(n)
%p A117633    option remember;
%p A117633    local i, father, End, X, walkN, dir, u, x, y;
%p A117633    if n=1 then [[[0, 0]]] else
%p A117633         father:=walks(n-1):
%p A117633         walkN:=NULL:
%p A117633         for i to nops(father) do
%p A117633            u:=father[i]:End:=u[n-1]:x:=End[1] mod 2; y:=End[2] mod 2;
%p A117633              dir:=[[(-1)**y, 0], [0, (-1)**x]]:
%p A117633            for X in dir do
%p A117633             if not(member(End+X, u)) then walkN:=walkN, [op(u), End+X]: fi;
%p A117633             od od:
%p A117633         [walkN] fi end:
%p A117633 walks(5); # _Robert FERREOL_, Dec 08 2018
%o A117633 (Python)
%o A117633 def add(L, x):
%o A117633     M=[y for y in L]; M.append(x)
%o A117633     return M
%o A117633 plus=lambda L, M:[x+y for x, y in zip(L, M)]
%o A117633 mo=[[1, 0], [0, 1], [-1, 0], [0, -1]]
%o A117633 def a(n, P=[[0, 0]]):
%o A117633     if n==0: return 1
%o A117633     X=P[-1]; x=X[0]%2; y=X[1]%2; mo=[[(-1)**y, 0], [0, (-1)**x]]
%o A117633     mv1 = [plus(P[-1], x) for x in mo]
%o A117633     mv2=[x for x in mv1 if x not in P]
%o A117633     if n==1: return len(mv2)
%o A117633     else: return sum(a(n-1, add(P, x)) for x in mv2)
%o A117633 [a(n) for n in range(21)]
%o A117633 # _Robert FERREOL_, Dec 08 2018
%Y A117633 Cf. A006744, A001411 (square lattice), A322419 (L-lattice).
%K A117633 nonn,walk
%O A117633 0,2
%A A117633 _R. J. Mathar_, Apr 08 2006
%E A117633 Terms from a(29) on by _Robert FERREOL_, Dec 08 2018