A328139 Number of self-avoiding planar walks starting at (0,0), ending at (n,0), not extending above the line (x,2x) or below the line (x,-2x), and using steps (0,1), (-1,1), and (1,-1) with the restriction that (-1,1) and (1,-1) are always immediately followed by (0,1).

1, 1, 2, 4, 11, 29, 80, 222, 622, 1758, 5000, 14296, 41049, 118281, 341852, 990570, 2876821, 8371453, 24403371, 71248708, 208311036, 609812089, 1787215592, 5243371099, 15397785369, 45257023128, 133126287754, 391890954915, 1154427358177, 3402881326012

Offset

0,3

Links

Alois P. Heinz, Table of n, a(n) for n = 0..2100

Alois P. Heinz, Animation of a(7) = 222 walks

Wikipedia, Lattice path

Wikipedia, Self-avoiding walk

Maple

b:= proc(x, y, t) option remember; `if`(x<0 or
       abs(y)>2*x, 0, `if`(x=0, 1, b(x-1, y, 1)+
      `if`(t=1, b(x-1, y+1, 0)+b(x+1, y-1, 0), 0)))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..32);

Mathematica

b[x_, y_, t_] := b[x, y, t] = If[x < 0 || Abs[y] > 2 x, 0, If[x==0, 1, b[x - 1, y, 1] + If[t==1, b[x - 1, y + 1, 0] + b[x + 1, y - 1, 0], 0]]];
a[n_] := b[n, 0, 0];
a /@ Range[0, 32] (* Jean-François Alcover, May 13 2020, after Maple *)

Crossrefs

Cf. A328140.

Sequence in context: A118311 A132836 A148140 * A369359 A148141 A317879

Adjacent sequences: A328136 A328137 A328138 * A328140 A328141 A328142

Keyword

nonn,walk

Author

Alois P. Heinz, Oct 04 2019

Status

approved