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.

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

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 * A370886 A135335 A336989

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