A256334 -id:A256334 - 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.

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

Offset: 1

Nicole Anderson, Apr 02 2017

nonn

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.

			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.

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

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

Cf. A000108, A014137, A014138, A256334.

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

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)).
(End)
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

A289834 Number of perfect matchings on n edges which represent RNA secondary folding structures characterized by the Lyngso and Pedersen (L&P) family and the Cao and Chen (C&C) family.

Original entry on oeis.org

1, 1, 3, 11, 39, 134, 456, 1557, 5364, 18674, 65680, 233182, 834796, 3010712, 10929245, 39904623, 146451871, 539972534, 1999185777, 7429623640, 27705320423, 103636336176, 388775988319, 1462261313876, 5513152229901, 20832701135628, 78884459229627

Offset: 0

Kyle Goryl, Jul 13 2017

nonn

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

Cf. A000108, A256334.

a:= proc(n) option remember; `if`(n<4, [1$2, 3, 11][n+1],
      (2*(74*n^2-69*n-110)*a(n-1)-3*(89*n^2-139*n-70)*a(n-2)+
       2*(91*n^2-204*n-52)*a(n-3)-4*(5*n+1)*(2*n-7)*a(n-4))
       /((n+2)*(23*n-43)))
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Jul 13 2017

c[n_] := c[n] = CatalanNumber[n];
b[n_] := b[n] = If[n<2, 0, 2+((5n-9) b[n-1] - (4n-2) b[n-2])/(n-1)];
a[n_] := Sum[c[i] Sum[c[j]-(n-i), {j, 1, n-i}], {i, 0, n-2}] + b[n] + c[n];
a /@ Range[0, 40] (* Jean-François Alcover, Nov 29 2020 *)

from functools import cache
@cache
def a(n):
    return (
        [1, 1, 3, 11][n]
        if n < 4
        else (
              2 * (74 * n ** 2 - 69 * n - 110) * a(n - 1)
            - 3 * (89 * n ** 2 - 139 * n - 70) * a(n - 2)
            + 2 * (91 * n ** 2 - 204 * n - 52) * a(n - 3)
            - 4 * (5 * n + 1) * (2 * n - 7) * a(n - 4)
        )
        // ((n + 2) * (23 * n - 43))
    )
print([a(n) for n in range(27)])
# Indranil Ghosh, Jul 15 2017, after Maple code, updated by Peter Luschny, Nov 29 2020

a(n) = Sum_{i=0..n-2} C_i*(Sum_{j=1..n-i} C_j - (n-i)) + C_n where C is A000108.
From Vaclav Kotesovec, Jul 13 2017: (Start)
D-finite recurrence (of order 3): (n+2)*(41*n^3 - 228*n^2 + 391*n - 180)*a(n) = 6*(41*n^4 - 187*n^3 + 192*n^2 + 120*n - 160)*a(n-1) - 3*(3*n - 4)*(41*n^3 - 146*n^2 + 83*n + 70)*a(n-2) + 2*(2*n - 5)*(41*n^3 - 105*n^2 + 58*n + 24)*a(n-3).
a(n) ~ 41 * 4^n / (9*sqrt(Pi)*n^(3/2)).
(End)

More terms from Alois P. Heinz, Jul 13 2017

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula