Counting Lyndon factors (Q2401409): Difference between revisions

Two words \(u\), \(v\) are conjugates if there are words \(x\), \(y\) such that \(u=xy\) and \(v=yx.\) A word is primitive if it cannot be expressed as \(x^{n}\) for a word \(x\) and \(n\geq2\). A Lyndon word is a non-empty primitive word that is the lexicographically least word in its conjugacy class. The paper provides formulas for the following values for an alphabet of size \(\sigma\): \(D\left( \sigma,n\right) \) -- the maximum number of distinct Lyndon factors in a word of length \(n\); \(ET\left( \sigma,n\right) \) -- the expected total number of Lyndon factors (counted according to their multiplicity) in a word of length \(n\); \(ED\left( \sigma,n\right) \) -- the expected number of distinct Lyndon factors in a word of length \(n\). Then the authors provide a generalization of a result of Saari on the number of Lyndon factors of a Fibonacci Lyndon word (a Lyndon factor of the infinite Fibonacci word -- being a particular Sturmian word) by determining the number of Lyndon factors of any Christoffel word (a Lyndon factor of any Sturmian word). They present, as well, a counterexample to a conjecture of Saari that the word in the set of all Lyndon words of the same length different from 6 which contains the least number of Lyndon factors is a Christoffel word.