A006744 -id:A006744 - 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

A344022 Numbers with binary expansion (b_1, ..., b_m) such that bending a strip of paper of length k+1 with an angle of +90 degrees (resp. -90 degrees) at position X=k when b_k = 1 (resp. b_k = 0) for k = 1..m yields a configuration where all edges are distinct.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 81, 82, 83, 84, 85

Offset: 1

Rémy Sigrist, May 07 2021

All positive terms belong to A166535, but the reverse is not true (for example, A166535(96) = 136 does not belong to this sequence).
This sequence is infinite as it contains A000975 and A343183.
If m belongs to the sequence, then floor(m/2) also belongs to the sequence.
For any k > 0, the sequence contains A006744(k) positive terms with k binary digits.
This sequence has connections with A258002, A255561 and A255571: these sequences encode in binary nonoverlapping or noncrossing paths in the honeycomb lattice.

			See illustration in Links section.

Rémy Sigrist, Illustration of initial terms

Cf. A000975, A006744, A166535, A258002, A255561, A255571, A343183, A344145.

is(n) = { my (b=binary(n), d=1, s=[d], z=2*d); for (k=1, #b, if (b[k], d*=I, d/=I); if (setsearch(s, z+=d), return (0), s=setunion(s, [z]); z+=d)); return (1) }

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