%I #27 Mar 08 2023 05:40:19
%S 0,0,1,5,18,56,161,443,1196,3228,8823,24579,69810,201380,586843,
%T 1719081,5044584,14800352,43384747,127076015,372100654,1089864344,
%U 3194496987,9372984609,27532712140,80966582548,238342592353,702222958797,2070454005078,6108341367004
%N Number of Motzkin meanders of length n with an odd number of humps.
%C 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.
%C A hump is an occurrence of the pattern UHH...HD (the number of Hs in the pattern is not fixed, and can be 0).
%H Alois P. Heinz, <a href="/A307572/b307572.txt">Table of n, a(n) for n = 0..1000</a>
%H Andrei Asinowski, Axel Bacher, Cyril Banderier, Bernhard Gittenberger, <a href="https://lipn.univ-paris13.fr/~banderier/Papers/patterns2019.pdf">Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata</a>, Algorithmica (2019).
%F G.f.: (sqrt((1-t^2)/(1-4*t+3*t^2)) - sqrt((1+t^2)/(1-4*t+5*t^2))) / (4*t).
%F 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
%F a(n) ~ 3^(n + 1/2) / (2*sqrt(Pi*n)). - _Vaclav Kotesovec_, Mar 08 2023
%e For n = 3 the a(3) = 5 paths are UDH, HUD, UHD, UUD, UDU.
%p b:= proc(x, y, t, c) option remember; `if`(y<0, 0, `if`(x=0, c,
%p b(x-1, y-1, 0, irem(c+t, 2))+b(x-1, y, t, c)+b(x-1, y+1, 1, c)))
%p end:
%p a:= n-> b(n, 0$3):
%p seq(a(n), n=0..35); # _Alois P. Heinz_, Apr 16 2019
%t 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]]];
%t a[n_] := b[n, 0, 0, 0];
%t Table[a[n], {n, 0, 35}] (* _Jean-François Alcover_, Apr 29 2019, after _Alois P. Heinz_ *)
%Y Cf. A001006.
%K nonn
%O 0,4
%A _Andrei Asinowski_, Apr 15 2019