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

Author

Shanzhen Gao, May 09 2011

Keywords

• nonn
• walk

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).

Crossrefs

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

Programs

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 *)

Formula

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