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