A307557 Number of Motzkin meanders of length n with no level steps at odd level.

1, 2, 4, 9, 20, 47, 110, 264, 634, 1541, 3754, 9204, 22622, 55817, 138026, 342203, 849984, 2115245, 5271970, 13158944, 32886338, 82285031, 206101422, 516728937, 1296664512, 3256472235, 8184526438, 20584627358, 51805243138, 130456806425, 328703655114

Offset: 0

Author

Andrei Asinowski, Apr 14 2019

Keywords

• nonn

Comments

A Motzkin meander is a lattice path with steps from the set {D=-1, H=0, U=1} that starts at (0,0), and never goes below the x-axis.

Examples

			For n = 3 the a(3) = 9 paths are UUU, UUH, UUD, UDU, UDH, HUU, HUD, HHU, HHH.
		

Links

• Andrei Asinowski, Axel Bacher, Cyril Banderier, Bernhard Gittenberger, Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata, Algorithmica (2019).

Crossrefs

Cf. A307555.

Formula

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

D-finite with recurrence (n+1)*a(n) +(-n-2)*a(n-1) +(-5*n+3)*a(n-2) +(n+4)*a(n-3) +2*(2*n-5)*a(n-4)=0. - R. J. Mathar, Jan 25 2023

a(n) ~ sqrt(13 + 53/sqrt(17)) * (1 + sqrt(17))^n / (sqrt(Pi*n) * 2^(n + 3/2)). - Vaclav Kotesovec, Jun 24 2023

a(n) = (A026569(n) + A026569(n+1))/2. - Mark van Hoeij, Nov 29 2024