login
Number of Motzkin meanders of length n with an even number of humps and an even number of peaks.
7

%I #24 Jan 25 2023 12:20:14

%S 1,2,4,8,17,38,92,239,653,1832,5192,14726,41683,117822,333312,945952,

%T 2698117,7740920,22337788,64788768,188683267,551179370,1613612996,

%U 4731245903,13888157307,40804653640,119984904744,353085202434,1039830559085,3064566227434

%N Number of Motzkin meanders of length n with an even number of humps and an even number of peaks.

%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 peak is an occurrence of the pattern UD.

%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="/A325921/b325921.txt">Table of n, a(n) for n = 0..2100</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.: ( (-1+4*t-3*t^2+sqrt(-3*t^4+4*t^3+2*t^2-4*t+1))/(3*t^2-4*t+1) + (-1+4*t-5*t^2+2*t^3+sqrt(4*t^6-12*t^5+13*t^4-8*t^3+6*t^2-4*t+1))/(-2*t^3+5*t^2-4*t+1) + (-1+4*t-5*t^2+sqrt(5*t^4-4*t^3+6*t^2-4*t+1))/(5*t^2-4*t+1) + (-1+4*t-3*t^2-2*t^3+sqrt(4*t^6+4*t^5-11*t^4+8*t^3+2*t^2-4*t+1))/(2*t^3+3*t^2-4*t+1) ) / (8*t).

%F a(n) ~ 3^(n + 1/2) / (4*sqrt(Pi*n)). - _Vaclav Kotesovec_, Jul 03 2019

%F a(n) + A325923(n) = A307575(n). - _R. J. Mathar_, Jan 25 2023

%F a(n) + A325925(n) = A307555(n). - _R. J. Mathar_, Jan 25 2023

%e For n=0, 1, 2, 3 there are 2^n paths: all the paths without D (0 humps, 0 peaks).

%e For example, for n=3: UUU, UUH, UHU, UHH, HUU, HUH, HHU, HHH.

%e For n=4, the "extra" path is UDUD (2 humps, 2 peaks).

%e The smallest example with #(humps) <> #(peaks) is UHDUHD (2 humps, 0 peaks).

%p b:= proc(x, y, t, p, h) option remember; `if`(x=0, `if`(p+h=0, 1, 0),

%p `if`(y>0, b(x-1, y-1, 0, irem(p+`if`(t=1, 1, 0), 2), irem(h+

%p `if`(t=2, 1, 0), 2)), 0)+b(x-1, y, `if`(t>0, 2, 0), p, h)+

%p b(x-1, y+1, 1, p, h))

%p end:

%p a:= n-> b(n, 0$4):

%p seq(a(n), n=0..35); # _Alois P. Heinz_, Jul 03 2019

%t CoefficientList[Series[(1/(8*x))*((-1 + 4*x - 3*x^2 + Sqrt[(-(-1 + x)^2)* (-1 + 2*x + 3*x^2)])/ (1 - 4*x + 3*x^2) - (-1 + 4*x - 5*x^2 + 2*x^3 + Sqrt[(-1 + x)^3*(-1 + x + 4*x^3)])/((-1 + x)^2* (-1 + 2*x)) + (-1 + 4*x - 5*x^2 + Sqrt[1 - 4*x + 6*x^2 - 4*x^3 + 5*x^4])/ (1 - 4*x + 5*x^2) + (-1 + 4*x - 3*x^2 - 2*x^3 + Sqrt[1 - 4*x + 2*x^2 + 8*x^3 - 11*x^4 + 4*x^5 + 4*x^6])/(1 - 4*x + 3*x^2 + 2*x^3)), {x, 0, 30}], x] (* _Vaclav Kotesovec_, Jul 03 2019 *)

%Y Cf. A307572, A325922.

%K nonn

%O 0,2

%A _Andrei Asinowski_, Jun 27 2019