A187254 Number of 3-noncrossing RNA structures over 2n vertices with no isolated vertices.
1, 0, 1, 4, 22, 139, 979, 7484, 61018, 523995, 4696277, 43623618, 417729564, 4106089683, 41289287337, 423556384020, 4422308778458, 46904447607369, 504544306691569, 5496706186024364, 60576765646658782, 674624324569952719, 7585425185883023881
Offset: 0
Keywords
Examples
a(3) = 4 because we have ABACBC, ABCBAC, ABCACB, and ABCBCA, where identically labeled vertices are assumed to be joined by an arc.
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.
Programs
-
Maple
c := n -> binomial(2*n, n)/(n + 1): a := n -> add((-1)^j*binomial(2*n-j, j)*(c(n-j)*c(n-j+2) - c(n-j+1)^2), j = 0..n): seq(a(n), n = 0 .. 22);
-
Mathematica
Table[Sum[(-1)^j*Binomial[2*n-j,j] * (CatalanNumber[n-j]*CatalanNumber[n-j+2] - CatalanNumber[n-j+1]^2), {j,0,n}], {n,0,25}] (* Vaclav Kotesovec, Dec 10 2021 *)
Formula
a(n) = Sum_{j=0..n} (-1)^j*binomial(2n-j,j)*(c(n-j)*c(n-j+2) - c(n-j+1)^2), where c(i) = A000108(i) are the Catalan numbers.
a(n) = A187253(2*n, 0).
a(n) ~ 27 * (1 + sqrt(3))^(4*n + 2) / (Pi * n^5 * 2^(2*n + 4)). - Vaclav Kotesovec, Dec 10 2021
D-finite with recurrence (n+3)*(n+2)*a(n) + 2*(-7*n^2-2)*a(n-1) + 2*(-2*n+3)*a(n-2) + 2*(7*n^2-42*n+65)*a(n-3) - (n-5)*(n-6)*a(n-4) = 0. - R. J. Mathar, Jul 22 2022
G.f.: (1/4)*(x + 9 - (1 - 14*x + x^2)^(3/2)/x^2*hypergeom([-3/2, 5/2], [2], -16*x/(1 - 14*x + x^2))). - Mark van Hoeij, Nov 10 2022
Maple (depending on the version) gives the third-order recurrence (n - 5)*(2*n - 1)*(n - 4)*a(n - 3) - (n - 1)*(13*n - 24)*(2*n - 3)*a(n - 2) - (n - 1)*(2*n - 1)*(13*n - 2)*a(n - 1) + (n + 3)*(n + 2)*(2*n - 3)*a(n) = 0. - Peter Bala, Nov 11 2022