|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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).
|
|
LINKS
|
|
|
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):
|
|
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];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|