A322419 -id:A322419 - cp's OEIS frontend

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

R. J. Mathar, Apr 08 2006

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

			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.

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

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

# 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

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

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

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

A151798 a(0)=1, a(1)=2, a(n)=4 for n>=2.

Original entry on oeis.org

1, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4

Offset: 0

David Applegate, Jun 29 2009

A010709 preceded by 1, 2.
Partial sums give A131098.
The INVERT transform gives A077996 without A077996(0). The Motzkin transform gives A105696 without A105696(0). Decimal expansion of 28/225=0.12444... . - R. J. Mathar, Jun 29 2009
Continued fraction expansion of 1 + sqrt(1/5). - Arkadiusz Wesolowski, Mar 30 2012
The number of solutions x (mod 2^(n+1)) of x^2 = 1 (mod 2^(n+1)), namely x = 1 (n=0), x = -1, 1 (n=1) and x = -1, 1, 2^n-1, 2^n+1 (n at least 2). - Christopher J. Smyth, May 15 2014
Also, the number of n-step self-avoiding walks on the L-lattice with no non-contiguous adjacencies (see A322419 for details of L-lattice). - Sean A. Irvine, Jul 29 2020

David Applegate, The movie version
Index entries for linear recurrences with constant coefficients, signature (1).

Cf. A010709, A131098, A077996, A105696.

[ n le 1 select n+1 else 4: n in [0..104] ];

f[n_] := Fold[#2*Floor[#1/#2 + 1/2] &, n, Reverse@ Range[n - 1]]; Array[f, 55]

Vec((1+x+2*x^2)/(1-x) + O(x^100)) \\ Altug Alkan, Jan 19 2016

G.f.: (1+x+2*x^2)/(1-x).
E.g.f. A(x)=x*B(x) satisfies the differential equation B'(x)=1+x+x^2+B(x). - Vladimir Kruchinin, Jan 19 2011
E.g.f.: 4*exp(x) - 2*x - 3. - Elmo R. Oliveira, Aug 06 2024

A336724 Number of n-step self-avoiding walks on the half-Manhattan square lattice.

Original entry on oeis.org

1, 3, 7, 17, 37, 83, 181, 399, 863, 1887, 4057, 8797, 18851, 40649, 86911, 186705, 398413, 853407, 1818099, 3885377, 8266359, 17632961, 37473467, 79814011, 169457991, 360469139, 764700473, 1624915019, 3444615545, 7312733017, 15492242679, 32862908109, 69581860921, 147497088201

Offset: 0

Sean A. Irvine, Aug 01 2020

In the half-Manhattan lattice, E-W streets run alternately E and W, but N-S streets are two way.

Sean A. Irvine, Java program (github)

Cf. A336705 (coordination sequence), A336742 (self-avoiding cycles), A117633 (Manhattan lattice), A001411 (square lattice), A322419 (L-lattice).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Python

Formula

Extensions

A151798 a(0)=1, a(1)=2, a(n)=4 for n>=2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A336724 Number of n-step self-avoiding walks on the half-Manhattan square lattice.

Views

Author

Keywords

Comments

Links

Crossrefs