login
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).
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
OFFSET
1,9
COMMENTS
Row sums yield the RNA secondary structure numbers (A004148).
Column sums yield the Catalan numbers (A000108).
A rearrangement of the Narayana numbers triangle (A001263).
LINKS
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.
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).
EXAMPLE
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.
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 *)
PROG
(PARI) T(n, k) = (1/k)*binomial(k, n-k)*binomial(k, n-k+1); \\ Andrew Howroyd, Feb 27 2018
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Jul 19 2005
STATUS
approved