login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A322419 Number of n-step self-avoiding walks on L-lattice. 4
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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

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

FORMULA

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

EXAMPLE

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

MAPLE

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.

MATHEMATICA

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

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], [-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)]

CROSSREFS

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

Sequence in context: A103258 A100684 A131770 * A246850 A294066 A163489

Adjacent sequences:  A322416 A322417 A322418 * A322420 A322421 A322422

KEYWORD

nonn,walk

AUTHOR

Robert FERREOL, Dec 07 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 June 15 02:56 EDT 2021. Contains 345042 sequences. (Running on oeis4.)