|
| |
|
|
A307578
|
|
Number of Motzkin excursions of length n with an odd number of peaks.
|
|
1
|
|
|
|
0, 0, 1, 2, 4, 10, 25, 62, 159, 414, 1087, 2886, 7734, 20878, 56743, 155154, 426492, 1177938, 3267359, 9098102, 25423124, 71268382, 200371507, 564861178, 1596327999, 4521633466, 12834780857, 36503642746, 104011176114, 296870510994, 848691054657, 2429877628398
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
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 terminates at the altitude 0.
A peak is an occurrence of the pattern UD.
|
|
|
LINKS
|
|
|
|
FORMULA
|
G.f.: (-2*t^2 - sqrt((1+t)*(1-3*t)) + sqrt((1-t)*(1-2*t)*(1+t+2*t^2))) / (4*t^2).
D-finite with recurrence: 2*n*(n+2)*(6213*n-138098)*a(n) +(n-1)*(12426*n^2+978417*n+821680)*a(n-1) +2*(-23065*n^3-728759*n^2+2760574*n-410840)*a(n-2) +2*(-292946*n^3+3649919*n^2-11479673*n+8929300)*a(n-3) +2*(233455*n^3-3707982*n^2+13757984*n-13497400)*a(n-4) +(608874*n^3-5758645*n^2+11199163*n+5963900)*a(n-5) +2*(848625*n^3-11463971*n^2+51225442*n-77109420)*a(n-6) -16*(n-7)*(2213*n^2+270746*n-1493325)*a(n-7) -24*(88769*n-321795)*(n-7)*(n-8)*a(n-8)=0. - R. J. Mathar, Jan 27 2020
|
|
|
EXAMPLE
|
For n = 4 the a(4) = 4 paths are UDHH, HUDH, HHUD, 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, 0, 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, 0, c] + b[x-1, y+1, 1, c]]];
a[n_] := b[n, 0, 0, 0];
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
