A325923 Number of Motzkin meanders of length n with an odd number of humps and an even number of peaks.

0, 0, 0, 1, 5, 18, 56, 163, 459, 1286, 3640, 10479, 30659, 90738, 270092, 804833, 2393929, 7098790, 20984188, 61872587, 182130495, 535698422, 1575478728, 4635125097, 13645054833, 40196623234, 118493318904, 349506908369, 1031426887149

Offset

0,5

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

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.: ( (-3*t^2+4*t+sqrt(-3*t^4+4*t^3+2*t^2-4*t+1)-1)/(3*t^2-4*t+1) + (2*t^3-5*t^2+4*t+sqrt(4*t^6-12*t^5+13*t^4-8*t^3+6*t^2-4*t+1)-1)/(-2*t^3+5*t^2-4*t+1) - (-5*t^2+4*t+sqrt(5*t^4-4*t^3+6*t^2-4*t+1)-1)/(5*t^2-4*t+1) - (-2*t^3-3*t^2+4*t+sqrt(4*t^6+4*t^5-11*t^4+8*t^3+2*t^2-4*t+1)-1)/(2*t^3+3*t^2-4*t+1) ) / (8*t).

a(n) ~ 3^(n + 1/2) / (4*sqrt(Pi*n)). - Vaclav Kotesovec, Aug 09 2019

Example

For n = 4 the a(4) = 5 paths are UHDU, UHDH, UUHD, HUHD, UHHD: in all these paths, 0 peaks, 1 hump.
For n=0..6 we have only paths with 0 peaks and 1 hump.
For n=7, we have a(7)=163. Among them, 160 paths with 0 peaks and 1 hump, and 3 walks with 2 peaks and 3 humps: UDUDUHD, UDUHDUD, UHDUDUD.

Maple

b:= proc(x, y, t, p, h) option remember; `if`(x=0, `if`(p+1=h, 1, 0),
      `if`(y>0, b(x-1, y-1, 0, irem(p+`if`(t=1, 1, 0), 2), irem(h+
      `if`(t=2, 1, 0), 2)), 0)+b(x-1, y, `if`(t>0, 2, 0), p, h)+
         b(x-1, y+1, 1, p, h))
    end:
a:= n-> b(n, 0$4):
seq(a(n), n=0..35);  # Alois P. Heinz, Jul 04 2019

Mathematica

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

Crossrefs

Cf. A325921.

Sequence in context: A325919 A317849 A307572 * A335720 A093374 A258109

Adjacent sequences: A325920 A325921 A325922 * A325924 A325925 A325926

Keyword

nonn

Author

Andrei Asinowski, Jul 04 2019

Status

approved