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).
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
Offset: 1
Examples
Triangle begins: 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; ... 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.
Links
- Andrew Howroyd, Table of n, a(n) for n = 1..1275
- 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, Polynômes orthogonaux et problèmes d'énumeration en biologie moléculaire, Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, Actes 8e Sem. Lotharingien, pp. 79-86.
Programs
-
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
-
Mathematica
T[n_, k_] := (1/k)*Binomial[k, n - k]*Binomial[k, n - k + 1]; Table[T[n, k], {n, 1, 14}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jul 06 2018, from Maple *) -
PARI
T(n,k) = (1/k)*binomial(k, n-k)*binomial(k, n-k+1); \\ Andrew Howroyd, Feb 27 2018
Formula
Sum_{k=1..n} k*T(n,k) = A110320(n).
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).
Comments