login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A117633 Number of self-avoiding walks of n steps on a Manhattan square lattice. 3
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 (list; graph; refs; listen; history; text; internal format)
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: A317884 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 21 16:04 EST 2019. Contains 329371 sequences. (Running on oeis4.)