
arXiv: 1701.00928
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 a lower bound for the number of distinct Lyndon factors in a Lyndon word of length $n$ is $\lceil\log_{\phi}(n) + 1\rceil$, where $\phi$ denotes the golden ratio $(1 + \sqrt{5})/2$. Moreover, this lower bound is sharp when $n$ is a Fibonacci number and is attained by the so-called finite Fibonacci Lyndon words, which are precisely the Lyndon factors of the well-known infinite Fibonacci word $\boldsymbol{f}$ (a special example of an infinite Sturmian word). Saari (2014) conjectured that if $w$ is Lyndon word of length $n$, $n\ne 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.
FOS: Computer and information sciences, Combinatorics on words, Discrete Mathematics (cs.DM), 512, 68R15, Lyndon word, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Lyndon factor, Christoffel word, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Combinatorics on words, Discrete Mathematics (cs.DM), 512, 68R15, Lyndon word, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Lyndon factor, Christoffel word, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
