Les arbres binaires compactés possèdent un exponentiel étiré
Time: 10:30 -- Location: à distance par Zoom
Lien de connection : https://zoom.us/j/665864494?pwd=aFFwZmZjMUVvNHpoVlQ0Z0ZGb0VKUT09 Meeting ID: 665 864 494 Password: 073084
Un arbre binaire compacté est un graphe acyclique dirigé qui représente un arbre binaire de façon sans redondances, dans le sens que tous les sous-arbres isomorphes sont partagés. Nous montrons que le nombre des arbres binaires compactés de tailles n croît asymptotiquement en \(\Theta(n! 4^n e^{3 a_1 n^{1/3}} n^{3/4})\), avec a_1 ≈ -2,338 la plus grande racine de la fonction d'Airy. Ce résultat est obtenu à partir d'une nouvelle récurrence des nombres de ces arbres compactés, et avec une nouvelle méthode qui, inspirée par des estimations empiriques suffisament précises, prouve des bonnes bornes par induction. Avec la même méthode, nous avons obtenu aussi l'énumération asymptotique des automates minimaux qui reconnaissent un langage fini d'un alphabet binaire, qui possède aussi un exponentiel étiré. Par sa simplicité, notre méthode s'applique potentiellement aux autres objets. Il s'agit d'un travail commun avec Andrew Elvey Price et Michael Wallner.