A191758 Number of n-step four-sided prudent self-avoiding walks ending at the northwest corner of their box.

1, 2, 4, 10, 24, 60, 146, 362, 894, 2220, 5506, 13686, 34014, 84620, 210538, 524074, 1304662, 3248652, 8089768, 20147228, 50177160, 124972192, 311257258, 775219392, 1930719596, 4808416726, 11974790286, 29820532540, 74257690132

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.

Mireille Bousquet-Mélou, Families of prudent self-avoiding walks, arXiv:0804.4843 [math.CO], 2008-2009.

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

Example

a(3) = 10: ENW, NNN, NNW, NWN, NWW, WNN, WNW, WWN, WWW, SWN.

Maple

b:= proc(d, i, n, x, y, w, s) option remember;
      `if`(n=0, `if`(y=0 and w=0, 1, 0),
         `if`(d in [0, 1] or d in [2, 4] and (x=0 or i),
              b(1, x=0, n-1, max(x-1, 0), y, w+1, s), 0) +
         `if`(d in [0, 2] or d in [1, 3] and (y=0 or i),
              b(2, y=0, n-1, x, max(y-1, 0), w, s+1), 0) +
         `if`(d in [0, 3] or d in [2, 4] and (w=0 or i),
              b(3, w=0, n-1, x+1, y, max(w-1, 0), s), 0) +
         `if`(d in [0, 4] or d in [1, 3] and (s=0 or i),
              b(4, s=0, n-1, x, y+1, w, max(s-1, 0)), 0))
    end:
a:= n-> b(0, true, 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[n == 0, If[y == 0 && w == 0, 1, 0],
  If[d == 0 || d == 1 || (d == 2 || d == 4) && (x == 0 ||i),
    b[1, x == 0, n - 1, Max[x - 1, 0], y, w + 1, s], 0] +
  If[d == 0 || d == 2 || (d == 1 || d == 3) && (y == 0 || i),
    b[2, y == 0, n - 1, x, Max[y - 1, 0], w, s + 1], 0] +
  If[d == 0 || d == 3 || (d == 2 || d == 4) && (w == 0 || i),
    b[3, w == 0, n - 1, x + 1, y, Max[w - 1, 0], s], 0] +
  If[d == 0 || d == 4 || (d == 1 || d == 3) && (s == 0 || i),
    b[4, s == 0, n - 1, x, y + 1, w, Max[s - 1, 0]], 0]
];
a[n_] := b[0, True, n, 0, 0, 0, 0];
a /@ Range[0, 30] (* Jean-François Alcover, Sep 22 2019, after Alois P. Heinz *)

Crossrefs

Cf. A191756, A191757.

Sequence in context: A191828 A065161 A337317 * A038373 A052987 A349365

Adjacent sequences: A191755 A191756 A191757 * A191759 A191760 A191761

Keyword

nonn,walk

Author

Alois P. Heinz, Jun 15 2011

Status

approved