|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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];
|
|
PROG
|
(PARI) T(n, k) = (1/k)*binomial(k, n-k)*binomial(k, n-k+1); \\ Andrew Howroyd, Feb 27 2018
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|