login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Number of Motzkin excursions of length n with an even number of peaks.
0

%I #17 Jan 25 2023 11:46:25

%S 1,1,1,2,5,11,26,65,164,421,1101,2912,7777,20957,56891,155418,426975,

%T 1178841,3269023,9101182,25428895,71279177,200391716,564899237,

%U 1596399798,4521769035,12835037619,36504130056,104012102095,296872273835,848694416554,2429884047993

%N Number of Motzkin excursions of length n with an even number of peaks.

%C A Motzkin excursion is a lattice path with steps from the set {D=-1, H=0, U=1} that starts at (0,0), never goes below the x-axis, and terminates at the altitude 0.

%C A peak is an occurrence of the pattern UD.

%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.: (2*(1-t+t^2) - sqrt((1+t)*(1-3*t)) - sqrt((1-t)*(1-2*t)*(1+t+2*t^2))) / (4*t^2).

%F D-finite with recurrence 2*n*(n+2)*(6213*n-138098)*a(n) +(n-1)*(12426*n^2+978417*n+821680)*a(n-1) +2*(-23065*n^3-728759*n^2+2760574*n-410840)*a(n-2) +2*(-292946*n^3 +3649919*n^2 -11479673*n +8929300)*a(n-3) +2*(233455*n^3 -3707982*n^2 +13757984*n -13497400)*a(n-4) +(608874*n^3 -5758645*n^2 +11199163*n +5963900)*a(n-5) +2*(848625*n^3 -11463971*n^2 +51225442*n -77109420)*a(n-6) -16*(n-7)*(2213*n^2 +270746*n -1493325)*a(n-7) -24*(88769*n -321795)*(n-7)*(n-8)*a(n-8)=0. - _R. J. Mathar_, Jan 25 2023

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

%e For n = 4 the a(4) = 5 paths are HHHH, HUHD, UHDH, UHHD, UDUD.

%p b:= proc(x, y, t, c) option remember; `if`(y>x or y<0, 0, `if`(x=0, 1-c,

%p b(x-1, y-1, 0, irem(c+t, 2))+b(x-1, y, 0, 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 15 2019

%t b[x_, y_, t_, c_] := b[x, y, t, c] = If[y > x || y < 0, 0, If[x == 0, 1-c, b[x-1, y-1, 0, Mod[c+t, 2]] + b[x-1, y, 0, c] + b[x-1, y+1, 1, c]]];

%t a[n_] := b[n, 0, 0, 0];

%t a /@ Range[0, 35] (* _Jean-François Alcover_, May 12 2020, after Maple *)

%Y Cf. A001006.

%K nonn

%O 0,4

%A _Andrei Asinowski_, Apr 15 2019