A307575 - OEIS

%I #20 Jan 25 2023 12:00:59

%S 1,2,4,9,22,56,148,402,1112,3118,8832,25205,72342,208560,603404,

%T 1750785,5092046,14839710,43321976,126661355,370813762,1086877792,

%U 3189091724,9366371000,27533212140,81001276874,238478223648,702592110803,2071257446234,6109731270056

%N Number of Motzkin meanders of length n with 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.

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

%F D-finite with recurrence -3*(n+1)*(n-2)*a(n) +4*(4*n^2-7*n-3)*a(n-1) +3*(-7*n^2+17*n-2)*a(n-2) +4*n*(n-3)*a(n-3) -(n-3)*(25*n-82)*a(n-4) +4*(n-3)*(6*n-19)*a(n-5) +(61*n^2-575*n+1302)*a(n-6) -4*(11*n-37)*(n-6)*a(n-7) -12*(n-6)*(n-7)*a(n-8)=0. - _R. J. Mathar_, Mar 06 2022

%F a(n) + A307577(n) = A005773(n+1). - _R. J. Mathar_, Jan 25 2023

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

%p b:= proc(x, y, t, c) option remember; `if`(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 16 2019

%t b[x_, y_, t_, c_] := b[x, y, t, c] = If[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,2

%A _Andrei Asinowski_, Apr 15 2019