The OEIS is supported by the many generous donors to the OEIS Foundation.



Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A284968 Least hairpin family matchings with n edges that are both L&P and C&C whose leftmost edge is part of a hairpin. 0
0, 1, 5, 18, 59, 190, 618, 2047, 6908, 23703, 82488, 290499, 1033398, 3707837, 13402681, 48760350, 178405139, 656043838, 2423307027, 8987427446, 33453694465, 124936258104, 467995871753, 1757900019076, 6619846420527, 24987199492678, 94520750408681 (list; graph; refs; listen; history; text; internal format)



RNA secondary structures can be modeled mathematically by considering each nucleotide as a vertex and non-backbone bonds between nucleotides as edges. (Jefferson, 2015) Since RNA is an ordered sequence of nucleotides which are connected by bonds, we can list all vertices in this order. The edges which represent the bonds that preserve this ordering are called the backbone and are omitted from the graph. Thus each vertex is incident to at most one edge and thus the graph obtained is a matching. A nested sequence of edges in a matching is called a ladder. A pair of edges that cross is called a hairpin. We look at the intersection of all largest hairpin family matchings with n edges that are both L&P and C&C whose leftmost edge is part of a hairpin. The L&P family of matchings are those which can be constructed inductively by starting with a single edge or hairpin and inflating an edge of an L&P matching by a ladder and inserting a non-crossing matching into an L&P matching. The C&C family can be constructed inductively by inserting C&C matchings in spaces shown below and then inflating the original edges by ladders.


C. R. Ahrendt, N. I. Anderson, M. R. Riehl, and M. D. Scanlan, The intersection of all Largest Hairpin Family Matchings, preprint.


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

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


From Vaclav Kotesovec, Apr 07 2017: (Start)

D-finite with recurrence: (n-2)*(n+1)*a(n) = 2*(3*n^2 - 6*n + 1)*a(n-1) - (3*n - 5)*(3*n - 2)*a(n-2) + 2*(n-1)*(2*n - 3)*a(n-3).

a(n) ~ 2^(2*n+2) / (3*sqrt(Pi)*n^(3/2)).


a(n) = (Sum_{k=1..n} Catalan(k)) - n. - Peter Luschny, Jul 22 2017

G.f.: (sqrt(1-4*x)-1)/(2*x*(x-1))-1/(x-1)^2. - Alois P. Heinz, Jul 22 2017


There are a total of 11 matchings with 3 edges that are both L&P and C&C. Of those 11, 5 begin with a hairpin.


f:= n->(-1/2*(1+I*sqrt(3))-4*4^n*GAMMA(n+3/2)*hypergeom([1, n+3/2], [n+3], 4)/(sqrt(Pi)*GAMMA(n+3)))-n;

# Alternatively:

a_list := proc(m) local L, b, s, n;

L := NULL; b := 1; s:= 0;

for n from 1 to m do

s := s + b;

L := L, s - n;

b := b * (4 * n + 2) / (n + 2);

od; L end:

a_list(27); # Peter Luschny, Jul 22 2017


Table[Sum[CatalanNumber[k], {k, 1, n}] - n, {n, 1, 27}] (* Peter Luschny, Jul 22 2017 *)



from sympy import catalan

def a(n): return sum(catalan(k) for k in range(1, n + 1)) - n

print([a(n) for n in range(1, 51)]) # Indranil Ghosh, Jul 31 2017


Cf. A000108, A014137, A014138, A256334.

Sequence in context: A301880 A034567 A133648 * A222567 A099449 A104630

Adjacent sequences: A284965 A284966 A284967 * A284969 A284970 A284971




Nicole Anderson, Apr 02 2017



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 7 11:43 EST 2022. Contains 358656 sequences. (Running on oeis4.)