A191756 Number of n-step four-sided prudent self-avoiding walks.

1, 4, 12, 36, 100, 276, 748, 2012, 5356, 14172, 37276, 97604, 254508, 661364, 1713292, 4426428, 11408300, 29339324, 75305596, 192945124, 493554916, 1260643868, 3215551292, 8191635220, 20843850764, 52980214316, 134527157780, 341268196780

Offset

0,2

Links

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

M. Bousquet-Mélou, Families of prudent self-avoiding walks, DMTCS proc. AJ, 2008, 167-180.

Enrica Duchi, On some classes of prudent walks, in: FPSAC'05, Taormina, Italy, 2005.

Maple

b:= proc(n, x, y, w, s, i) option remember;
      `if`(n=0, 1, `if`(y>s, b(n, x, s, w, y, i),
                     b(n-1, max(x-1, 0), y, w+1, s, evalb(x=0))+
      `if`(y=0 or i, b(n-1, max(y-1, 0), w, s+1, x, evalb(y=0)), 0)+
      `if`(s=0 or i, b(n-1, max(s-1, 0), x, y+1, w, evalb(s=0)), 0)))
    end:
a:= n-> `if`(n=0, 1, 4*b(n-1, 0, 0, 1, 0, true)):
seq(a(n), n=0..30);

Mathematica

b[n_, x_, y_, w_, s_, i_] := b[n, x, y, w, s, i] = If[n == 0, 1, If[y > s, b[n, x, s, w, y, i], b[n - 1, Max[x - 1, 0], y, w + 1, s, x == 0] + If[y == 0 || i, b[n - 1, Max[y - 1, 0], w, s + 1, x, y == 0], 0] + If[s == 0 || i, b[n - 1, Max[s - 1, 0], x, y + 1, w, s == 0], 0]]];
a[n_] :=  If[n == 0, 1, 4*b[n - 1, 0, 0, 1, 0, True]];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jun 23 2017, translated from Maple *)

Crossrefs

Cf. A191757, A191758.

Sequence in context: A192626 A294782 A002906 * A001411 A095350 A084776

Adjacent sequences: A191753 A191754 A191755 * A191757 A191758 A191759

Keyword

nonn,walk

Author

Alois P. Heinz, Jun 15 2011

Status

approved