A190528 Number of n-step one-sided prudent walks avoiding exactly three consecutive West steps.

1, 3, 7, 16, 39, 92, 219, 521, 1238, 2944, 6999, 16640, 39562, 94058, 223623, 531663, 1264027, 3005221, 7144904, 16986989, 40386518, 96018831, 228284497, 542745740, 1290376448, 3067866323, 7293843428, 17341091936, 41228396592, 98020395245

Offset

0,2

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..100

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

Formula

G.f.: x*(1+x-x^3+x^4)/(1-2*x-x^2+x^4-x^5).

a(0)=1, a(1)=3, a(2)=7, a(3)=16, a(4)=39, a(n)=2*a(n-1)+a(n-2)- a(n-4)+ a(n-5) [From Harvey P. Dale, Sep 20 2011]

Example

a(3)=16 since there are 16 such walks: WWN, NWW, WNN, WNW, WNE, NNN, NNW, NNE, NEE, NWN, NEN, EEE, EEN, ENW, ENN, ENE.

Mathematica

Rest[CoefficientList[Series[x (1+x-x^3+x^4)/(1-2x-x^2+x^4-x^5), {x, 0, 40}], x]] (* or *) LinearRecurrence[{2, 1, 0, -1, 1}, {1, 3, 7, 16, 39}, 40] (* Harvey P. Dale, Sep 20 2011 *)

Prog

(PARI) Vec(x*(1+x-x^3+x^4)/(1-2*x-x^2+x^4-x^5)+O(x^66)) \\ Joerg Arndt, May 13 2011

Crossrefs

Sequence in context: A227235 A304937 A152090 * A203611 A176604 A014140

Adjacent sequences: A190525 A190526 A190527 * A190529 A190530 A190531

Keyword

nonn,walk

Author

Shanzhen Gao, May 11 2011

Status

approved