The standard factorization of Lyndon words:: an average point of view

A non-empty word w is a Lyndon word if and only if it is strictly smaller for the lexicographical order than any of its proper suffixes. Such a word w is either a letter or admits a standard factorization u v where v is its smallest proper suffix. For any Lyndon word v, we show that the set of Lyndon words having v as right factor of the standard factorization is regular and compute explicitly the associated generating function. Next, considering the Lyndon words of length n over a two-letter alphabet, we establish that, for the uniform distribution, the average length of the right factor v of the standard factorization is asymptotically 3n/4. (C) 2004 Elsevier B.V. All rights reserved.