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

1, 2, 4, 9, 20, 46, 105, 244, 567, 1328, 3114, 7334, 17301, 40925, 96955, 230128, 546942, 1301721, 3101513, 7397751, 17661413, 42201765, 100918554, 241504437, 578312697, 1385684687, 3322065246, 7968514308, 19122960036, 45912141148, 110276058832, 264974818317

Offset

0,2

Links

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

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(4) = 20: ENNW, ENWN, ENWW, NENW, NNNN, NNNW, NNWN, NNWW, NWNN, NWNW, NWWN, NWWW, WNNN, WNNW, WNWN, WNWW, WWNN, WWNW, WWWN, WWWW.

Maple

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

Mathematica

b[d_, i_, n_, x_, y_, w_] := b[d, i, n, x, y, w] = If[y + w > n, 0,
  If[n==0, If[y==0 && w==0, 1, 0],
  If[d != 3, b[1, x==0, n-1, Max[x-1, 0], y, w+1], 0] +
  If[d != 4, b[2, y==0, n-1, x, Max[y-1, 0], w], 0] +
  If[d==0 || d==3 || d==2 && i, b[3, False, n-1, x+1, y, Max[w-1, 0]], 0] +
  If[d==0 || d==4 || d==1 && i, b[4, False, n-1, x, y+1, w], 0]]
];
a[n_] := b[0, False, n, 0, 0, 0];
a /@ Range[0, 31] (* Jean-François Alcover, Sep 22 2019, after Alois P. Heinz *)

Crossrefs

Cf. A191605, A191625, A191652.

Sequence in context: A367713 A007902 A057417 * A191827 A000968 A005908

Adjacent sequences: A191650 A191651 A191652 * A191654 A191655 A191656

Keyword

nonn,walk

Author

Alois P. Heinz, Jun 10 2011

Status

approved