login
A307564
Number of Motzkin excursions of length n with an even number of humps.
0
1, 1, 1, 1, 2, 6, 19, 57, 162, 442, 1176, 3092, 8119, 21451, 57275, 154771, 422970, 1166762, 3241282, 9049682, 25356109, 71229481, 200520398, 565594404, 1598436567, 4526347791, 12843234665, 36514629469, 104015020498, 296835850798, 848542194283, 2429468192825
OFFSET
0,5
COMMENTS
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 ends at the altitude 0.
A hump is an occurrence of the pattern UHH...HD (the number of Hs in the pattern is not fixed, and can be 0).
FORMULA
G.f.: (2-4*t+4*t^2 - sqrt((1-t^2)*(1-4*t+3*t^2)) - sqrt((1+t^2)*(1-4*t+5*t^2)))/(4*t^2*(1-t)).
D-finite with recurrence: n*(n+2)*(n-17)*a(n) +(n^3+93*n^2+14*n-60)*a(n-1) +(-37*n^3-96*n^2+376*n-60)*a(n-2) +(107*n^3-273*n^2-527*n+876)*a(n-3) +3*(-29*n^3+120*n^2+117*n-540)*a(n-4) +(-31*n^3+339*n^2-1178*n+1212)*a(n-5) +(37*n^3-60*n^2-1234*n+2844)*a(n-6) +(-107*n^3+981*n^2-1039*n-5628)*a(n-7) +(n-7)*(86*n^2-187*n-1068)*a(n-8) +30*(n-3)*(n-7)*(n-8)*a(n-9)=0. - R. J. Mathar, Jan 27 2020
a(n)+A307573(n) = A001006(n). - R. J. Mathar, Jan 25 2023
EXAMPLE
For n = 5 the a(5) = 6 paths are HHHHH, UDUHD, UHDUD, UDUDH, UDHUD, HUDUD.
MAPLE
b:= proc(x, y, t, c) option remember; `if`(y>x or y<0, 0, `if`(x=0, 1-c,
b(x-1, y-1, 0, irem(c+t, 2))+b(x-1, y, t, 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 15 2019
MATHEMATICA
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, t, c] + b[x-1, y+1, 1, c]]];
a[n_] := b[n, 0, 0, 0];
a /@ Range[0, 35] (* Jean-François Alcover, May 11 2020, after Maple *)
CROSSREFS
Cf. A001006.
Sequence in context: A121483 A077834 A325918 * A308240 A328658 A067675
KEYWORD
nonn
AUTHOR
Andrei Asinowski, Apr 15 2019
STATUS
approved