

A280429


Longest word T from a string S using no breakpointreuse.


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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 NoBreakpointReuse, preprint.


LINKS

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


FORMULA

a(n) = (2^k)*(n5) + 2*k + 5 with k = floor((n1)/3).
From Chai Wah Wu, Jul 24 2020: (Start)
a(n) = a(n1) + 5*a(n3)  5*a(n4)  8*a(n6) + 8*a(n7) + 4*a(n9)  4*a(n10) 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
ABCDEFG > ABCDEFBCDEG
ABCDEFBCDEG > 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
Adjacent sequences: A280426 A280427 A280428 * A280430 A280431 A280432


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



