The height of the Lyndon tree
L. Mercier, Ph. Chassaing
Abstract
We consider the set n of n-letters long Lyndon words on the alphabet &mathcal;A={0,1}. For a random uniform element Ln of the set n, the binary tree &lyndontree; (Ln) obtained by successive standard factorization of Ln and of the factors produced by these factorization is the Lyndon tree of Ln. We prove that the height Hn of &lyndontree; (Ln) satisfies limnHnn=&constant;, in which the constant Δ is solution of an equation involving large deviation rate functions related to the asymptotics of Eulerian numbers (&constant;≃5.092...). The convergence is the convergence in probability of random variables.
Résumé. Pour un mot Ln choisi au hasard uniformément dans l'ensemble des mots de Lyndon de longueur n sur l'alphabet {0,1}, on montre que la hauteur Hn de l'arbre de Lyndon associé possède le comportement asymptotique suivant limnHnn=&constant;. La constante Δ est définie à l'aide de fonctions de taux liées au comportement asymptotique des nombres eulériens (incidemment, &constant;≃5.092...). La convergence est la convergence en probabilité des variables aléatoires.
Résumé. Pour un mot Ln choisi au hasard uniformément dans l'ensemble des mots de Lyndon de longueur n sur l'alphabet {0,1}, on montre que la hauteur Hn de l'arbre de Lyndon associé possède le comportement asymptotique suivant limnHnn=&constant;. La constante Δ est définie à l'aide de fonctions de taux liées au comportement asymptotique des nombres eulériens (incidemment, &constant;≃5.092...). La convergence est la convergence en probabilité des variables aléatoires.
Full Text: PostScript PDF