A133365 -id:A133365 - cp's OEIS frontend

A187253 Triangle read by rows: T(n,k) is the number of 3-noncrossing RNA structures on n vertices having k isolated vertices.

1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 3, 0, 1, 0, 6, 0, 6, 0, 1, 4, 0, 21, 0, 10, 0, 1, 0, 34, 0, 55, 0, 15, 0, 1, 22, 0, 157, 0, 120, 0, 21, 0, 1, 0, 232, 0, 526, 0, 231, 0, 28, 0, 1, 139, 0, 1317, 0, 1435, 0, 406, 0, 36, 0, 1, 0, 1761, 0, 5355, 0, 3388, 0, 666, 0, 45, 0, 1, 979, 0, 11883, 0, 17500, 0, 7182, 0, 1035, 0, 55, 0, 1

Offset: 0

Emeric Deutsch, Apr 24 2011

Sum of entries in row n is A133365(n).
T(n,k)=0 if n-k is odd.
T(n,0)=A187254(n).
Sum_{k=0..n} k*T(n,k) = A187255(n).

			T(4,2)=3 because we have AIAI, IAIA, AIIA, where in each structure the two A's are joined by an arc and the two I's are isolated vertices.
T(4,4)=1 because we have IIII.
T(4,0)=1 because we have ABAB, where the two A's are joined by an arc and the two B's are joined by an arc.
Triangle starts:
  1;
  0,  1;
  0,  0,  1;
  0,  1,  0,  1;
  1,  0,  3,  0,  1;
  0,  6,  0,  6,  0,  1;
  4,  0, 21,  0, 10,  0,  1.

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.

Cf. A000108, A133365, A187254, A187255.

c := proc (n) options operator, arrow: binomial(2*n, n)/(n+1) end proc: T := proc (n, l) if `mod`(n-l, 2) = 0 then sum((-1)^b*binomial(n-b, b)*binomial(n-2*b, l)*(c((1/2)*n-(1/2)*l-b)*c((1/2)*n-(1/2)*l-b+2)-c((1/2)*n-(1/2)*l-b+1)^2), b = 0 .. (1/2)*n-(1/2)*l) else 0 end if end proc: for n from 0 to 12 do seq(T(n, k), k = 0 .. n) end do; # yields sequence in triangular form

T(n,k) = Sum_{j=0..(n-k)/2} (-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), where c(n)=A000108(n) are the Catalan numbers (see Corollary 2 in the Jin et al. reference).

A103140 Number of 3-noncrossing restricted RNA structures with n vertices.

Original entry on oeis.org

1, 1, 1, 2, 5, 14, 40, 119, 364, 1145, 3688, 12139, 40734, 139071, 482214, 1695469, 6036768, 21740969, 79117822, 290674470, 1077306351, 4025068621, 15151115808, 57427176992, 219068962330, 840708048210, 3244438898552, 12586627632549, 49069788882951

Offset: 1

Parthasarathy Nambi, Sep 07 2008

nonn

a(n) is the number of 3-noncrossing partial matchings over n vertices and without arcs of length 1 and 2. - Andrey Zabolotskiy, Nov 11 2023

Andrei Asinowski, Axel Bacher, Cyril Banderier, and Bernhard Gittenberger, Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata, Laboratoire d'Informatique de Paris Nord (LIPN 2019).
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. See Table 2 on page 62 for details.

Cf. A133365, A049401.

sf3[n_] := sf3[n] = Sum[Binomial[n, 2 k] (CatalanNumber[k + 2] CatalanNumber[k] - CatalanNumber[k + 1]^2), {k, 0, n/2}]; (* this is A049401 *)
la[0, 0, 0] = 1;
la[?Negative, , ] = la[, ?Negative, ] = la[, , _?Negative] = 0;
la[n_, b1_, b2_] := la[n, b1, b2] = la[n - 2, b1 - 1, b2] + la[n - 1, b1, b2] + la[n - 4, b1, b2 - 2] + la[n - 3, b1, b2 - 1];
a[n_] := Sum[(-1)^(b1 + b2) la[n, b1, b2] sf3[n - 2 (b1 + b2)], {b1, 0, n/2}, {b2, 0, n/2}];
Table[a[n], {n, 30}] (* Andrey Zabolotskiy, Nov 11 2023, from eqs. (4.2), (4.3), and (2.14) by Jin et al. *)

Terms a(16) and beyond from Andrey Zabolotskiy, Nov 11 2023

cp's OEIS Frontend

A187253 Triangle read by rows: T(n,k) is the number of 3-noncrossing RNA structures on n vertices having k isolated vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula