|
|
A307577
|
|
Number of Motzkin meanders of length n with an odd number of peaks.
|
|
2
|
|
|
0, 0, 1, 4, 13, 40, 119, 348, 1011, 2928, 8471, 24516, 71023, 206024, 598513, 1741332, 5073733, 14804160, 43252855, 126526756, 370551287, 1086365336, 3188090101, 9364411252, 27529374201, 80993754352, 238463467529, 702563144252, 2071200546129, 6109619428824
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
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.
|
|
LINKS
|
|
|
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))) / (4*t).
|
|
EXAMPLE
|
For n = 3 the a(3) = 4 paths are UDH, HUD, UDU, UUD.
|
|
MAPLE
|
b:= proc(x, y, t, c) option remember; `if`(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<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
|
|
|
|