A325922 Number of Motzkin excursions of length n with an even number of humps and an even number of peaks.

1, 1, 1, 1, 2, 4, 11, 31, 86, 230, 608, 1588, 4151, 10925, 29083, 78373, 213702, 588366, 1631906, 4550346, 12736029, 35746763, 100561622, 283486702, 800798659, 2266802139, 6429960961, 18276530005, 52051825058, 148520257620, 424507695627

Offset

0,5

Comments

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

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

Formula

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

a(n) ~ 3^(n + 3/2) / (8*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Jul 03 2019

conjecture: a(n)+A325924(n) = A307557(n). - R. J. Mathar, Jan 25 2023

Example

For n=3 the a(5)=4 paths are HHHHH, UDUDH, UDHUD, HUDUD.

Mathematica

CoefficientList[Series[(4 (1 - 2 x + 2 x^2) - Sqrt[(1 - 2 x - 3 x^2) (1 - x)^2] - Sqrt[(1 - x - 4 x^3) (1 - x)^3] - Sqrt[(1 + x^2) (1 - 4 x + 5  x^2)] - Sqrt[(1 - 2 x) (1 - 2 x - x^2) (1 - x^2 + 2 x^3)]) / (8  x^2 (1 - x)), {x, 0, 30}], x] (* Vincenzo Librandi, Jun 30 2019 *)

Crossrefs

Cf. A325921.

Sequence in context: A276687 A298891 A002387 * A148160 A148161 A263375

Adjacent sequences: A325919 A325920 A325921 * A325923 A325924 A325925

Keyword

nonn

Author

Andrei Asinowski, Jun 27 2019

Status

approved