Nicole Anderson - cp's OEIS frontend

User: Nicole Anderson

Nicole Anderson has authored 3 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, 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

A280429 Longest word T from a string S using no breakpoint-reuse.

Original entry on oeis.org

1, 2, 3, 5, 7, 9, 17, 21, 25, 51, 59, 67, 141, 157, 173, 367, 399, 431, 913, 977, 1041, 2195, 2323, 2451, 5141, 5397, 5653, 11799, 12311, 12823, 26649, 27673, 28697, 59419, 61467, 63515, 131101, 135197, 139293, 286751, 294943, 303135, 622625, 639009, 655393

Offset: 1

Nicole Anderson, Jan 02 2017

nonn

We start with a string, of length n, that is the identity permutation of alphabet letters. The space between two adjacent letters is called a breakpoint. We then apply duplications, which take a substring and inserts it into another part of the string. Each duplication uses three breakpoints; two for the substring and one for its destination. The destination cannot be within the substring to be duplicated. Each breakpoint can only be used once. These duplications produce a word T. The formula for the longest possible T uses the length of each string (n) and the most duplications that can occur (k).

			In this case, S is a string with length 7. There are 6 breakpoints so 2 duplications can be made. The longest possible T has length 17 which can be obtained using the process below.
ABCDEFG
A|BCDE|F|G -> ABCDEFBCDEG
AB|CDEFBC|D|EG -> ABCDEFBCDCDEFBCEG

N. I. Anderson, M. J. Paukner, M. R. Riehl, and A. M. Steinman, String Duplication Histories with No-Breakpoint-Reuse, preprint.

Broňa Brejová, Martin Kravec, Gad M. Landau, Tomáš Vinař, Fast computation of a string duplication history under no-breakpoint-reuse, Philos. Trans. Royal Soc. A, 21 April 2014.
Jean-Philippe Doyon, Vincent Ranwez, Vincent Daubin, Vincent Berry, Models, algorithms and programs for phylogeny reconciliation Brief Bioinform, 12:5, 392-400, 2011.
Index entries for linear recurrences with constant coefficients, signature (1,0,5,-5,0,-8,8,0,4,-4).

Table[2^#*(n - 5) + 2 # + 5 &[Floor[(n - 1)/3]], {n, 45}] (* Michael De Vlieger, Feb 17 2017 *)

a(n) = (2^k)*(n-5) + 2*k + 5 with k = floor((n-1)/3).
From Chai Wah Wu, Jul 24 2020: (Start)
a(n) = a(n-1) + 5*a(n-3) - 5*a(n-4) - 8*a(n-6) + 8*a(n-7) + 4*a(n-9) - 4*a(n-10) for n > 10.
G.f.: x*(-2*x^9 + 2*x^8 + 2*x^7 + 6*x^6 - 3*x^5 - 3*x^4 - 3*x^3 + x^2 + x + 1)/((x - 1)^2*(2*x^3 - 1)^2*(x^2 + x + 1)). (End)

More terms from Michael De Vlieger, Feb 17 2017

Offset corrected by Chai Wah Wu, Jul 24 2020

A280430 Longest word T from 2 equal length strings S using no breakpoint reuse.

Original entry on oeis.org

2, 4, 7, 14, 19, 34, 63, 76, 137, 248, 282, 502, 891, 980, 1718, 3000, 3233, 5594, 9646, 10256, 17565, 30000, 31597, 53690, 91033, 95214, 160803, 271108, 282054, 474060, 795677, 824334, 1380142, 2308114, 2383139, 3977364, 6631898, 6828316, 11366227

Offset: 0

Nicole Anderson, Jan 02 2017

nonn

We start with two strings, of length n, that are the identity permutation of alphabet letters. The space between two adjacent letters is called a breakpoint. We then apply duplications, which take a substring from one string and insert it into the center of the other string. Each duplication uses three breakpoints; two for the substring and one for its destination. Each breakpoint can only be used once. This alternating duplications pattern produces a word T. The formula for the longest possible T uses the length of each string (n).

			In this case, S is 2 strings with length 5. There are 8 breakpoints so 2 duplications can be made. The longest possible T has length 19 which can be obtained using the process below.
ABCDE FGHIJ
A|BCD|E  FG|HIJ becomes ABCDE FGBCDHIJ after inserting BCD between G and H.
AB|CDE  F|GBCDHI|J becomes ABGBCDHICDE FGBCDHIJ after inserting GBCDHI between B and C.

N. I. Anderson, M. J. Paukner, M. R. Riehl, and A. M. Steinman, String Duplication Histories with No-Breakpoint-Reuse, preprint.

Brona Brejová, Gad M. Landau, Tomáš Vinar, Fast computation of a string duplication history under no-breakpoint-reuse, Philos T Roy Soc A 372:20130133.
Jean-Philippe Doyon, Vincent Ranwez, Vincent Daubin, Vincent Berry, Models, algorithms and programs for phylogeny reconciliation, Brief Bioinform, 12:5, 392-400, 2011.

Table[n + Simplify@ Sum[(((n - 2)/(1 + #2^2)) + (2/(#2 - #1))) #1^k + (((#2^2 (n - 2))/(1 + #2^2)) - (2/(#2 - #1))) #2^k + 2, {k, 0, Floor[2 (n - 1)/3]}] & @@ ((1 + Sqrt[5] {1, -1})/2), {n, 53}] (* Michael De Vlieger, Mar 01 2017 *)

a(n) = n + Sum_{0..k} (((n-2)/(1+Beta^2)) + (2/(Beta-alpha)))alpha^k + (((Beta^2(n-2))/(1+Beta^2)) - (2/(Beta-alpha)))Beta^k + 2 where alpha = (1+sqrt(5))/2, beta = (1-sqrt(5))/2, n = number of letters in each chromosome, and k = floor(2(n-1)/3).

Conjecture: (2 +2*x +3*x^2 -7*x^3 -9*x^4 -6*x^5 +14*x^6 +12*x^7 +7*x^8 -7*x^9 -6*x^10 -3*x^11 +x^13+x^14)/ (1+x+x^2)/ (x-1)^2/ (x^6-3*x^3+1)^2 . - R. J. Mathar, Mar 06 2022

More terms from Michael De Vlieger, Mar 01 2017

cp's OEIS Frontend

User: Nicole Anderson

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

A280429 Longest word T from a string S using no breakpoint-reuse.

Views

Author

Keywords

Comments

Examples

References

Links

Programs

Mathematica

Formula

Extensions

A280430 Longest word T from 2 equal length strings S using no breakpoint reuse.

Views

Author

Keywords

Comments

Examples

References

Links

Programs

Mathematica

Formula

Extensions