login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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.

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

Cf. A000108, A001263, A004148, A089732, A110320.

Sequence in context: A117389 A122083 A098158 * A036872 A036871 A036876

Adjacent sequences:  A110316 A110317 A110318 * A110320 A110321 A110322

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Jul 19 2005

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 21 08:29 EDT 2019. Contains 326162 sequences. (Running on oeis4.)