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

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

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

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)

Example

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

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 *)

Prog

(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
(Sage)
def A190525_list(prec):
    P.<x> = 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

Crossrefs

Sequence in context: A063832 A006647 A032126 * A032176 A173992 A027600

Adjacent sequences: A190522 A190523 A190524 * A190526 A190527 A190528

Keyword

nonn,walk,easy

Author

Shanzhen Gao, May 11 2011

Status

approved