login
A307575
Number of Motzkin meanders of length n with an even number of peaks.
1
1, 2, 4, 9, 22, 56, 148, 402, 1112, 3118, 8832, 25205, 72342, 208560, 603404, 1750785, 5092046, 14839710, 43321976, 126661355, 370813762, 1086877792, 3189091724, 9366371000, 27533212140, 81001276874, 238478223648, 702592110803, 2071257446234, 6109731270056
OFFSET
0,2
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 peak is an occurrence of the pattern UD.
FORMULA
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).
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
a(n) + A307577(n) = A005773(n+1). - R. J. Mathar, Jan 25 2023
EXAMPLE
For n = 3 the a(3) = 9 paths are UUU, UUH, UHU, UHH, UHD, HUU, HUH, HHU, HHH.
MAPLE
b:= proc(x, y, t, c) option remember; `if`(y<0, 0, `if`(x=0, 1-c,
b(x-1, y-1, 0, irem(c+t, 2))+b(x-1, y, 0, c)+b(x-1, y+1, 1, c)))
end:
a:= n-> b(n, 0$3):
seq(a(n), n=0..35); # Alois P. Heinz, Apr 16 2019
MATHEMATICA
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]]];
a[n_] := b[n, 0, 0, 0];
a /@ Range[0, 35] (* Jean-François Alcover, May 12 2020, after Maple *)
CROSSREFS
Cf. A001006.
Sequence in context: A037245 A244886 A143017 * A301362 A130018 A352176
KEYWORD
nonn
AUTHOR
Andrei Asinowski, Apr 15 2019
STATUS
approved