

A089735


Selfconvolution 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, 207237.
P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26, 1979, 261272.
M. Vauchassade de Chaumont and G. Viennot, Polynomes orthogonaux et problemes d'enumeration en biologie moleculaire, Publ. I.R.M.A. Strasbourg, 1984, 229/S08, Actes 8e Sem. Lotharingien, pp. 7986.


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) 7986.
M. S. Waterman, Home Page (contains copies of his papers)


FORMULA

a(n)=2sum(binomial(k, nk)*binomial(k+1, nk+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/[1z+z^2+sqrt(12zz^22z^3+z^4)]^2.
G.f. = z^3*S^2, where S=S(z) is given by S=1+zS+z^2*S(S1) (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



