Intervalles de Tamari et énumération

Intervalles de Tamari et énumération

Comme nous l’avons vu dans le chapitre précédent, les éléments PT de PBT s’expriment comme une somme de permutations dans FQSym. Ces permutations appartiennent à la classe sylvestre de T . Ce sont les extensions linéaires de l’arbre binaire et elles forment un intervalle de l’ordre faible. Les éléments HT et ETsont aussi des sommes sur des intervalles de l’ordre faible qui englobent cette fois plusieurs classes sylvestres. Plus précisément, ce sont les extensions linéaires des arbres T ′ ≤ T (resp. T ′ ≥ T ) pour l’ordre de Tamari. En fait, on peut exprimer ces intervalles initiaux et finaux comme les extensions linéaires des deux arbres planaires obtenus par la bijection décrite au paragraphe 6.1.3. Plus généralement, un intervalle de Tamari [T1, T2] est encodé par un poset particulier dont les exten- sions linéaires correspondent aux classes sylvestres des arbres inclus dans [T1, T2]. Nous appelons ces posets les intervalles-posets de Tamari et utilisons leurs pro- priétés combinatoires pour obtenir de nouveaux résultats sur le treillis de Tamari.Cette formule est obtenue par la résolution d’une équation fonctionnelle sur la série génératrice des intervalles de Tamari. Pour prouver que la série généra- trice vérifie bien l’équation fonctionnelle, Chapoton utilise des arguments combi- natoires. Nous proposons dans ce chapitre une nouvelle preuve de ce résultat util- isant les intervalles-posets. L’équation fonctionnelle donnée par Chapoton peut s’exprimer en fonction d’un opérateur bilinéaire qui s’interprète simplement en termes d’intervalles-posets. On note Φ(x, y) la série génératrice des intervalles de Tamari où y compte la taille des arbres et x le nombre de nœuds sur la branche gauche du plus petit arbre de l’intervalle. On prouve que.

Théorème 7.0.6. Soit T un arbre binaire. Son polynôme de Tamari BT (x) compte le nombre d’arbres inférieurs ou égaux à T pour l’ordre de Tamari en fonction du nombre de nœuds sur leur branche gauche. En particulier BT (1) est le nombre d’arbres inférieurs ou égaux à T .Un exemple de calcul du polynôme de Tamari et du résultat du théorème est donné figure 7.1. La preuve du théorème 7.0.6 est donné paragraphe 7.2.3. Nous commençons au paragraphe 7.1 par définir les intervalles-posets et nous en donnons les principales propriétés. Dans le paragraphe 7.2.1, nous décrivons une opération de composition sur les intervalles-posets. Nous utilisons cette opéra- tion, tout d’abord pour donner une nouvelle preuve du résultat de Chapoton sur la fonction génératrice des intervalles (paragraphe 7.2.2) puis pour prouver le théorème 7.0.6 (paragraphe 7.2.3). Au paragraphe 7.2.4, nous faisons le lien avec un autre résultat de Chapoton sur les flots d’arbres enracinés [Cha13]. Les résul- tats de ce chapitre découlent d’un travail fait en commun avec Grégory Chatel et sont publiés dans [CP13].Définition 7.1.1. Soit T un arbre binaire. On identifie T à son arbre binaire de recherche que l’on considère comme un poset. On note a ⊳T b si a précède b dans le poset c’est-à-dire si a est dans le sous-arbre issu de b. Si a ⊳T b et a < b alors a est dans le sous-arbre gauche de b et on dit que a ⊳T b est une relation croissante de b. Si b ⊳T a alors b est dans le sous-arbre droit de a et on dit que b ⊳T a est une relation décroissante.

Un exemple de la construction est donné figure 7.2.Les deux opérations sont en fait chacune des bijections : on peut retrouverl’arbre binaire à partir de sa forêt initiale ou de sa forêt finale. Ainsi, la bijection entre la forêt finale et l’arbre binaire est celle donnée entre les arbres planaires et les arbres binaires au paragraphe 6.1.3. À partir d’une forêt étiquetée, on obtient en effet un arbre planaire en supprimant les étiquettes et en rajoutant une racine commune aux arbres. La construction récursive de l’arbre binaire en fonction desa forêt initiale ou finale est illustrée figure 7.2. On donne à présent la condi- tion nécessaire et suffisante sur l’étiquetage d’une forêt pour qu’il corresponde à l’étiquetage de l’arbre binaire de recherche correspondant.Tout d’abord, prouvons que si F est la forêt finale d’un arbre binaire T , alors la condition est vérifiée. Soit c > a tel que c ⊳F a. Par construction, on a c ⊳T a ce qui signifie que c est dans le sous-arbre droit de a dans T . Soit b tel que a < b < c. Trois configurations sont possibles : soit a ⊳T b et a est dans le sous-arbre gauche de b, soit a et b ne sont pas comparables, soit b ⊳T a et b est dans le sous-arbre droit de a.Supposons que a et b ne soient pas comparables dans T . Alors, il existe b′ tel que a < b′ < b avec a dans le sous-arbre gauche de b′ et b dans le sous-arbre droit de b′. Comme c est dans le sous-arbre droit de a, il est aussi dans le sous-arbre gauche de b′. Or b′ < c ce qui contredit la règle de l’arbre binaire de recherche. Pour la même raison, a ne peut pas être dans le sous-arbre gauche de b. On a donc que b est dans le sous-arbre droit de a, c’est-à-dire b ⊳T a. La forêt F est formée par les relations décroissantes de T et on a bien b ⊳F a.