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[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
KEYWORD
nonn,walk
AUTHOR
R. J. Mathar, Apr 08 2006
EXTENSIONS
Terms from a(29) on by Robert FERREOL, Dec 08 2018
STATUS
approved