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

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

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

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

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

Example

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.

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

Crossrefs

Sequence in context: A329053 A084637 A100137 * A210542 A141366 A049142

Adjacent sequences: A325914 A325915 A325916 * A325918 A325919 A325920

Keyword

nonn

Author

Andrei Asinowski, May 28 2019

Status

approved