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

Author

Shanzhen Gao, May 11 2011

Keywords

• nonn
• walk

Examples

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

Links

• 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).

Crossrefs

Cf. A110513 (essentially a signed version).

Cf. A052980 (essentially the same sequence).

Programs

PARI

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

Formula

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

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