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,4

Links

Table of n, a(n) for n=0..22.

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.

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

a(n) = A358119(n) - A358118(n), (see first formula). - Peter Luschny, Nov 11 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

Example

a(3) = 4 because we have ABACBC, ABCBAC, ABCACB, and ABCBCA, where identically labeled vertices are assumed to be joined by an arc.

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

Crossrefs

Cf. A000108, A187253, A358118, A358119.

Sequence in context: A366119 A200731 A193116 * A325453 A216712 A240586

Adjacent sequences: A187251 A187252 A187253 * A187255 A187256 A187257

Keyword

nonn

Author

Emeric Deutsch, Apr 24 2011

Status

approved