|
%I #23 May 13 2020 09:53:29
%S 1,4,8,20,46,110,260,616,1456,3442,8134,19218,45394,107204,253140,
%T 597666,1410948,3330622,7861542,18555092,43792062,103349390,243895352,
%U 575552060,1358167086,3204874310,7562397040,17844314546,42104959766,99348325696,234413460808
%N Number of two-sided n-step prudent walks avoiding two or more consecutive west steps and two or more consecutive south steps.
%H Alois P. Heinz, <a href="/A190589/b190589.txt">Table of n, a(n) for n = 0..800</a>
%H Shanzhen Gao, Keh-Hsun Chen, <a href="http://worldcomp-proceedings.com/proc/p2014/FCS2696.pdf">Tackling Sequences From Prudent Self-Avoiding Walks</a>, FCS'14, The 2014 International Conference on Foundations of Computer Science.
%F G.f.: 1/((1-2*t-t^2+t^3)*(1-2*t-2*t^3))*(t*(1-t)^2*sqrt((1-t-t^3)^2-4*t^4)+1-t-2*t^2-2*t^4+4*t^5-t^6), see sequence 13 in link. - _Michel Marcus_, May 06 2015
%p b:= proc(d, i, n, x, y) option remember;
%p `if`(n=0, 1,
%p `if`(d<>3, b(1, x=0, n-1, max(x-1,0), y), 0) +
%p `if`(d<>4, b(2, y=0, n-1, x, max(y-1,0)), 0) +
%p `if`(d=0 or d=2 and i, b(3, false, n-1, x+1, y), 0) +
%p `if`(d=0 or d=1 and i, b(4, false, n-1, x, y+1), 0))
%p end:
%p a:= n-> b(0, false, n, 0, 0):
%p seq(a(n), n=0..30); # _Alois P. Heinz_, Jun 09 2011
%t b[d_, i_, n_, x_, y_] := b[d, i, n, x, y] =
%t If[n == 0, 1,
%t If[d != 3, b[1, x == 0, n - 1, Max[x - 1, 0], y], 0] +
%t If[d != 4, b[2, y == 0, n - 1, x, Max[y - 1, 0]], 0] +
%t If[d == 0 || d == 2 && i, b[3, False, n - 1, x + 1, y], 0] +
%t If[d == 0 || d == 1 && i, b[4, False, n - 1, x, y + 1], 0]
%t ];
%t a[n_] := b[0, False, n, 0, 0];
%t a /@ Range[0, 30] (* _Jean-François Alcover_, May 13 2020, after _Alois P. Heinz_ *)
%Y Equals 2*A190586 - A190587.
%K nonn,walk
%O 0,2
%A _Shanzhen Gao_, May 13 2011
%E More terms from _Alois P. Heinz_, Jun 09 2011
|
