cp's OEIS Frontend

A284968 Least hairpin family matchings with n edges that are both L&P and C&C whose leftmost edge is part of a hairpin.

%I A284968 #46 May 02 2020 05:28:43
%S A284968 0,1,5,18,59,190,618,2047,6908,23703,82488,290499,1033398,3707837,
%T A284968 13402681,48760350,178405139,656043838,2423307027,8987427446,
%U A284968 33453694465,124936258104,467995871753,1757900019076,6619846420527,24987199492678,94520750408681
%N A284968 Least hairpin family matchings with n edges that are both L&P and C&C whose leftmost edge is part of a hairpin.
%C A284968 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.
%D A284968 C. R. Ahrendt, N. I. Anderson, M. R. Riehl, and M. D. Scanlan, The intersection of all Largest Hairpin Family Matchings, preprint.
%H A284968 Aziza Jefferson, <a href="http://ufdc.ufl.edu/UFE0047620">The Substitution Decomposition of Matchings and RNA Secondary Structures</a>, PhD Thesis, University of Florida, 2015.
%F A284968 From _Vaclav Kotesovec_, Apr 07 2017: (Start)
%F A284968 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).
%F A284968 a(n) ~ 2^(2*n+2) / (3*sqrt(Pi)*n^(3/2)).
%F A284968 (End)
%F A284968 a(n) = (Sum_{k=1..n} Catalan(k)) - n. - _Peter Luschny_, Jul 22 2017
%F A284968 G.f.: (sqrt(1-4*x)-1)/(2*x*(x-1))-1/(x-1)^2. - _Alois P. Heinz_, Jul 22 2017
%e A284968 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.
%p A284968 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;
%p A284968 # Alternatively:
%p A284968 a_list := proc(m) local L, b, s, n;
%p A284968 L :=  NULL; b := 1; s:= 0;
%p A284968 for n from 1 to m do
%p A284968     s := s + b;
%p A284968     L := L, s - n;
%p A284968     b := b * (4 * n + 2) / (n + 2);
%p A284968 od; L end:
%p A284968 a_list(27); # _Peter Luschny_, Jul 22 2017
%t A284968 Table[Sum[CatalanNumber[k], {k, 1, n}] - n, {n, 1, 27}] (* _Peter Luschny_, Jul 22 2017 *)
%o A284968 (Python)
%o A284968 from sympy import catalan
%o A284968 def a(n): return sum(catalan(k) for k in range(1, n + 1)) - n
%o A284968 print([a(n) for n in range(1, 51)]) # _Indranil Ghosh_, Jul 31 2017
%Y A284968 Cf. A000108, A014137, A014138, A256334.
%K A284968 nonn
%O A284968 1,3
%A A284968 _Nicole Anderson_, Apr 02 2017