A328139 - OEIS

%I #13 May 13 2020 07:02:13

%S 1,1,2,4,11,29,80,222,622,1758,5000,14296,41049,118281,341852,990570,

%T 2876821,8371453,24403371,71248708,208311036,609812089,1787215592,

%U 5243371099,15397785369,45257023128,133126287754,391890954915,1154427358177,3402881326012

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

%H Alois P. Heinz, <a href="/A328139/b328139.txt">Table of n, a(n) for n = 0..2100</a>

%H Alois P. Heinz, <a href="/A328139/a328139.gif">Animation of a(7) = 222 walks</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Lattice_path">Lattice path</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Self-avoiding_walk">Self-avoiding walk</a>

%p b:= proc(x, y, t) option remember; `if`(x<0 or

%p        abs(y)>2*x, 0, `if`(x=0, 1, b(x-1, y, 1)+

%p       `if`(t=1, b(x-1, y+1, 0)+b(x+1, y-1, 0), 0)))

%p     end:

%p a:= n-> b(n, 0$2):

%p seq(a(n), n=0..32);

%t 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]]];

%t a[n_] := b[n, 0, 0];

%t a /@ Range[0, 32] (* _Jean-François Alcover_, May 13 2020, after Maple *)

%Y Cf. A328140.

%K nonn,walk

%O 0,3

%A _Alois P. Heinz_, Oct 04 2019