A307555 - OEIS

%I #22 Jan 25 2023 12:22:59

%S 1,2,4,8,17,40,106,307,927,2818,8480,25142,73555,213204,615074,

%T 1773036,5121195,14843518,43190084,126112096,369264395,1083378784,

%U 3182684838,9357797643,27529874201,81028448678,238599098824,702932296258,2072003987285,6111009331876

%N Number of Motzkin meanders of length n with an even 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 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((-t^2+1)/(3*t^2-4*t+1))+sqrt((t^2+1)/(5*t^2-4*t+1))-2)/(4*t).

%F 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_, Jan 25 2023

%e For n = 3, the a(3) = 8 paths are HHH, HHU, HUH, HUU, UHH, UHU, UUU.

%e For n=5, there are a(5) = 40 paths: 32 paths with no humps, {H, U}^5; and 8 paths with two humps, HUDUD, UDHUD, UDUDH, UDUDU, UDUHD, UDUUD, UHDUD, UUDUD.

%p a:=gfun[rectoproc]({(15*n^2+45*n+30)*u(n)+(-92*n^2-532*n-696)*u(n+1)+(62*n^2+426*n+672)*u(n+2)+(-32*n^2-264*n-524)*u(n+3)+(-20*n^2-192*n-428)*u(n+4)+(84*n^2+988*n+2848)*u(n+5)+(-70*n^2-906*n-2864)*u(n+6)+(24*n^2+336*n+1140)*u(n+7)+(-3*n^2-45*n-162)*u(n+8), u(0) = 1, u(1) = 2, u(2) = 4, u(3) = 8, u(4) = 17, u(5) = 40, u(6) = 106, u(7) = 307},u(n),remember):

%p seq(a(n), n=0..30);

%Y Cf. A307557.

%K nonn

%O 0,2

%A _Cyril Banderier_, Apr 14 2019