A329688 Number of excursions of length n with Motzkin-steps avoiding the consecutive steps UU, HH, HD and DU.

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

Offset

0,4

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

Formula

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

D-finite with recurrence: -(n+4)*(5*n^2-11*n-6)*a(n) +36*(-n+1)*a(n-1) +36*(n-2)*a(n-2) +2*(2*n-5)*(5*n^2-n-12)*a(n-3)=0. - R. J. Mathar, Jan 09 2020

a(n) ~ (sqrt(3)*(4 + 2^(1/3) + 2^(5/3)) - sqrt(3)*(-8 + 2^(1/3) + 2^(5/3)) * cos(2*Pi*n/3) + 3*(2^(1/3) - 2^(5/3)) * sin(2*Pi*n/3)) * 2^(2*n/3 - 1) / (sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Nov 19 2021

Example

a(5)=2 since we have 2 such excursions of length 5, namely UHUDD and UDHUD.

Crossrefs

Cf. A000108.

Sequence in context: A060547 A079878 A324469 * A217920 A137406 A181293

Adjacent sequences: A329685 A329686 A329687 * A329689 A329690 A329691

Keyword

nonn,walk

Author

Valerie Roitner, Nov 29 2019

Status

approved