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

Author

R. J. Mathar, Apr 08 2006

Keywords

• nonn
• walk

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

Examples

			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.
		

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

Crossrefs

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

Programs

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

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

Formula

a(n) = 2*A006744(n) for n >= 1. - Robert FERREOL, Dec 08 2018

Extensions

Terms from a(29) on by Robert FERREOL, Dec 08 2018