

A190528


Number of nstep onesided prudent walks avoiding exactly three consecutive West steps.


1



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


REFERENCES

S. Gao, H. Niederhausen, Sequences Arising From Prudent SelfAvoiding Walks (submitted to INTEGERS: The Electronic Journal of Combinatorial Number Theory).


LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..100
Index entries for linear recurrences with constant coefficients, signature (2, 1, 0, 1, 1).


FORMULA

G.f.: x*(1+xx^3+x^4)/(12*xx^2+x^4x^5).
a(0)=1, a(1)=3, a(2)=7, a(3)=16, a(4)=39, a(n)=2*a(n1)+a(n2) a(n4)+ a(n5) [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+xx^3+x^4)/(12xx^2+x^4x^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+xx^3+x^4)/(12*xx^2+x^4x^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



