# The height of the Lyndon tree

1 Probabilités et statistiques
IECL - Institut Élie Cartan de Lorraine
Abstract : We consider the set $\mathcal{L}_n<$ of n-letters long Lyndon words on the alphabet $\mathcal{A}=\{0,1\}$. For a random uniform element ${L_n}$ of the set $\mathcal{L}_n$, the binary tree $\mathfrak{L} (L_n)$ obtained by successive standard factorization of $L_n$ and of the factors produced by these factorization is the $\textit{Lyndon tree}$ of $L_n$. We prove that the height $H_n$ of $\mathfrak{L} (L_n)$ satisfies $\lim \limits_n \frac{H_n}{\mathsf{ln}n}=\Delta$, in which the constant $\Delta$ is solution of an equation involving large deviation rate functions related to the asymptotics of Eulerian numbers ($\Delta ≃5.092\dots$). The convergence is the convergence in probability of random variables.
Keywords :
Type de document :
Communication dans un congrès
Alain Goupil and Gilles Schaeffer. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), pp.957-968, 2013, DMTCS Proceedings

Littérature citée [14 références]

https://hal.inria.fr/hal-01229697
Contributeur : Alain Monteil <>
Soumis le : mardi 17 novembre 2015 - 10:20:07
Dernière modification le : jeudi 11 janvier 2018 - 06:26:22
Document(s) archivé(s) le : jeudi 18 février 2016 - 11:41:02

### Fichier

dmAS0181.pdf
Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-01229697, version 1

### Citation

Lucas Mercier, Philippe Chassaing. The height of the Lyndon tree. Alain Goupil and Gilles Schaeffer. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), pp.957-968, 2013, DMTCS Proceedings. 〈hal-01229697〉

### Métriques

Consultations de la notice

## 121

Téléchargements de fichiers