|
%I #23 Aug 13 2020 22:13:59
%S 1,3,7,19,49,129,333,865,2233,5763,14825,38087,97641,249961,638861,
%T 1630681,4156737,10583483,26916167,68383509,173565889,440133159,
%U 1115145081,2823128197,7141682287,18053470305,45606579731,115137581735,290498368253
%N Number of n-step four-sided prudent self-avoiding walks ending on the top side of their box.
%H Alois P. Heinz, <a href="/A191757/b191757.txt">Table of n, a(n) for n = 0..100</a>
%H Mireille Bousquet-Mélou, <a href="https://dmtcs.episciences.org/3627">Families of prudent self-avoiding walks</a>, DMTCS proc. AJ, 2008, 167-180.
%H Enrica Duchi, <a href="https://hal.archives-ouvertes.fr/hal-00159320">On some classes of prudent walks</a>, in: FPSAC'05, Taormina, Italy, 2005.
%e a(3) = 19: EEE, EEN, ENE, ENN, ENW, NEE, NEN, NNE, NNN, NNW, NWN, NWW, WNE, WNN, WNW, WWN, WWW, SEN, SWN.
%p b:= proc(d, i, n, x, y, w, s)
%p if w<x then b([3,2,1,4][d], i, n, w, y, x, s)
%p else b(d, i, n, x, y, w, s):=
%p `if`(y>n, 0, `if`(n=0, `if`(y=0, 1, 0),
%p `if`(d in [0, 1] or d<>3 and (x=0 or i),
%p b(1, evalb(x=0), n-1, max(x-1, 0), y, w+1, s), 0) +
%p `if`(d in [0, 2] or d<>4 and (y=0 or i),
%p b(2, evalb(y=0), n-1, x, max(y-1, 0), w, s+1), 0) +
%p `if`(d in [0, 3] or d<>1 and (w=0 or i),
%p b(3, evalb(w=0), n-1, x+1, y, max(w-1, 0), s), 0) +
%p `if`(d in [0, 4] or d<>2 and (s=0 or i),
%p b(4, evalb(s=0), n-1, x, y+1, w, max(s-1, 0)), 0)))
%p fi
%p end:
%p a:= n-> b(0, false, n, 0, 0, 0, 0):
%p seq(a(n), n=0..30);
%t 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]]]];
%t a[n_] := b[0, False, n, 0, 0, 0, 0];
%t Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Jun 23 2017, translated from Maple *)
%Y Cf. A191756, A191758.
%K nonn,walk
%O 0,2
%A _Alois P. Heinz_, Jun 15 2011
|
