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

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.

Links

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

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

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

Example

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

Crossrefs

Cf. A307555.

Sequence in context: A138164 A130802 A022543 * A036618 A349014 A003018

Adjacent sequences: A307554 A307555 A307556 * A307558 A307559 A307560

Keyword

nonn

Author

Andrei Asinowski, Apr 14 2019

Status

approved