login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A325924 Number of Motzkin excursions of length n with an odd number of humps and an even number of peaks. 4
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 01:25 EDT 2020. Contains 333104 sequences. (Running on oeis4.)