A325920 Number of Motzkin excursions of length n with an odd number of humps and without peaks.

0, 0, 0, 1, 3, 7, 15, 31, 63, 128, 262, 545, 1161, 2547, 5767, 13456, 32202, 78544, 194016, 482726, 1204874, 3008782, 7505420, 18689551, 46454971, 115296751, 285886839, 708673484, 1757339598, 4361894604, 10841959912

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

Example

For n = 5 the a(5) = 7 paths are UHHHD, UHHDH, HUHHD, HHUHD, HUHDH, UHDHH, UUHDD.

Crossrefs

Sequence in context: A178460 A351755 A057613 * A351754 A174743 A146686

Adjacent sequences: A325917 A325918 A325919 * A325921 A325922 A325923

Keyword

nonn

Author

Andrei Asinowski, Jun 25 2019

Status

approved