login
A280430
Longest word T from 2 equal length strings S using no breakpoint reuse.
0
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,1
COMMENTS
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).
REFERENCES
N. I. Anderson, M. J. Paukner, M. R. Riehl, and A. M. Steinman, String Duplication Histories with No-Breakpoint-Reuse, preprint.
LINKS
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.
FORMULA
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
EXAMPLE
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.
MATHEMATICA
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 *)
CROSSREFS
Sequence in context: A133638 A367266 A018505 * A108329 A057264 A045514
KEYWORD
nonn
AUTHOR
Nicole Anderson, Jan 02 2017
EXTENSIONS
More terms from Michael De Vlieger, Mar 01 2017
STATUS
approved