A191756 - OEIS

%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