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

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

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

Table of n, a(n) for n=0..38.

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[1] mod 2; y:=End[2] 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[0]%2; y=X[1]%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: A365253 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