|
|
A325918
|
|
Number of Motzkin excursions of length n with an even number of humps and without peaks.
|
|
0
|
|
|
1, 1, 1, 1, 1, 1, 2, 6, 19, 57, 161, 433, 1122, 2826, 6968, 16916, 40630, 96958, 230732, 549278, 1311473, 3146659, 7596281, 18460921, 45163078, 111164142, 275067208, 683577528, 1704485046, 4260677154, 10669252349
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,7
|
|
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.
A hump is an occurrence of the pattern UHH...HD (the number of Hs in the pattern is not fixed, and can be 0).
|
|
LINKS
|
|
|
FORMULA
|
G.f.: (1/4)*(t^3 - 2*t^2 + 2*t - 1 + sqrt(t^6 - 4*t^5 + 4*t^4 - 2*t^3 + 4*t^2 - 4*t + 1))/((t^2-t)*t)+(1/4)*(-t^3 - 2*t^2 - 1 + sqrt(t^6 + 4*t^5 - 4*t^4 + 2*t^3 + 4*t^2 - 4*t + 1) + 2*t)/((t^2-t)*t).
|
|
EXAMPLE
|
For n=0..5 we have a(n)=1 because for these values we have only the humpless paths HH...H. For n=6, the only "extra" path is UHDUHD. For n=7, the five "extra" paths are UHDUHHD, UHHDUHD, HUHDUHD, UHDHUHD, UHDUHDH.
|
|
MATHEMATICA
|
CoefficientList[Series[(1/4)*(x^3 - 2*x^2 + 2*x - 1 + Sqrt[x^6 - 4*x^5 + 4*x^4 - 2*x^3 + 4*x^2 - 4*x + 1])/((x^2-x)*x)+(1/4)*(-x^3 - 2*x^2 - 1 + Sqrt[x^6 + 4*x^5 - 4*x^4 + 2*x^3 + 4*x^2 - 4*x + 1] + 2*x)/((x^2-x)*x), {x, 0, 40}], x] (* Vaclav Kotesovec, Jun 05 2019 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|