A190360 Number of one-sided n-step prudent walks, avoiding 4 or more consecutive east steps.

1, 3, 7, 17, 40, 96, 229, 547, 1306, 3119, 7448, 17786, 42473, 101426, 242206, 578390, 1381200, 3298317, 7876408, 18808927, 44915872, 107259471, 256136497, 611656057, 1460639684, 3488019553, 8329419319, 19890721694, 47499206650

Offset

0,2

Comments

a(n,k) is the number of one-sided n-step prudent walks, avoiding k or more consecutive east steps; k=4 in this sequence.

Links

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

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

S. Gao and H. Niederhausen, Sequences Arising From Prudent Self-Avoiding Walks, 2010.

Index entries for linear recurrences with constant coefficients, signature (2, 1, 0, 0, -1).

Formula

G.f.: (1+t-t^k)/(1-2*t-t^2+t^(k+1)), (k=4 in this sequence).

Maple

b:= proc(n, i) option remember; `if`(n<0, 0,
      `if`(n=0, 1, b(n-1, 0) +`if`(i<=0, b(n-1, -1), 0)+
      `if`(i>=0 and i<3, b(n-1, i+1), 0)))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..30);  # Alois P. Heinz, Jun 04 2011

Mathematica

(1+t-t^k)/(1-2*t-t^2+t^(k+1)) /. k -> 4 + O[t]^25 // CoefficientList[#, t]& (* Jean-François Alcover, Oct 24 2016 *)

Crossrefs

Cf. A006356 = a(n,2), A033303 = a(n,3).

Sequence in context: A036885 A247300 A137682 * A167213 A249753 A000600

Adjacent sequences: A190357 A190358 A190359 * A190361 A190362 A190363

Keyword

nonn,walk

Author

Shanzhen Gao, May 09 2011

Status

approved