Prenons une expression logique du calcul des propositions: elle peut être représentée sous forme arborescente. Suivant les règles de construction de la formule, l'arbre sera binaire ou non, planaire ou non, et étiqueté avec différents connecteurs ou littéraux. L'énumération de tels arbres, et l'étude de leurs propriétés statistiques, sont un domaine classique d'application de la combinatoire analytique. Prenons maintenant une formule du calcul des prédicats: l'existence de quantificateurs fait que nous ne pouvons plus a priori utiliser une représentation arborescente. L'énumération de telles formules ne peut alors plus se faire suivant les techniques classiques d'énumération d'arbres, et requiert de nouvelles approches.

Une formule du calcul des prédicats est un cas particulier de ce que nous nommons "arbre enrichi": c'est un arbre auquel on ajoute des arcs partant de certains noeuds (ici ceux correspondant aux quantificateurs) et allant vers des feuilles. De manière équivalente, cela revient à colorer des arbres selon certaines règles; on peut aussi voir ces structures comme une classe particulière de graphes orientés acycliques.

Je présenterai les résultats (déjà obtenus ou en cours de finalisation) sur certaines familles d'arbres enrichis, relatifs à leur énumération et à certains paramètres, puis les possibilités d'extension à des modèles plus généraux.