A289031 Number of perfect matchings on n+3 edges which represent RNA secondary folding structures characterized by the Reeder and Giegerich and the Lyngso and Pedersen families, but not the family characterized by Cao and Chen.

1, 8, 42, 186, 759, 2970, 11369, 43024, 161889, 607630, 2279156, 8552292, 32124073, 120828404, 455175495, 1717506346, 6491412107, 24575174688, 93187097419, 353912403794, 1346146363275, 5127660231072, 19559151930621, 74706450932970

Offset

1,2

Comments

These matchings can be created inductively by beginning with a hairpin that has a single edge inserted into its middle, then inserting noncrossing matchings into the matching. Finally we can inflate the edges of the hairpin by ladders.

Links

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

Aziza Jefferson The Substitution Decomposition of Matchings and RNA Secondary Structures, PhD Thesis, University of Florida, 2015.

Formula

a(n) = 2*a(n-1) - a(n-2) + A003517(n+1).

D-finite recurrence: (n-1)*(n+5)*a(n) = 2*(3*n^2 + 9*n - 2)*a(n-1) - (3*n + 1)*(3*n + 7)*a(n-2) + 2*(n+1)*(2*n + 3)*a(n-3). - Vaclav Kotesovec, Jun 24 2017

a(n) ~ 2^(2*n+8) / (3*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Jun 27 2017

Crossrefs

Cf. A003517.

Sequence in context: A055082 A266940 A212337 * A093381 A097788 A171478

Adjacent sequences: A289028 A289029 A289030 * A289032 A289033 A289034

Keyword

nonn

Author

Kyle Goryl, Jun 22 2017

Status

approved