Frédérique Bassino: The Average Lengths of the Factors of the Standard Factorization of Lyndon Words

This is a joint work with Julien Clément and Cyril Nicaud.

A non-empty word $w$ of $\{a,b\}^*$ is a Lyndon word if and only if it is strictly smaller for the lexicographical order than any of its proper right factors. Such a word $w$ either is a letter or admits a standard factorization $uv$ where $v$ is its smallest proper right factor. For any Lyndon word $v$, we explicitly compute the generating function of Lyndon words having $v$ as right factor of the standard factorization, showing in this way that this function is rational. We establish that, for the uniform distribution over the Lyndon words of length $n$, the average length of the right factor $v$ of the standard factorization is asymptotically $3n/4$.

Back to the Index