Logo image
Back
Counting Lyndon factors
Journal article   Open access   Peer reviewed

Counting Lyndon factors

A. Glen, J. Simpson and W.F. Smyth
Electronic Journal of Combinatorics, Vol.24(3)
2017
pdf
lyndon.pdfDownloadView
Published (Version of Record) Open Access
url
Free to Read *No subscription requiredView

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 σ, 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 xn 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ϕ(n)+1⌉, where ϕ denotes the golden ratio (1+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" -- a special example of a "infinite Sturmian word". Saari (2014) conjectured that if w is Lyndon word of length n, n≠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.

Details

Metrics

100 File views/ downloads
128 Record Views
Logo image