login
A280429
Longest word T from a string S using no breakpoint-reuse.
0
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,2
COMMENTS
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).
REFERENCES
N. I. Anderson, M. J. Paukner, M. R. Riehl, and A. M. Steinman, String Duplication Histories with No-Breakpoint-Reuse, preprint.
LINKS
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.
FORMULA
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)
EXAMPLE
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
MATHEMATICA
Table[2^#*(n - 5) + 2 # + 5 &[Floor[(n - 1)/3]], {n, 45}] (* Michael De Vlieger, Feb 17 2017 *)
CROSSREFS
Sequence in context: A039888 A036959 A108031 * A076387 A193622 A265249
KEYWORD
nonn
AUTHOR
Nicole Anderson, Jan 02 2017
EXTENSIONS
More terms from Michael De Vlieger, Feb 17 2017
Offset corrected by Chai Wah Wu, Jul 24 2020
STATUS
approved