login
A307573
Number of Motzkin excursions of length n with an odd number of humps.
1
0, 0, 1, 3, 7, 15, 32, 70, 161, 393, 1012, 2706, 7392, 20384, 56359, 155801, 430497, 1190017, 3295100, 9149602, 25495910, 71318078, 200242825, 564166011, 1594291230, 4517054710, 12826583811, 36493143333, 104008257711, 296906934031, 848843276928, 2430293483566
OFFSET
0,4
COMMENTS
a(n) is the number of Motzkin excursions with an odd number of humps.
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.
A hump is an occurrence of the pattern UHH...HD (the number of 0's in the pattern is not fixed, and can be 0).
FORMULA
G.f.: (-2*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)*(5*n^2-105*n+454)*a(n) +(5*n^4+365*n^3-2348*n^2-614*n+1530)*a(n-1) +(-195*n^4+950*n^3+2838*n^2-8804*n+1530)*a(n-2) +(605*n^4-5865*n^3+13255*n^2+2724*n-14400)*a(n-3) +(-605*n^4+7370*n^3-27409*n^2+29410*n+4140)*a(n-4) +(-5*n^4-65*n^3+1418*n^2-7270*n+12690)*a(n-5) +(195*n^4-1850*n^3+492*n^2+31376*n-58950)*a(n-6) -5*(n-6)*(121*n^3-1227*n^2+2411*n+3042)*a(n-7) +75*(n-6)*(n-7)*(8*n^2-37*n-12)*a(n-8)=0. - R. J. Mathar, Mar 06 2022
EXAMPLE
For n = 4 the a(4) = 7 paths are UDHH, HUDH, HHUD, UHDH, HUHD, UHHD, UUDD.
MAPLE
b:= proc(x, y, t, c) option remember; `if`(y>x or y<0, 0, `if`(x=0, 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, 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: A132402 A137166 A101890 * A134195 A365527 A079444
KEYWORD
nonn
AUTHOR
Andrei Asinowski, Apr 15 2019
STATUS
approved