A303477 Number of self-avoiding planar walks starting at (0,0), ending at (n,0), remaining in the first quadrant and using steps (0,1), (1,0), (1,1), (-1,1), and (1,-1) with the restrictions that (0,1) and (1,-1) are never used above the diagonal and (1,0) and (-1,1) are never used below the diagonal and (1,1) can only be used below the diagonal.

1, 1, 2, 5, 16, 51, 186, 675, 2619, 10222, 41278, 168322, 699654, 2936170, 12472461, 53415773, 230718087, 1003219186, 4390238536, 19317023478, 85423978859, 379448391283, 1692394492863, 7576241773049, 34031365237595, 153338751409238, 692894165597139

Offset

0,3

Links

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

Alois P. Heinz, Animation of a(6)=186 walks

Wikipedia, Lattice path

Wikipedia, Self-avoiding walk

Maple

b:= proc(x, y) option remember; `if`(x<0 or y<0, 0,
     `if`(x=0 and y=0, 1, `if`(x>y-2, b(x, y-1), 0)+
     `if`(x<y+2, b(x-1, y), 0)+`if`(x>y, b(x-1, y-1), 0)+
     `if`(x<y-1, b(x+1, y-1), 0)+`if`(x>y+1, b(x-1, y+1), 0)))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..30);

Mathematica

b[x_, y_] := b[x, y] = If[x < 0 || y < 0, 0,
  If[x == 0 && y == 0, 1, If[x > y - 2, b[x, y - 1], 0] +
  If[x < y + 2, b[x - 1, y], 0] + If[x > y, b[x - 1, y - 1], 0] +
  If[x < y - 1, b[x + 1, y - 1], 0] + If[x > y + 1, b[x - 1, y + 1], 0]]];
a[n_] := b[n, 0];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jun 02 2018, from Maple *)

Crossrefs

Cf. A303478.

Sequence in context: A108529 A268213 A231357 * A234843 A011819 A148390

Adjacent sequences: A303474 A303475 A303476 * A303478 A303479 A303480

Keyword

nonn,walk

Author

Alois P. Heinz, Apr 24 2018

Status

approved