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

Author

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

Keywords

• nonn

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)).

Examples

			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.
		

Links

• 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.

Crossrefs

Cf. A000108, A187253.

Programs

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 *)

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]