A325917 Number of Motzkin meanders of length n with an even number of humps and without peaks.

1, 2, 4, 8, 16, 32, 65, 136, 298, 691, 1694, 4340, 11433, 30510, 81592, 217238, 573970, 1503296, 3904181, 10065079, 25796324, 65837541, 167602092, 426213784, 1084095329, 2760717190, 7043305930, 18008810836, 46151503544, 118529776510, 304998080821

Offset: 0

Author

Andrei Asinowski, May 28 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.

A peak is an occurrence of the pattern UD.

A hump is an occurrence of the pattern UHH...HD (the number of Hs in the pattern is not fixed, and can be 0).

Examples

			For n=0..5 we have a(n)=2^n because for these values we have only the humpless paths {U, H}^n. For n=6, the only "extra" path is UHDUHD. For n=7, the eight "extra" paths are UHDUHHD, UHHDUHD, UHDUHDH, UHDUHDU, UHDHUHD, UHDUUHD, HUHDUHD, UUHDUHD.
		

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).
• Andrei Asinowski, Axel Bacher, Cyril Banderier, Bernhard Gittenberger, Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Asymptotic Aspects and Borges's Theorem, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018).

Programs

Mathematica

CoefficientList[Series[(1/4)*(x^3 - 4*x^2 + 4*x - 1 + Sqrt[x^6 - 4*x^5 + 4*x^4 - 2*x^3 + 4*x^2 - 4*x + 1])/((-x^3 + 4*x^2 - 4*x + 1)*x) + (1/4)*(-x^3 - 4*x^2 + 4*x - 1 + Sqrt[x^6 + 4*x^5 - 4*x^4 + 2*x^3 + 4*x^2 - 4*x + 1])/((x^3 + 4*x^2 - 4*x + 1)*x), {x, 0, 40}], x] (* Vaclav Kotesovec, Jun 05 2019 *)

Formula

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

a(n) + A325919(n) = A091964(n). - R. J. Mathar, Jan 25 2023