|
%I #42 Jul 25 2020 10:41:36
%S 1,2,3,5,7,9,17,21,25,51,59,67,141,157,173,367,399,431,913,977,1041,
%T 2195,2323,2451,5141,5397,5653,11799,12311,12823,26649,27673,28697,
%U 59419,61467,63515,131101,135197,139293,286751,294943,303135,622625,639009,655393
%N Longest word T from a string S using no breakpoint-reuse.
%C 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).
%D N. I. Anderson, M. J. Paukner, M. R. Riehl, and A. M. Steinman, String Duplication Histories with No-Breakpoint-Reuse, preprint.
%H Broňa Brejová, Martin Kravec, Gad M. Landau, Tomáš Vinař, <a href="http://dx.doi.org/10.1098/rsta.2013.0133">Fast computation of a string duplication history under no-breakpoint-reuse</a>, Philos. Trans. Royal Soc. A, 21 April 2014.
%H Jean-Philippe Doyon, Vincent Ranwez, Vincent Daubin, Vincent Berry, <a href="https://doi.org/10.1093/bib/bbr045">Models, algorithms and programs for phylogeny reconciliation</a> Brief Bioinform, 12:5, 392-400, 2011.
%H <a href="/index/Rec#order_10">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,5,-5,0,-8,8,0,4,-4).
%F a(n) = (2^k)*(n-5) + 2*k + 5 with k = floor((n-1)/3).
%F From _Chai Wah Wu_, Jul 24 2020: (Start)
%F 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.
%F 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)
%e 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.
%e ABCDEFG
%e A|BCDE|F|G -> ABCDEFBCDEG
%e AB|CDEFBC|D|EG -> ABCDEFBCDCDEFBCEG
%t Table[2^#*(n - 5) + 2 # + 5 &[Floor[(n - 1)/3]], {n, 45}] (* _Michael De Vlieger_, Feb 17 2017 *)
%K nonn
%O 1,2
%A _Nicole Anderson_, Jan 02 2017
%E More terms from _Michael De Vlieger_, Feb 17 2017
%E Offset corrected by _Chai Wah Wu_, Jul 24 2020
|
