OFFSET
0,4
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 hump is an occurrence of the pattern UHH...HD (the number of Hs in the pattern is not fixed, and can be 0).
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1000
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).
Tamás Szakács, Linear recursive sequences and factorials, Ph. D. Thesis, Univ. Debrecen (Hungary, 2024). See pp. 51, 58.
FORMULA
G.f.: (sqrt((1-t^2)/(1-4*t+3*t^2)) - sqrt((1+t^2)/(1-4*t+5*t^2))) / (4*t).
Conjecture: D-finite with recurrence -3*(n+1)*(n-2)*a(n) +12*(2*n^2-4*n-1)*a(n-1) +2*(-35*n^2+107*n-48)*a(n-2) +4*(21*n^2-89*n+80)*a(n-3) +4*(-5*n^2+32*n-43)*a(n-4) +4*(-8*n^2+62*n-115)*a(n-5) +2*(31*n^2-283*n+616)*a(n-6) -4*(23*n-97)*(n-6)*a(n-7) +15*(n-6)*(n-7)*a(n-8)=0. - R. J. Mathar, May 06 2020
a(n) ~ 3^(n + 1/2) / (2*sqrt(Pi*n)). - Vaclav Kotesovec, Mar 08 2023
EXAMPLE
For n = 3 the a(3) = 5 paths are UDH, HUD, UHD, UUD, UDU.
MAPLE
b:= proc(x, y, t, c) option remember; `if`(y<0, 0, `if`(x=0, c,
b(x-1, y-1, 0, irem(c+t, 2))+b(x-1, y, t, c)+b(x-1, y+1, 1, c)))
end:
a:= n-> b(n, 0$3):
seq(a(n), n=0..35); # Alois P. Heinz, Apr 16 2019
MATHEMATICA
b[x_, y_, t_, c_] := b[x, y, t, c] = If[y<0, 0, If[x==0, c, b[x-1, y-1, 0, Mod[c+t, 2]] + b[x-1, y, t, c] + b[x-1, y+1, 1, c]]];
a[n_] := b[n, 0, 0, 0];
Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Apr 29 2019, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Andrei Asinowski, Apr 15 2019
STATUS
approved