A117633 - OEIS

%I #17 May 17 2021 04:54:30

%S 1,2,4,8,14,26,48,88,154,278,500,900,1576,2806,4996,8894,15564,27538,

%T 48726,86212,150792,265730,468342,825462,1442866,2535802,4457332,

%U 7835308,13687192,24008300,42118956,73895808,129012260,225966856,395842772,693470658,1210093142,2117089488,3704400974

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

%C 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 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 Robert FERREOL, <a href="/A117633/a117633.gif">The a(4)=14 walks in Manhattan lattice</a>

%H 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 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 Wikipedia, <a href="https://en.wikipedia.org/wiki/Connective_constant">Connective constant</a>

%F a(n) = 2*A006744(n) for n >= 1. - _Robert FERREOL_, Dec 08 2018

%e On each crossing, the first step may follow a street or an avenue. So a(1)=2.

%e 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 # This program explicitly gives the a(n) walks.

%p walks:=proc(n)

%p    option remember;

%p    local i, father, End, X, walkN, dir, u, x, y;

%p    if n=1 then [[[0, 0]]] else

%p         father:=walks(n-1):

%p         walkN:=NULL:

%p         for i to nops(father) do

%p            u:=father[i]:End:=u[n-1]:x:=End[1] mod 2; y:=End[2] mod 2;

%p              dir:=[[(-1)**y, 0], [0, (-1)**x]]:

%p            for X in dir do

%p             if not(member(End+X, u)) then walkN:=walkN, [op(u), End+X]: fi;

%p             od od:

%p         [walkN] fi end:

%p walks(5); # _Robert FERREOL_, Dec 08 2018

%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     X=P[-1]; x=X[0]%2; y=X[1]%2; mo=[[(-1)**y, 0], [0, (-1)**x]]

%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(21)]

%o # _Robert FERREOL_, Dec 08 2018

%Y Cf. A006744, A001411 (square lattice), A322419 (L-lattice).

%K nonn,walk

%O 0,2

%A _R. J. Mathar_, Apr 08 2006

%E Terms from a(29) on by _Robert FERREOL_, Dec 08 2018