cp's OEIS Frontend

A091964 Number of left factors of peakless Motzkin paths of length n.

%I A091964 #66 Jan 27 2025 10:19:45
%S A091964 1,2,4,9,21,50,121,296,730,1812,4521,11328,28485,71844,181674,460443,
%T A091964 1169283,2974574,7578937,19337489,49401526,126350742,323495259,
%U A091964 829033334,2126454271,5458711430,14023219126,36049991901,92734505565
%N A091964 Number of left factors of peakless Motzkin paths of length n.
%C A091964 Number of paths from (0,0) to the line x=n, consisting of steps u=(1,1), h=(1,0), d=(1,-1), that never go below the x-axis and a u step is never followed by a d step.
%C A091964 a(n) is also the number of peakless Motzkin paths of length n in which the (1,0)-steps at level 0 come in 2 colors. Example: a(4)=21 because, denoting u=(1,1), h=(1,0), and d=(1,-1), we have 2^4 = 16 paths of shape hhhh, 2 paths of shape huhd, 2 paths of shape uhdh, and 1 path of shape uhhd. - _Emeric Deutsch_, May 03 2011
%C A091964 Equals diagonal sums of triangle A124428. - _Paul D. Hanna_, Oct 31 2006
%H A091964 Vincenzo Librandi, <a href="/A091964/b091964.txt">Table of n, a(n) for n = 0..1000</a>
%H A091964 Andrei Asinowski, Axel Bacher, Cyril Banderier, Bernhard Gittenberger, <a href="http://doi.org/10.1007/978-3-319-77313-1_15">Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Enumerative Aspects</a>, in International Conference on Language and Automata Theory and Applications, S. Klein, C. Martín-Vide, D. Shapira (eds), Springer, Cham, pp 195-206, 2018.
%H A091964 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>, Laboratoire d'Informatique de Paris Nord (LIPN 2019).
%H A091964 Ivo L. Hofacker, Christian M. Reidys, and Peter F. Stadler, <a href="http://dx.doi.org/10.1016/j.disc.2011.06.004">Symmetric circular matchings and RNA folding</a>. Discr. Math., 312:100-112, 2012. See Prop. 5, C_2^{1}(z).
%H A091964 Asamoah Nkwanta, <a href="https://bookstore.ams.org/dimacs-34/">Lattice paths and RNA secondary structures</a>, DIMACS Series in Discrete Math. and Theoretical Computer Science, 34, 1997, 137-147.
%H A091964 Helmut Prodinger, <a href="https://arxiv.org/abs/2501.13645">Cornerless, peakless, valleyless Motzkin paths (regular and skew) and applications to bargraphs</a>, arXiv:2501.13645 [math.CO], 2025. See p. 8.
%F A091964 G.f.: 2/(1 - 3*z + z^2 + sqrt(1 - 2*z - z^2 - 2*z^3 + z^4)).
%F A091964 a(n) = Sum_{k=0..n} C(n-floor(k/2), floor((k+1)/2)) * C(n-floor((k+1)/2), floor(k/2)). - _Paul D. Hanna_, Mar 24 2005
%F A091964 a(n) = Sum_{k=0..n} C(floor((n+k)/2),k)*C(floor((n+k+1)/2),k). - _Paul D. Hanna_, Oct 31 2006
%F A091964 G.f.: 1/(1-x-x/(1-x^2/(1-x/(1-x^2/(1-x/(1-x^2/(1-... (continued fraction). - _Paul Barry_, Jun 30 2009
%F A091964 D-finite with recurrence (n+1)*a(n) + 2*(-n-1)*a(n-1) + (-n+1)*a(n-2) + 2*(-n+3)*a(n-3) + (n-3)*a(n-4) = 0. - _R. J. Mathar_, Nov 24 2012
%F A091964 a(n) ~ (3+sqrt(5))^n / (sqrt(7*sqrt(5)-15) * sqrt(Pi*n) * 2^(n-1/2)). - _Vaclav Kotesovec_, Feb 12 2014
%F A091964 Equivalently, a(n) ~ phi^(2*n + 2) / (5^(1/4) * sqrt(Pi*n)), where phi = A001622 is the golden ratio. - _Vaclav Kotesovec_, Dec 08 2021
%e A091964 a(2)=4 because we have hh, hu, uh and uu.
%t A091964 CoefficientList[Series[2/(1-3*x+x^2+Sqrt[1-2*x-x^2-2*x^3+x^4]), {x, 0, 20}], x] (* _Vaclav Kotesovec_, Feb 12 2014 *)
%o A091964 (PARI) a(n)=sum(k=0,n,binomial(n-k\2,(k+1)\2)*binomial(n-(k+1)\2,k\2)) \\ _Paul D. Hanna_, Mar 24 2005
%o A091964 (PARI) a(n)=sum(k=0,n,binomial((n+k)\2,k)*binomial((n+k+1)\2,k)) \\ _Paul D. Hanna_, Oct 31 2006
%o A091964 (Magma) [(&+[Binomial(Floor((n+k)/2),k)*Binomial(Floor((n+k+1)/2),k): k in [0..n]]): n in [0..30]]; // _G. C. Greubel_, Feb 26 2019
%o A091964 (Sage) [sum(binomial(floor((n+k)/2),k)*binomial(floor((n+k+1)/2),k) for k in (0..n)) for n in (0..30)] # _G. C. Greubel_, Feb 26 2019
%Y A091964 Cf. A004148, A104559, A124428.
%K A091964 nonn
%O A091964 0,2
%A A091964 _Emeric Deutsch_, Mar 13 2004