A190512 Number of one-sided n-step prudent walks, avoiding single west step only, i.e., two or more consecutive west steps are permitted.

1, 2, 5, 11, 24, 53, 117, 258, 569, 1255, 2768, 6105, 13465, 29698, 65501, 144467, 318632, 702765, 1549997, 3418626, 7540017, 16630031, 36678688, 80897393, 178424817, 393528322, 867954037, 1914332891, 4222194104, 9312342245, 20539017381, 45300228866

Offset

0,2

Links

Table of n, a(n) for n=0..31.

S. Gao and H. Niederhausen, Sequences Arising From Prudent Self-Avoiding Walks, 2010.

Index entries for linear recurrences with constant coefficients, signature (2,0,1).

Formula

a(n) = A052980(n+1). - R. J. Mathar, May 16 2011

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

Example

a(2)=5 since there are 5 such walks: WW, NN, EN, NE, EE.

Prog

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

Crossrefs

Cf. A110513 (essentially a signed version).

Cf. A052980 (essentially the same sequence).

Sequence in context: A111297 A077864 A052980 * A110513 A018115 A242551

Adjacent sequences: A190509 A190510 A190511 * A190513 A190514 A190515

Keyword

nonn,walk

Author

Shanzhen Gao, May 11 2011

Status

approved