Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

Counting Lyndon factors

Glen, A.ORCID: 0000-0002-9434-3412, 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.

Item Type: Journal Article
Murdoch Affiliation(s): 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