A329686 Number of excursions of length n with Motzkin-steps forbidding all consecutive steps of length 2 except UH, HU, HD and DH.

1, 1, 0, 1, 2, 1, 0, 2, 4, 2, 0, 5, 10, 5, 0, 14, 28, 14, 0, 42, 84, 42, 0, 132, 264, 132, 0, 429, 858, 429, 0, 1430, 2860, 1430, 0, 4862, 9724, 4862, 0, 16796, 33592, 16796, 0, 58786, 117572, 58786, 0, 208012, 416024, 208012, 0, 742900, 1485800, 742900, 0, 2674440, 5348880, 2674440, 0

Offset

0,5

Comments

The Motzkin step set is U=(1,1), H=(1,0) and D=(1,-1). An excursion is a path starting at (0,0), ending on the x-axis and never crossing the x-axis, i.e., staying at nonnegative altitude.

Links

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

Formula

G.f.: ((1+t)(1+t-2t^4-(1+t)*sqrt(1-4t^4)))/(2t^5).

a(4n)=2*C(n), a(4n-1)=C(n), a(4n+1)=C(n) and a(4n+2)=0, where C(n) are the Catalan numbers A000108.

D-finite with recurrence: (n+5)*(3*n^2-27*n+92)*a(n) +16*(3*n-19)*a(n-1) +16*(-3*n+22)*a(n-2) +16*(3*n-25)*a(n-3) -4*(n-3)*(3*n^2-21*n+68)*a(n-4)=0. - R. J. Mathar, Jan 09 2020

Example

a(8)=4 since we have the following four excursions of length 8: UHDHUHDH, HUHDHUHD, UHUHDHDH and HUHUHDHD.

Crossrefs

Cf. A000108.

Sequence in context: A279226 A108354 A329099 * A261615 A146162 A147702

Adjacent sequences: A329683 A329684 A329685 * A329687 A329688 A329689

Keyword

nonn,walk

Author

Valerie Roitner, Nov 29 2019

Status

approved