login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(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)
OFFSET

0,2

COMMENTS

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

REFERENCES

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.

LINKS

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)

FORMULA

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

CROSSREFS

Cf. A004148, A190170

Sequence in context: A132045 A032143 A032160 * A000646 A197463 A032048

Adjacent sequences:  A089732 A089733 A089734 * A089736 A089737 A089738

KEYWORD

nonn

AUTHOR

Emeric Deutsch, Jan 07 2004

STATUS

approved

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 October 22 20:47 EDT 2014. Contains 248408 sequences.