This site is supported by donations to The OEIS Foundation.



Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A089737 Number of (1,1) steps starting at level zero in all peakless Motzkin paths of length n+3. 1
1, 3, 7, 17, 41, 98, 235, 565, 1362, 3294, 7992, 19450, 47475, 116204, 285178, 701585, 1730003, 4275162, 10586164, 26263365, 65273566, 162499838, 405185762, 1011815774, 2530219435, 6335642377, 15884284791, 39871297479, 100194076029 (list; graph; refs; listen; history; text; internal format)



This sequence can be easily expressed also in RNA secondary structure terminology.

lim(a(n)/A004148(n), n=infinity) = sqrt(5).


I. L. Hofacker, P. Schuster and P. F. Stadler, Combinatorics of RNA secondary structures, Discrete Appl. Math., 88, 1998, 207-237.

P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26, 1979, 261-272.

M. Vauchassade de Chaumont and G. Viennot, Polynomes orthogonaux et problemes d'enumeration en biologie moleculaire, Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, Actes 8e Sem. Lotharingien, pp. 79-86.


Table of n, a(n) for n=0..28.

M. S. Waterman, Home Page (contains copies of his papers)

M. Vauchassade de Chaumont and G. Viennot, Polynomes orthogonaux at problemes d'enumeration en biologie moleculaire, Sem. Loth. Comb. B08l (1984) 79-86.


a(n)=sum((5k-2n-2)binomial(k, n+1-k)*binomial(k+1, n+3-k)/[k(n+4-k)], k=ceil(n/2+1)..n+1). a(n)=A004148(n+5)-2A004148(n+4)+A004148(n+3)-A004148(n+2). G.f.=2/[1-3z+2z^2-2z^3+2z^4-z^5+(1-2z+z^2-z^3)sqrt(1-2z-z^2-2z^3+z^4)].


a(2)=7 because in the eight peakless Motzkin paths of length 5, namely HHHHH, HHU'HD, HU'HHD, HU'HDH, U'HDHH, U'HHDH, U'HHHD and U'UHDD, where U=(1,1), D=(1,-1), H=(1,0), we have altogether seven U steps starting at level zero (indicated by U').


Cf. A004148.

Sequence in context: A272480 A131056 A077851 * A001333 A123335 A078057

Adjacent sequences:  A089734 A089735 A089736 * A089738 A089739 A089740




Emeric Deutsch, Jan 07 2004



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 January 17 10:30 EST 2019. Contains 319218 sequences. (Running on oeis4.)