Schröder's paths and random hierarchies (Q5941076)

Un chemin de Schröder est un chemin positif du plan \(Z^{2}\) commençant et terminant sur l'axe des abscisses en effectuant des pas Nord-Est, Sud-Est, ou deux pas Est consécutifs. Nous donnons dans cet article un algorithme de complexité moyenne \(O(n)\) en espace et en temps qui engendre de façon aléatoire et uniforme un chemin de Schröder de longueur \(2n.\) Si l'on considère uniquement les chemins de Schröder n'ayant aucun pas horizontal sur l'axe des abscisses, on obtient un ensemble de chemins énumérés par les petits nombre de Schröder. Nous donnons une bijection entre ces chemins et des arbres ordonnés enracinés, appelés arbres de Schröder ou hiérarchies ordonnées, dont les noeuds internes ont au moins deux fils. Nous déduisons de cette bijection un algorithme linéaire de génération aléatoire et uniforme de hiérarchies ordonnées selon le nombre de feuilles.