|
%I #12 Jun 15 2019 02:53:59
%S 1,1,1,1,1,1,2,6,19,57,161,433,1122,2826,6968,16916,40630,96958,
%T 230732,549278,1311473,3146659,7596281,18460921,45163078,111164142,
%U 275067208,683577528,1704485046,4260677154,10669252349
%N Number of Motzkin excursions of length n with an even number of humps and without peaks.
%C 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.
%C A peak is an occurrence of the pattern UD.
%C A hump is an occurrence of the pattern UHH...HD (the number of Hs in the pattern is not fixed, and can be 0).
%H Andrei Asinowski, Axel Bacher, Cyril Banderier, Bernhard Gittenberger, <a href="https://lipn.univ-paris13.fr/~banderier/Papers/patterns2019.pdf">Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata</a>, Algorithmica (2019).
%H Andrei Asinowski, Axel Bacher, Cyril Banderier, Bernhard Gittenberger, <a href="https://doi.org/10.4230/LIPIcs.AofA.2018.10">Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Asymptotic Aspects and Borges's Theorem</a>, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018).
%F 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).
%e 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.
%t 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 *)
%K nonn
%O 0,7
%A _Andrei Asinowski_, May 28 2019
|
