%I #22 Jun 28 2021 09:25:06
%S 1,3,7,16,39,92,219,521,1238,2944,6999,16640,39562,94058,223623,
%T 531663,1264027,3005221,7144904,16986989,40386518,96018831,228284497,
%U 542745740,1290376448,3067866323,7293843428,17341091936,41228396592,98020395245
%N Number of n-step one-sided prudent walks avoiding exactly three consecutive West steps.
%H Vincenzo Librandi, <a href="/A190528/b190528.txt">Table of n, a(n) for n = 0..100</a>
%H S. Gao and H. Niederhausen, <a href="http://math.fau.edu/Niederhausen/HTML/Papers/Sequences%20Arising%20From%20Prudent%20Self-Avoiding%20Walks-February%2001-2010.pdf">Sequences Arising From Prudent Self-Avoiding Walks</a>, 2010.
%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (2,1,0,-1,1).
%F G.f.: x*(1+x-x^3+x^4)/(1-2*x-x^2+x^4-x^5).
%F 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]
%e 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.
%t 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 *)
%o (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
%K nonn,walk
%O 0,2
%A _Shanzhen Gao_, May 11 2011
|