A091964 - OEIS

%I #63 Sep 08 2022 08:45:13

%S 1,2,4,9,21,50,121,296,730,1812,4521,11328,28485,71844,181674,460443,

%T 1169283,2974574,7578937,19337489,49401526,126350742,323495259,

%U 829033334,2126454271,5458711430,14023219126,36049991901,92734505565

%N Number of left factors of peakless Motzkin paths of length n.

%C 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 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 Equals diagonal sums of triangle A124428. - _Paul D. Hanna_, Oct 31 2006

%H Vincenzo Librandi, <a href="/A091964/b091964.txt">Table of n, a(n) for n = 0..1000</a>

%H 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 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 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 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.

%F G.f.: 2/(1 - 3*z + z^2 + sqrt(1 - 2*z - z^2 - 2*z^3 + z^4)).

%F 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 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 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 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 a(n) ~ (3+sqrt(5))^n / (sqrt(7*sqrt(5)-15) * sqrt(Pi*n) * 2^(n-1/2)). - _Vaclav Kotesovec_, Feb 12 2014

%F 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 a(2)=4 because we have hh, hu, uh and uu.

%t 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 (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 (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 (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 (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 Cf. A004148, A104559, A124428.

%K nonn

%O 0,2

%A _Emeric Deutsch_, Mar 13 2004