OFFSET
0,2
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..400
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) = 34: EEE, EEN, EES, ENE, ENN, ENW, ESE, ESS, NEE, NEN, NES, NNE, NNN, NNW, NWN, NWW, NWS, WNE, WNN, WNW, WWN, WWW, WWS, WSW, WSS, SEE, SEN, SES, SWN, SWW, SWS, SSE, SSW, SSS.
MAPLE
b:= proc(d, i, n, x, y, w) option remember;
`if`(n=0, 1,
`if`(d in [0, 1] or d in [2, 4] and x=0 or d=2 and i,
b(1, evalb(x=0), n-1, max(x-1, 0), y, w+1), 0) +
`if`(d in [0, 2] or d in [1, 3] and (y=0 or i),
b(2, evalb(y=0), n-1, x, max(y-1, 0), w), 0) +
`if`(d in [0, 3] or d in [2, 4] and w=0 or d=2 and i,
b(3, evalb(w=0), n-1, x+1, y, max(w-1, 0)), 0) +
`if`(d in [0, 4] or d in [1, 3] and (s=0 or i),
b(4, false, n-1, x, y+1, w), 0))
end:
a:= n-> b(0, true, 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[n == 0, 1, If [MatchQ[d, 0|1] || MatchQ[d, 2|4] && x == 0 || d == 2 && i, b[1, x == 0, n-1, Max[x-1, 0], y, w+1], 0] + If[MatchQ[d, 0|2] || MatchQ[d, 1|3] && (y == 0 || i), b[2, y == 0, n-1, x, Max[y-1, 0], w], 0] + If[MatchQ[d, 0|3] || MatchQ[d, 2|4] && w == 0 || d == 2 && i, b[3, w == 0, n-1, x+1, y, Max[w-1, 0]], 0] + If[MatchQ[d, 0|4] || MatchQ[d, 1|3] && i, b[4, False, n-1, x, y+1, w], 0]]; a[n_] := b[0, True, n, 0, 0, 0]; Table [a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 20 2014, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn,walk
AUTHOR
Alois P. Heinz, Jun 17 2011
STATUS
approved