A191757 Number of n-step four-sided prudent self-avoiding walks ending on the top side of their box.

1, 3, 7, 19, 49, 129, 333, 865, 2233, 5763, 14825, 38087, 97641, 249961, 638861, 1630681, 4156737, 10583483, 26916167, 68383509, 173565889, 440133159, 1115145081, 2823128197, 7141682287, 18053470305, 45606579731, 115137581735, 290498368253

Offset

0,2

Links

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

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

Example

a(3) = 19: EEE, EEN, ENE, ENN, ENW, NEE, NEN, NNE, NNN, NNW, NWN, NWW, WNE, WNN, WNW, WWN, WWW, SEN, SWN.

Maple

b:= proc(d, i, n, x, y, w, s)
      if w<x then b([3, 2, 1, 4][d], i, n, w, y, x, s)
    else b(d, i, n, x, y, w, s):=
         `if`(y>n, 0, `if`(n=0, `if`(y=0, 1, 0),
         `if`(d in [0, 1] or d<>3 and (x=0 or i),
              b(1, evalb(x=0), n-1, max(x-1, 0), y, w+1, s), 0) +
         `if`(d in [0, 2] or d<>4 and (y=0 or i),
              b(2, evalb(y=0), n-1, x, max(y-1, 0), w, s+1), 0) +
         `if`(d in [0, 3] or d<>1 and (w=0 or i),
              b(3, evalb(w=0), n-1, x+1, y, max(w-1, 0), s), 0) +
         `if`(d in [0, 4] or d<>2 and (s=0 or i),
              b(4, evalb(s=0), n-1, x, y+1, w, max(s-1, 0)), 0)))
      fi
    end:
a:= n-> b(0, false, n, 0, 0, 0, 0):
seq(a(n), n=0..30);

Mathematica

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

Crossrefs

Cf. A191756, A191758.

Sequence in context: A370169 A007288 A191824 * A061646 A017926 A017927

Adjacent sequences: A191754 A191755 A191756 * A191758 A191759 A191760

Keyword

nonn,walk

Author

Alois P. Heinz, Jun 15 2011

Status

approved