|
| |
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
