This site is supported by donations to The OEIS Foundation.



Annual Appeal: Please make a donation (tax deductible in USA) to keep the OEIS running. Over 4500 articles have referenced us, often saying "we would not have discovered this result without the OEIS".

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A089735 Self-convolution of A004148 (the RNA secondary structure numbers) with itself. 3
1, 2, 3, 6, 13, 28, 62, 140, 320, 740, 1728, 4068, 9645, 23010, 55195, 133042, 322078, 782758, 1909091, 4671098, 11462607, 28204212, 69569278, 171993316, 426111203, 1057757858, 2630527679, 6552998126, 16350465147, 40857321696, 102239831436 (list; graph; refs; listen; history; text; internal format)



Number of (1,0) steps at level zero in all peakless Motzkin paths of length n+1 (can be easily expressed also in RNA secondary structure terminology). Example: a(3)=6 because in the four peakless Motzkin paths of length four, namely H'H'H'H', H'UHD, UHDH' and UHHD, where U=(1,1), D=(1,-1), H=(1,0), we have six H steps at level zero (indicated by H'). lim(a(n)/A004148(n), n=infinity) = 2.

Number of UHD's starting at level 0 in all peakless Motzkin paths of length n+3; here U=(1,1), H=(1,0), and D=(1,-1). Example: a(1)=2 because in HHHH, H(UHD), (UHD)H, and UHHD we have a total of 0+1+1+0 UHD's starting at level 0 (shown between parentheses).


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..30.

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

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


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

G.f. = z^3*S^2, where S=S(z) is given by S=1+zS+z^2*S(S-1) (the g.f. of the RNA secondary structure numbers, A004148).


Cf. A004148, A190170

Sequence in context: A132045 A032143 A032160 * A000646 A197463 A032048

Adjacent sequences:  A089732 A089733 A089734 * A089736 A089737 A089738




Emeric Deutsch, Jan 07 2004



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

Content is available under The OEIS End-User License Agreement .

Last modified November 24 19:03 EST 2015. Contains 264371 sequences.