A117633 -id:A117633 - cp's OEIS frontend

A336627 Coordination sequence for the Manhattan lattice.

1, 2, 4, 8, 11, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, 80, 84, 88, 92, 96, 100, 104, 108, 112, 116, 120, 124, 128, 132, 136, 140, 144, 148, 152, 156, 160, 164, 168, 172, 176, 180, 184, 188, 192, 196, 200, 204, 208, 212, 216, 220, 224

Offset: 0

Sean A. Irvine, Jul 28 2020

In the Manhattan lattice, N-S streets run alternately N and S, and E-W streets run alternately E and W. - N. J. A. Sloane, Jul 29 2020

Sean A. Irvine, Illustration of a(0) to a(7)
N. J. A. Sloane, Crude drawing of initial layers showing paths of length 6 from origin (looking North-West). The presence of three points at distance 4 from the origin on the line of symmetry explains why a(4) is odd!
Index entries for linear recurrences with constant coefficients, signature (2,-1).

Cf. A008574 (square lattice), A117633 (self-avoiding walks).

CoefficientList[Series[(1+x^2)(1+2x^3-x^4)/(1-x)^2,{x,0,80}],x] (* or *) LinearRecurrence[{2,-1},{1,2,4,8,11,16,20},80] (* Harvey P. Dale, Dec 28 2021 *)

a(n)=if(n>4, 4*n-4, min(2^n, 11)) \\ Charles R Greathouse IV, Oct 18 2022

G.f.: (1+x^2) * (1+2*x^3-x^4) / (1-x)^2.

a(n) = 4*(n-1), n >= 5.

A322419 Number of n-step self-avoiding walks on L-lattice.

Original entry on oeis.org

1, 2, 4, 8, 12, 20, 32, 52, 84, 136, 220, 356, 564, 904, 1448, 2320, 3684, 5872, 9376, 14960, 23688, 37652, 59912, 95316, 150744, 239080, 379528, 602424, 951788, 1507136, 2388252, 3784344, 5973988, 9447880, 14950796, 23658540, 37321752, 58965260, 93206864, 147333080, 232286272

Offset: 0

Robert FERREOL, Dec 07 2018

The L-lattice is an oriented square lattice in which each step must be followed by a step perpendicular to the preceding one.

			a(1) = 2 because there are only two possible directions at each intersection; for the same reason a(2) = 2*2 and a(3) = 2*4 ; but a(4) = 12 (not 16) because four paths return to the starting point and are not self-avoiding. See the 12 paths under "links".

Sean A. Irvine, Table of n, a(n) for n = 0..50
Robert FERREOL, The a(4)=12 walks in L-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, Journal of Physics A: Mathematical and General, Volume 8, Number 12 (1975), page 1890.
Wikipedia, Connective constant

Cf. A001411 (square lattice), A117633 (Manhattan lattice), A189722, A004277 (coordination sequence), A151798.

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]:if n mod 2 = 0 then
            dir:=[[1,0], [-1, 0]] else dir := [[0,1], [0, -1]] fi:
            for X in dir do
             if not(member(End+X,u)) then walkN:=walkN,[op(u),End+X] fi;
             od od:
         [walkN] fi end:
n:=5:L:=walks(n):N:=nops(L);
# This program explicitly gives the a(n) walks.

mo = {{1, 0}, {-1, 0}}; moo = {{0, 1}, {0, -1}}; a[0] = 1;
a[tg_, p_: {{0, 0}}] := Module[{e, mv},
If[Mod[tg, 2] == 0, mv = Complement[Last[p] + # & /@ mo, p],
mv = Complement[Last[p] + # & /@ moo, p]];
If[tg == 1, Length@mv, Sum[a[tg - 1, Append[p, e]], {e, mv}]]];
a /@ Range[0, 20] (* after the program from Giovanni Resta at A001411 *)

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], [-1, 0]]
moo = [[0, 1], [0, -1]]
def a(n, P=[[0, 0]]):
    if n == 0:
        return 1
    if n % 2 == 0:
        mv1 = [plus(P[-1], x) for x in mo]
    else:
        mv1 = [plus(P[-1], x) for x in moo]
    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)]

a(n) = 4*A189722(n) for n >= 2.

It is proved that a(n)^(1/n) has a limit mu called the "connective constant" of the L-lattice; approximate value of mu: 1.5657. It is only conjectured that a(n + 1) ~ mu * a(n).

A006744 Number of n-step self-avoiding walks on a Manhattan lattice.

Original entry on oeis.org

1, 2, 4, 7, 13, 24, 44, 77, 139, 250, 450, 788, 1403, 2498, 4447, 7782, 13769, 24363, 43106, 75396, 132865, 234171, 412731, 721433, 1267901, 2228666, 3917654, 6843596, 12004150, 21059478, 36947904, 64506130, 112983428, 197921386, 346735329, 605046571, 1058544744, 1852200487

Offset: 1

Simon Plouffe

It seems that a(n) = A117633(n)/2 (the two sequences have similar names). Sequence A117633 is based on the paper by Malakis (1975). - Petros Hadjicostas, Jan 02 2019

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

