Catalog Home Page

Counting Lyndon factors

Glen, A., Simpson, J. and Smyth, W.F. (2017) Counting Lyndon factors. Electronic Journal of Combinatorics, 24 (3).

[img]
Preview
PDF - Published Version
Download (287kB) | Preview
Free to read: http://www.combinatorics.org/ojs/index.php/eljc/ar...
*No subscription required

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.

Publication Type: Journal Article
Murdoch Affiliation: School of Engineering and Information Technology
Publisher: E-JC
URI: http://researchrepository.murdoch.edu.au/id/eprint/38263
Item Control Page Item Control Page

Downloads

Downloads per month over past year