login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 56th year. In the past year we added 10000 new sequences and reached almost 9000 citations (which often say "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A091964 Number of left factors of peakless Motzkin paths of length n. 4
1, 2, 4, 9, 21, 50, 121, 296, 730, 1812, 4521, 11328, 28485, 71844, 181674, 460443, 1169283, 2974574, 7578937, 19337489, 49401526, 126350742, 323495259, 829033334, 2126454271, 5458711430, 14023219126, 36049991901, 92734505565 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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.

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

Equals diagonal sums of triangle A124428. - Paul D. Hanna, Oct 31 2006

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Andrei Asinowski, Axel Bacher, Cyril Banderier, Bernhard Gittenberger, Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Enumerative Aspects, 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.

Andrei Asinowski, Axel Bacher, Cyril Banderier, Bernhard Gittenberger, Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata, Laboratoire d'Informatique de Paris Nord (LIPN 2019).

Ivo L. Hofacker, Christian M. Reidys, and Peter F. Stadler, Symmetric circular matchings and RNA folding. Discr. Math., 312:100-112, 2012. See Prop. 5, C_2^{1}(z).

Asamoah Nkwanta, Lattice paths and RNA secondary structures, DIMACS Series in Discrete Math. and Theoretical Computer Science, 34, 1997, 137-147.

FORMULA

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

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

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

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

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

a(n) ~ (3+sqrt(5))^n / (sqrt(7*sqrt(5)-15) * sqrt(Pi*n) * 2^(n-1/2)). - Vaclav Kotesovec, Feb 12 2014

EXAMPLE

a(2)=4 because we have hh, hu, uh and uu.

MATHEMATICA

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 *)

PROG

(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

(PARI) a(n)=sum(k=0, n, binomial((n+k)\2, k)*binomial((n+k+1)\2, k)) \\ Paul D. Hanna, Oct 31 2006

(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

(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

CROSSREFS

Cf. A004148, A104559, A124428.

Sequence in context: A296201 A027826 A261664 * A092423 A238438 A257104

Adjacent sequences:  A091961 A091962 A091963 * A091965 A091966 A091967

KEYWORD

nonn

AUTHOR

Emeric Deutsch, Mar 13 2004

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 3 16:20 EST 2020. Contains 338906 sequences. (Running on oeis4.)