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

0, 0, 0, 1, 3, 7, 15, 34, 78, 191, 493, 1324, 3626, 10032, 27808, 77045, 213273, 590475, 1637117, 4550836, 12692866, 35532414, 99830094, 281412535, 795601139, 2254966896, 6405076658, 18227600051, 51960277037, 148352016215, 424186720927, 1214602291322

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

Thus every peak is also a hump.

Links

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

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*t^3 + 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, Aug 09 2019

Example

For n = 5 the a(5) = 7 paths are UHHHD, UHHDH, HUHHD, HHUHD, HUHDH, UHDHH, UUHDD. In all these paths, 0 peaks and 1 hump.
For n = 0..6, we have only paths with 0 peaks and 1 hump.
For n=7, we have a(n)=34. Among them, 31 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`(y>x, 0, `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[-(4 x^3 + 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, 33}], x] (* Vincenzo Librandi, Jul 09 2019 *)

Crossrefs

Cf. A325923.

Sequence in context: A147102 A147379 A213722 * A217092 A153588 A221945

Adjacent sequences: A325921 A325922 A325923 * A325925 A325926 A325927

Keyword

nonn

Author

Andrei Asinowski, Jul 04 2019

Status

approved