A190525 Number of n-step one-sided prudent walks, avoiding exactly two consecutive west steps (can have three or more west steps).

1, 3, 6, 15, 34, 80, 185, 431, 1001, 2328, 5411, 12580, 29244, 67985, 158045, 367411, 854126, 1985603, 4615966, 10730820, 24946129, 57992715, 134816705, 313410816, 728591751, 1693770328, 3937538296, 9153665985, 21279691689, 49469281395

Offset: 0

Author

Shanzhen Gao, May 11 2011

Keywords

• nonn
• walk
• easy

Comments

The Ze2 sums, see A180662 for the definition of these sums, of the 'Races with Ties' triangle A035317 leads to this sequence with a(-1) = 1; the recurrence relation confirms this value. - Johannes W. Meijer, Jul 20 2011

Number of tilings of a 5 X 3n rectangle with 5 X 1 pentominoes. - M. Poyraz Torcuk, Dec 25 2021

Examples

			a(2) = 6 since there are 6 such walks: NN, NW, WN, EE, EN, NE.
		

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• S. Gao and H. Niederhausen, Sequences Arising From Prudent Self-Avoiding Walks, 2010.
• Index entries for linear recurrences with constant coefficients, signature (2,1,-1,1).

Programs

Magma

I:=[1,3,6,15]; [n le 4 select I[n] else 2*Self(n-1) +Self(n-2) -Self(n-3) +Self(n-4): n in [1..40]]; // G. C. Greubel, Apr 17 2021

Maple

A190525 := proc(n) option remember: if n=0 then 1 elif n=1 then 3 elif n=2 then 6 elif n=3 then 15 else 2*procname(n-1) + procname(n-2) - procname(n-3) + procname(n-4) fi: end: seq(A190525(n), n=0..29); # Johannes W. Meijer, Jul 20 2011

Mathematica

LinearRecurrence[{2,1,-1,1}, {1,3,6,15}, 40] (* G. C. Greubel, Apr 17 2021 *)

Sage

def A190525_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( (1+x-x^2+x^3)/(1-2*x-x^2+x^3-x^4) ).list()
A190525_list(40) # G. C. Greubel, Apr 17 2021

Formula

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

From Johannes W. Meijer, Jul 20 2011: (Start)

a(n) = 2*a(n-1) + a(n-2) - a(n-3) + a(n-4) with a(0) = 1, a(1) = 3, a(2) = 6 and a(3) = 15.

a(n) = (9*A095263(n+1) - 8*A095263(n) + 5*A095263(n-1) - 2*(-1)^n)/7. (End)