A307555 Number of Motzkin meanders of length n with an even number of humps.

1, 2, 4, 8, 17, 40, 106, 307, 927, 2818, 8480, 25142, 73555, 213204, 615074, 1773036, 5121195, 14843518, 43190084, 126112096, 369264395, 1083378784, 3182684838, 9357797643, 27529874201, 81028448678, 238599098824, 702932296258, 2072003987285, 6111009331876

Offset: 0

Author

Cyril Banderier, Apr 14 2019

Keywords

• nonn

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).

Examples

			For n = 3, the a(3) = 8 paths are HHH, HHU, HUH, HUU, UHH, UHU, UUU.
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.
		

Links

• 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).

Crossrefs

Cf. A307557.

Programs

Maple

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):
seq(a(n), n=0..30);

Formula

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).

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