A191824 - OEIS

A191824

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

%I #23 Aug 13 2020 22:14:15

%S 1,3,7,19,49,127,327,841,2157,5523,14115,36019,91779,233557,593625,

%T 1507125,3822395,9685135,24518103,62016309,156742115,395865603,

%U 999105203,2519960799,6352014717,16002180569,40291214021,101395244925,255042422247

%N Number of n-step three-sided prudent self-avoiding walks ending on the top side of their box.

%H Alois P. Heinz, <a href="/A191824/b191824.txt">Table of n, a(n) for n = 0..250</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 Mireille Bousquet-Mélou, <a href="https://arxiv.org/abs/0804.4843">Families of prudent self-avoiding walks</a>, arXiv:0804.4843 [math.CO], 2008-2009.

%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) option remember;

%p `if`(y>n, 0, `if`(n=0, `if`(y=0, 1, 0),

%p `if`(d in [0, 1] or d in [2, 4] and x=0 or d=2 and i,

%p b(1, evalb(x=0), n-1, max(x-1, 0), y, w+1), 0) +

%p `if`(d in [0, 2] or d in [1, 3] and (y=0 or i),

%p b(2, evalb(y=0), n-1, x, max(y-1, 0), w), 0) +

%p `if`(d in [0, 3] or d in [2, 4] and w=0 or d=2 and i,

%p b(3, evalb(w=0), n-1, x+1, y, max(w-1, 0)), 0) +

%p `if`(d in [0, 4] or d in [1, 3] and i,

%p b(4, false, n-1, x, y+1, w), 0)))

%p end:

%p a:= n-> b(0, true, n, 0, 0, 0):

%p seq(a(n), n=0..30);

%t b[d_, i_, n_, x_, y_, w_] := b[d, i, n, x, y, w] = If[y>n, 0, If[n == 0, If[n == 0, 1, 0], 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_, Dec 22 2014, after _Alois P. Heinz_ *)

%Y Cf. A191823, A191825, A191826, A191827, A191828.

%K nonn,walk

%O 0,2

%A _Alois P. Heinz_, Jun 17 2011