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

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

Comments

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

Links

Table of n, a(n) for n=1..29.

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.

Mathematica

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

Crossrefs

Cf. A133365, A049401.

Sequence in context: A349413 A200438 A363933 * A148320 A301871 A076866

Adjacent sequences: A103137 A103138 A103139 * A103141 A103142 A103143

Keyword

nonn

Author

Parthasarathy Nambi, Sep 07 2008

Extensions

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

Status

approved