A190571 Number of n-step one-sided prudent walks, avoiding exactly three consecutive west steps and three consecutive east steps.

1, 3, 7, 15, 37, 85, 199, 467, 1089, 2549, 5959, 13931, 32577, 76165, 178087, 416395, 973585, 2276389, 5322519, 12444811, 29097761, 68034725, 159074951, 371940043, 869649137, 2033364389, 4754297463, 11116229131, 25991337537, 60771473701

Offset

1,2

Links

Table of n, a(n) for n=1..30.

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

Formula

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

Mathematica

CoefficientList[Series[x (1+x-2x^3+2x^4)/(1-2x-x^2+2x^4-2x^5), {x, 0, 30}], x] (* or *) LinearRecurrence[{2, 1, 0, -2, 2}, {1, 3, 7, 15, 37}, 30] (* Harvey P. Dale, Oct 20 2024 *)

Prog

(PARI) my(x='x+O('x^35)); Vec(x*(1+x-2*x^3+2*x^4)/(1-2*x-x^2+2*x^4-2*x^5)) \\ Michel Marcus, Jun 28 2021

Crossrefs

Sequence in context: A373767 A183557 A255962 * A317881 A018020 A192472

Adjacent sequences: A190568 A190569 A190570 * A190572 A190573 A190574

Keyword

nonn,walk

Author

Shanzhen Gao, May 12 2011

Status

approved