login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A190589 Number of two-sided n-step prudent walks avoiding two or more consecutive west steps and two or more consecutive south steps. 1
1, 4, 8, 20, 46, 110, 260, 616, 1456, 3442, 8134, 19218, 45394, 107204, 253140, 597666, 1410948, 3330622, 7861542, 18555092, 43792062, 103349390, 243895352, 575552060, 1358167086, 3204874310, 7562397040, 17844314546, 42104959766, 99348325696, 234413460808 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..800

Shanzhen Gao, Keh-Hsun Chen, Tackling Sequences From Prudent Self-Avoiding Walks, FCS'14, The 2014 International Conference on Foundations of Computer Science.

FORMULA

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

MAPLE

b:= proc(d, i, n, x, y) option remember;

      `if`(n=0, 1,

         `if`(d<>3, b(1, x=0, n-1, max(x-1, 0), y), 0) +

         `if`(d<>4, b(2, y=0, n-1, x, max(y-1, 0)), 0) +

         `if`(d=0 or d=2 and i, b(3, false, n-1, x+1, y), 0) +

         `if`(d=0 or d=1 and i, b(4, false, n-1, x, y+1), 0))

    end:

a:= n-> b(0, false, n, 0, 0):

seq(a(n), n=0..30);  # Alois P. Heinz, Jun 09 2011

MATHEMATICA

b[d_, i_, n_, x_, y_] := b[d, i, n, x, y] =

If[n == 0, 1,

  If[d != 3, b[1, x == 0, n - 1, Max[x - 1, 0], y], 0] +

  If[d != 4, b[2, y == 0, n - 1, x, Max[y - 1, 0]], 0] +

  If[d == 0 || d == 2 && i, b[3, False, n - 1, x + 1, y], 0] +

  If[d == 0 || d == 1 && i, b[4, False, n - 1, x, y + 1], 0]

];

a[n_] := b[0, False, n, 0, 0];

a /@ Range[0, 30] (* Jean-Fran├žois Alcover, May 13 2020, after Alois P. Heinz *)

CROSSREFS

Equals 2*A190586 - A190587.

Sequence in context: A334706 A095804 A084219 * A009916 A203167 A123861

Adjacent sequences:  A190586 A190587 A190588 * A190590 A190591 A190592

KEYWORD

nonn,walk

AUTHOR

Shanzhen Gao, May 13 2011

EXTENSIONS

More terms from Alois P. Heinz, Jun 09 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 10 03:38 EDT 2022. Contains 356029 sequences. (Running on oeis4.)