|
Search: id:A110319
|
|
|
| A110319 |
|
Triangle read by rows: T(n,k) (1<=k<=n) is number of RNA secondary structures of size n (i.e. with n nodes) having k blocks (an RNA secondary structure can be viewed as a restricted noncrossing partition). |
|
+0
3
|
|
| 1, 0, 1, 0, 1, 1, 0, 0, 3, 1, 0, 0, 1, 6, 1, 0, 0, 0, 6, 10, 1, 0, 0, 0, 1, 20, 15, 1, 0, 0, 0, 0, 10, 50, 21, 1, 0, 0, 0, 0, 1, 50, 105, 28, 1, 0, 0, 0, 0, 0, 15, 175, 196, 36, 1, 0, 0, 0, 0, 0, 1, 105, 490, 336, 45, 1, 0, 0, 0, 0, 0, 0, 21, 490, 1176, 540, 55, 1, 0, 0, 0, 0, 0, 0, 1, 196
(list; table; graph; listen)
|
|
|
OFFSET
|
1,9
|
|
|
COMMENT
|
Row sums yield the RNA secondary structure numbers (A004148). Column sums yield the Catalan numbers (A000108). A rearrangement of the Narayana numbers triangle (A001263). Sum(k*T(n,k),k=1..n)=A110320(n).
|
|
REFERENCES
|
W. R. Schmitt and M. S. Waterman, Linear trees and RNA secondary structure, Discrete Appl. Math., 51, 317-323, 1994.
P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26, 1978, 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.
|
|
FORMULA
|
T(n, k)=(1/k)*binomial(k, n-k)*binomial(k, n-k+1). G.f.=[1-tz-tz^2-sqrt(1-2tz-2tz^2+t^2*z^2-2t^2*z^3+t^2*z^4)]/[2tz^2].
|
|
EXAMPLE
|
T(5,4)=6 because we have 13/2/4/5, 14/2/3/5. 15/2/3/4, 1/24/3/5, 1/25/3/4, and 1/2/35/4.
|
|
MAPLE
|
T:=(n, k)->(1/k)*binomial(k, n-k)*binomial(k, n-k+1): for n from 1 to 14 do seq(T(n, k), k=1..n) od; # yields sequence in triangular form
|
|
CROSSREFS
|
Cf. A004148, A000108, A001263, A089732, A110320.
Sequence in context: A117389 A122083 A098158 this_sequence A036872 A036871 A036876
Adjacent sequences: A110316 A110317 A110318 this_sequence A110320 A110321 A110322
|
|
KEYWORD
|
nonn,tabl
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Jul 19 2005
|
|
|
Search completed in 0.002 seconds
|