H. Jamke, Table of n, a(n) for n=1..53 [From Herman Jamke (hermanjamke(AT)fastmail.fm), Sep 13 2010]
D. Bennett-Wood, J. L. Cardy, I. Enting, A. J. Guttmann and A. L. Owczarek, On the Non-Universality of a Critical Exponent for Self-Avoiding Walks, Nuc. Phys. B, 528, 533-552, 1998. [From Herman Jamke (hermanjamke(AT)fastmail.fm), Sep 13 2010] Also wayback, or arxiv:9805146.
A. Malakis, Self-avoiding walks on oriented square lattices, J. Phys. A: Math. Gen. 8 (1975), no 12, 1885-1898.
S. S. Manna and A. J. Guttmann, Kinetic growth walks and trails on oriented square lattices: Hull percolation and percolation hulls, J. Phys. A 22 (1989), 3113-3122.

Cf. A117633.

A336662 Number of n-step self-avoiding walks on the Manhattan lattice with no non-contiguous adjacencies.

Original entry on oeis.org

1, 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, 282, 452, 724, 1160, 1842, 2936, 4688, 7480, 11844, 18826, 29956, 47658, 75372, 119540, 189764, 301212, 475894, 753568, 1194126, 1892172, 2986994, 4723940, 7475398, 11829270, 18660876, 29482630, 46603432, 73666540

Offset: 0

Sean A. Irvine, Jul 28 2020

Adjacencies are forbidden regardless of the direction of the Manhattan lattice at the point in question.

Sean A. Irvine, Table of n, a(n) for n = 0..50
Sean A. Irvine, Java program (github)

Cf. A117633 (without adjacency requirements), A173380 (square lattice).

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).

A364580 Number of n-step self-avoiding walks on the square Manhattan lattice that do not take two consecutive turns.

Original entry on oeis.org

1, 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, 288, 460, 740, 1192, 1918, 3064, 4910, 7872, 12620, 20114, 32150, 51396, 82160, 130730, 208506, 332616, 530588, 843222, 1342662, 2138280, 3405346, 5406522, 8597632, 13674278, 21748530, 34501460, 54807754, 87077354

Offset: 0

David Galvin, Jul 28 2023

The square Manhattan lattice is an oriented square lattice in which the orientations are constant along horizontal and vertical lines, with pairs of consecutive lines having alternating orientations (similar to a generic portion of the streets and avenues of midtown Manhattan).
In the hard-core (independent set) model on the ordinary two-dimensional integer lattice, the contours separating odd-occupied regions from even-occupied regions can be viewed as self-avoiding walks on the square Manhattan lattice that do take two consecutive turns. It follows via a standard Peierls argument that if a(n) grows like mu^n then the hard-core model on the ordinary two-dimensional integer lattice exhibits phase coexistence for all values of the fugacity above mu^4-1. See the Blanca, Chen, Galvin, Randall and Tetali reference for details.
In the Blanca et al. reference these are called "taxi walks" because a savvy passenger in a Manhattan cab would be suspicious if the cab took two consecutive turns.

			With the x-axis and the y-axis both oriented positively, here are the 6 walks of length 3:
 * (0,0)-(1,0)-(2,0)-(3,0)
 * (0,0)-(1,0)-(2,0)-(2,1)
 * (0,0)-(1,0)-(1,-1)-(1,-2)
 * (0,0)-(0,1)-(0,2)-(0,3)
 * (0,0)-(0,1)-(0,2)-(1,2)
 * (0,0)-(0,1)-(-1,1)-(-2,1)
The following is not a valid walk, because it takes two consecutive turns:
 * (0,0)-(1,0)-(1,-1)-(0,-1)

A. Blanca, Y. Chen, D. Galvin, D. Randall and P. Tetali, Phase Coexistence for the Hard-Core Model on Z^2, Combinatorics, Probability and Computing, 28 (2019), 1-22.

A. Blanca, Y. Chen, D. Galvin, D. Randall and P. Tetali, Phase Coexistence for the Hard-Core Model on Z^2, arXiv:1611.01115 [math.PR], 2016-2018.
Haoquan Liang, Phase Coexistence for the Hard-Core Model on Z^2: Improved Bounds, Penn State Honors Thesis, Spring 2021.

A117633 gives the number of self-avoiding walks on the square Manhattan lattice without the restriction on consecutive turns.

a(n) = f(n)*mu^n where mu is a constant and f(n) is subexponential in n. This follows from the subadditivity of log a(n). See the Blanca, Chen, Galvin, Randall and Tetali reference for details.

mu is known to lie between 1.5186 and 1.5874. See the Blanca et al. reference for the lower bound, and the Liang link for the upper bound.

cp's OEIS Frontend

A336627 Coordination sequence for the Manhattan lattice.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A322419 Number of n-step self-avoiding walks on L-lattice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A006744 Number of n-step self-avoiding walks on a Manhattan lattice.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A336662 Number of n-step self-avoiding walks on the Manhattan lattice with no non-contiguous adjacencies.

Views

Author

Keywords

Comments

Links

Crossrefs

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

Views

Author

Keywords

Comments

Links

Crossrefs

A364580 Number of n-step self-avoiding walks on the square Manhattan lattice that do not take two consecutive turns.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula