|
| |
|
|
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_{n->infinity} a(n)/A004148(n) = 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).
|
|
|
LINKS
|
Table of n, a(n) for n=0..30.
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, Polynômes orthogonaux et problèmes d'énumeration en biologie moléculaire, Sem. Loth. Comb. B08l (1984) 79-86.
M. S. Waterman, Home Page (contains copies of his papers)
|
|
|
FORMULA
|
a(n) = 2*Sum_{k=ceiling((n+1)/2)..n} binomial(k, n-k)*binomial(k+1, n-k+2)/k 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).
a(n) ~ 5^(1/4) * phi^(2*n+4) / (sqrt(Pi) * n^(3/2)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, May 29 2022
D-finite with recurrence (n+4)*a(n) +(-3*n-7)*a(n-1) +2*n*a(n-2) +3*(-n+1)*a(n-3) +2*(n-2)*a(n-4) +(-3*n+13)*a(n-5) +(n-6)*a(n-6)=0. - R. J. Mathar, Jul 26 2022
|
|
|
CROSSREFS
|
Cf. A004148, A190170.
Sequence in context: A132045 A032143 A032160 * A316694 A000646 A316770
Adjacent sequences: A089732 A089733 A089734 * A089736 A089737 A089738
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
Emeric Deutsch, Jan 07 2004
|
|
|
STATUS
|
approved
|
| |
|
|
