|
%I #14 Jan 25 2023 12:09:45
%S 1,2,4,8,16,32,65,136,298,691,1694,4340,11433,30510,81592,217238,
%T 573970,1503296,3904181,10065079,25796324,65837541,167602092,
%U 426213784,1084095329,2760717190,7043305930,18008810836,46151503544,118529776510,304998080821
%N Number of Motzkin meanders of length n with an even number of humps and without peaks.
%C 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.
%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 - 4*t^2 + 4*t - 1 + sqrt(t^6 - 4*t^5 + 4*t^4 - 2*t^3 + 4*t^2 - 4*t + 1))/((-t^3 + 4*t^2 - 4*t + 1)*t) + (1/4)*(-t^3 - 4*t^2 + 4*t - 1 + sqrt(t^6 + 4*t^5 - 4*t^4 + 2*t^3 + 4*t^2 - 4*t + 1))/((t^3 + 4*t^2 - 4*t + 1)*t).
%F a(n) + A325919(n) = A091964(n). - _R. J. Mathar_, Jan 25 2023
%e For n=0..5 we have a(n)=2^n because for these values we have only the humpless paths {U, H}^n. For n=6, the only "extra" path is UHDUHD. For n=7, the eight "extra" paths are UHDUHHD, UHHDUHD, UHDUHDH, UHDUHDU, UHDHUHD, UHDUUHD, HUHDUHD, UUHDUHD.
%t CoefficientList[Series[(1/4)*(x^3 - 4*x^2 + 4*x - 1 + Sqrt[x^6 - 4*x^5 + 4*x^4 - 2*x^3 + 4*x^2 - 4*x + 1])/((-x^3 + 4*x^2 - 4*x + 1)*x) + (1/4)*(-x^3 - 4*x^2 + 4*x - 1 + Sqrt[x^6 + 4*x^5 - 4*x^4 + 2*x^3 + 4*x^2 - 4*x + 1])/((x^3 + 4*x^2 - 4*x + 1)*x), {x, 0, 40}], x] (* _Vaclav Kotesovec_, Jun 05 2019 *)
%K nonn
%O 0,2
%A _Andrei Asinowski_, May 28 2019
|
