Name
Abstract | ||
|---|---|---|
In this paper, we determine the maximum number of distinct Lyndon factors that a word of length n can contain. We also derive formulas for the expected total number of Lyndon factors in a word of length n on an alphabet of size sigma, as well as the expected number of distinct Lyndon factors in such a word. The minimum number of distinct Lyndon factors in a word of length n is 1 and the minimum total number is n, with both bounds being achieved by x(n) where x is a letter. A more interesting question to ask is what is the minimum number of distinct Lyndon factors in a Lyndon word of length n? In this direction, it is known (Saari, 2014) that an optimal lower bound for the number of distinct Lyndon factors in a Lyndon word of length n is [log(phi)(n)+1], where phi denotes the golden ratio (1+root 5)/2. Moreover, this lower bound is attained by the so-called finite Fibonacci Lyndon words, which are precisely the Lyndon factors of the well-known infinite Fibonacci word f (a special example of a infinite Sturmian word). Saari (2014) conjectured that if w is Lyndon word of length n, n not equal 6, containing the least number of distinct Lyndon factors over all Lyndon words of the same length, then w is a Christoffel word (i.e., a Lyndon factor of an infinite Sturmian word). We give a counterexample to this conjecture. Furthermore, we generalise Saari's result on the number of distinct Lyndon factors of a Fibonacci Lyndon word by determining the number of distinct Lyndon factors of a given Christoffel word. We end with two open problems. |
Year | Venue | DocType |
|---|---|---|
2017 | ELECTRONIC JOURNAL OF COMBINATORICS | Journal |
Volume | Issue | ISSN |
24.0 | 3.0 | 1077-8926 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amy Glen | 1 | 121 | 9.48 |
| Jamie Simpson | 2 | 164 | 21.41 |
| William F. Smyth | 3 | 0 | 0.34 |