|
%I #28 Jan 31 2024 10:06:20
%S 1,4,12,36,100,276,748,2012,5356,14172,37276,97604,254508,661364,
%T 1713292,4426428,11408300,29339324,75305596,192945124,493554916,
%U 1260643868,3215551292,8191635220,20843850764,52980214316,134527157780,341268196780
%N Number of n-step four-sided prudent self-avoiding walks.
%H Alois P. Heinz, <a href="/A191756/b191756.txt">Table of n, a(n) for n = 0..192</a>
%H M. Bousquet-Mélou, <a href="https://doi.org/10.46298/dmtcs.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.
%p b:= proc(n, x, y, w, s, i) option remember;
%p `if`(n=0, 1, `if`(y>s, b(n, x, s, w, y, i),
%p b(n-1, max(x-1, 0), y, w+1, s, evalb(x=0))+
%p `if`(y=0 or i, b(n-1, max(y-1, 0), w, s+1, x, evalb(y=0)), 0)+
%p `if`(s=0 or i, b(n-1, max(s-1, 0), x, y+1, w, evalb(s=0)), 0)))
%p end:
%p a:= n-> `if`(n=0, 1, 4*b(n-1, 0, 0, 1, 0, true)):
%p seq(a(n), n=0..30);
%t b[n_, x_, y_, w_, s_, i_] := b[n, x, y, w, s, i] = If[n == 0, 1, If[y > s, b[n, x, s, w, y, i], b[n - 1, Max[x - 1, 0], y, w + 1, s, x == 0] + If[y == 0 || i, b[n - 1, Max[y - 1, 0], w, s + 1, x, y == 0], 0] + If[s == 0 || i, b[n - 1, Max[s - 1, 0], x, y + 1, w, s == 0], 0]]];
%t a[n_] := If[n == 0, 1, 4*b[n - 1, 0, 0, 1, 0, True]];
%t Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Jun 23 2017, translated from Maple *)
%Y Cf. A191757, A191758.
%K nonn,walk
%O 0,2
%A _Alois P. Heinz_, Jun 15 2011
|
