login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A133365 Number of 3-noncrossing RNA structures, i.e., the number of 3-noncrossing partial matchings over n vertices and without arcs of length 1. 2
1, 1, 2, 5, 13, 36, 105, 321, 1018, 3334, 11216, 38635, 135835, 486337, 1769500, 6531796, 24425758, 92420026, 353444218, 1364933719, 5318450239, 20894505025, 82713826842, 329746065427, 1323179962753, 5341963415921, 21689519880470, 88533441655211 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

a(n) is the sum of entries in row n of the triangle in A187253.

a(n) is asymptotically equal to 4!*10.4724*((5+sqrt(21))/2)^n/(n(n-1)(n-2)(n-3)(n-4)).

LINKS

Table of n, a(n) for n=1..28.

Emma Y. Jin, Jing Qin and Christian M. Reidys, Combinatorics of RNA structures with pseudoknots, arXiv:0704.2518 [math.CO], 2007.

Emma Y. Jin, Jing Qin and Christian M. Reidys, Combinatorics of RNA structures with pseudoknots, Bulletin of Mathematical Biology Vol. 70 (2008) pp. 45-67.

Emma Y. Jin and Christian M. Reidys, Asymptotic Enumeration of RNA Structures with Pseudoknots, arXiv:0706.3137 [q-bio.BM], 2007.

Emma Y. Jin and Christian M. Reidys, Asymptotic Enumeration of RNA Structures with Pseudoknots, Bulletin of Mathematical Biology 70 (2008), 951-970.

Emma Y. Jin and Christian M. Reidys, Central and local limit theorems for RNA structures, J. Theoretical Biology, 250, 2008, 547-559.

FORMULA

a(n) = Sum_{k=0..n} T(n,k), where T(n,k) = Sum((-1)^j*binomial(n-j,j)*binomial(n-2j,k)*[c((n-k)/2-2j)*c((n-k)/2-j+2)-c((n-k)/2-j+1)^2], j=0..(n-k)/2), and c(n)=A000108(n) are the Catalan numbers. [Perhaps this formula is using the convention that c(x) = 0 unless x is a nonnegative integer? - N. J. A. Sloane, Jul 24 2017]

EXAMPLE

a(4)=5 because we have ABAB, AIAI, AIIA, IAIA, and IIII, where pairs of A's and pairs of B's are assumed to be joined by an arc and the I's are isolated vertices.

MAPLE

c := proc (n) options operator, arrow: binomial(2*n, n)/(n+1) end proc: T := proc (n, k) if `mod`(n-k, 2) = 0 then sum((-1)^b*binomial(n-b, b)*binomial(n-2*b, k)*(c((1/2)*n-(1/2)*k-b)*c((1/2)*n-(1/2)*k-b+2)-c((1/2)*n-(1/2)*k-b+1)^2), b = 0 .. (1/2)*n-(1/2)*k) else 0 end if end proc: seq(add(T(n, k), k = 0 .. n), n = 1 .. 28);

MATHEMATICA

c = CatalanNumber;

T[n_, k_] := If[EvenQ[m = n-k], Sum[(-1)^b*Binomial[n-b, b] * Binomial[n - 2*b, k] * (c[m/2-b]*c[m/2-b+2] - c[m/2-b+1]^2), {b, 0, m/2}], 0];

a[n_] := Sum[T[n, k], {k, 0, n}];

Array[a, 28] (* Jean-Fran├žois Alcover, Nov 26 2017, from Maple *)

CROSSREFS

Cf. A000108, A187253.

Sequence in context: A114465 A135310 A135337 * A135335 A066723 A000994

Adjacent sequences:  A133362 A133363 A133364 * A133366 A133367 A133368

KEYWORD

nonn

AUTHOR

Emma Y. Jin (emma(AT)cfc.nankai.edu.cn), Oct 26 2007

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 April 9 20:34 EDT 2020. Contains 333362 sequences. (Running on oeis4.)