Abstract : Dans cet exposé, je présente une approche d'énumération asymptotique du type guess-and-check pour certaines récurrences, à travers de l'étude des arbres binaires compactés. Un arbre binaire compacté est un graphe acyclique dirigé qui encode un arbre binaire, où on garde une seule copie pour les sous-arbres identiques. Nous prouvons que le nombre des arbres binaires compactés de taille n est asymptotiquement $\Theta\left(n ! 4^n \exp \left(3 a_1 n^{1 / 3}\right) n^{3 / 4}\right)$, avec $a_1 \sim-2.338$ la plus grande racine de la fonction d'Airy. Typiquement, cette expression asymptotique contient un exponentiel étiré, qui est rare et intéressant dans l'énumération asymptotique. Pour arriver à ce résultat, nous postulons d'abord une récurrence à deux paramètres pour ces nombres, puis nous devinons la forme de l'asymptotique et la démontrons toujours à travers de la récurrence. Je présenterai aussi quelques autres applications, et notre effort à généraliser cette méthode.
Travail commun avec Andrew Elvey Price et Michael Wallner.
https://igm.univ-mlv.fr/~wfang/

Keywords : recurrence; stretched exponential; compacted tree