Séminaire Lotharingien de Combinatoire 55 (2006), Article B55f

SUR LE NOMBRE D’INTERVALLES DANS LES TREILLIS DE TAMARI

F. CHAPOTON

Résumé. On compte le nombre d’intervalles dans les treillis de Tamari. On utilise pour cela une description récursive de l’ensemble des intervalles. On introduit ensuite une notion d’intervalle nouveau dans les treillis de Tamari et on compte les intervalles nouveaux. On obtient aussi l’inverse de deux séries particulières dans un groupe de séries formelles en arbres.

Abstract. We enumerate the intervals in the Tamari lattices. For this, we introduce an inductive description of the intervals. Then a notion of “new interval” is defined and these are also enumerated. As a side result, the inverse of two special series is computed in a group of tree-indexed series.

0. Introduction

Les treillis de Tamari sont des ordres partiels remarquables, liés aux polytopes de Stasheff (associaèdres). On peut notamment les réaliser comme l’ordre induit par une forme linéaire particulière sur l’ensemble des sommets d’une certaine version du polytope de Stasheff. Ils ont été récemment généralisés par Reading [8], qui a introduit des treillis dits cambriens, associés aux carquois sur les diagrammes de Dynkin. Dans ce contexte, les treillis de Tamari correspondent aux carquois de type 𝔸 équi-orientés.

L’objectif principal de cet article est de compter les intervalles dans les treillis de Tamari. On y parvient en obtenant une description récursive complète de l’ensemble des intervalles. On montre ainsi l’existence d’une formule close pour le nombre d’intervalles.

Un objectif secondaire est de compter ceux parmi les intervalles qui ne proviennent pas de treillis de Tamari d’indice inférieur par une sorte d’“induction”. En termes géométriques, ce sont ceux qui ne sont pas contenus dans une des facettes du polytope de Stasheff. On les appelle les intervalles nouveaux, et on démontre aussi une formule close pour le nombre d’intervalles nouveaux.

Il est assez remarquable que ces nombres d’intervalles et d’intervalles nouveaux apparaissent aussi ensemble dans l’article [3] dont le sujet est l’énumération de certaines classes de cartes planes.

Par ailleurs, on calcule l’inverse de deux éléments particuliers dans un groupe de séries formelles en arbres lié à l’opérade dendriforme. Ces séries sont des raffinements de la série génératrice usuelle des nombres d’intervalles. La découverte de ces inverses a été la clé de la description récursive des intervalles.

Fig. 1. Les treillis de Tamari Y_{3} et Y_{4}

L’utilisation du système de calcul formel MuPAD a été cruciale dans la recherche qui a abouti à cet article.

1. Les treillis de Tamari

Un arbre binaire plan est un graphe fini plan connexe et simplement connexe, dont les sommets ont pour valence 1 ou 3, muni d’un sommet de valence 1 distingué appelé la racine. Les autres sommets de valence 1 sont appelés les feuilles, les sommets de valence 3 sont appelés sommets internes. On dessine les arbres binaires plans avec les feuilles en haut et la racine en bas.

Soit Y_{n} l’ensemble des arbres binaires plans à n sommets internes. Le cardinal de Y_{n} est le nombre de Catalan c_{n} = \frac{1}{n+1} \binom{2n}{n}. Pour n = 1, il y a un seul arbre binaire plan, qui sera noté Y. Sauf mention explicite du contraire, on considère toujours qu’un arbre binaire plan a au moins un sommet interne. L’utilisation éventuelle de l’arbre trivial à une feuille, noté |, sera toujours explicitée.

Le treillis de Tamari est un ordre partiel sur l’ensemble Y_{n}, introduit par Tamari [4]. Cet ordre partiel est défini comme suit : un arbre T est plus grand qu’un arbre S si on peut passer de S à T par une suite d’opérations consistant à remplacer localement la configuration par la configuration . Le treillis Y_{1} a un seul élément : Y. Le treillis Y_{2} est juste ≤ . La figure 1 représente les diagrammes de Hasse des treillis Y_{3} et Y_{4}.

1.1. Structures algébriques. On définit des opérations / et \ sur les arbres binaires plans (y compris l’arbre trivial |) : S/T est obtenu en identifiant la racine de S avec la feuille la plus à gauche de T ; S\T est obtenu en identifiant la racine de T avec la feuille la plus à droite de S. Ces opérations sont clairement associatives. Par exemple Y/Y = et Y\Y = .

On considère l’espace vectoriel gradué Y ayant pour base Y_{n} en degré n ≥ 1 et l’arbre trivial | en degré 0. On peut étendre les opérations / et \ par linéarité.

Sur Y, on dispose donc de deux produits associatifs. Un troisième produit associatif existe, qui sera noté ∗, et qui peut être défini comme suit :

S ∗ T = ∑_{S\T ≤U≤S/T} U,  (1)

où la relation d’ordre est celle du treillis de Tamari. L’arbre trivial | est une unité pour les trois produits.

On va aussi utiliser l’opération S ∨ T définie par la greffe de S à gauche et de T à droite sur les deux feuilles de Y.

Pour plus de détails sur ces structures algébriques, on renvoie le lecteur à [7].

2. Énumération des intervalles

Soit I_{n} l’ensemble des intervalles dans le treillis de Tamari Y_{n}.

En comptant les intervalles dans les premiers treillis de Tamari, on obtient que les premiers termes de la suite |I_{n}| sont, pour n ≥ 1,

1, 3, 13, 68, 399, 2530, etc.

Une consultation de l’encyclopédie des suites [9] mène immédiatement à conjecturer le résultat suivant.

Théorème 2.1. Le nombre d’intervalles dans le treillis de Tamari Y_{n} est

|I_{n}| = \frac{2(4n + 1)!}{(n + 1)!(3n + 2)!}.  (2)

Preuve. Il s’agit de calculer la série génératrice

ϕ = ∑_{n≥1} |I_{n}|y^{n} = y + 3y^{2} + 13y^{3} + …

Pour cela, on introduit un paramètre supplémentaire. Si T est un arbre binaire plan dans Y_{n}, on note L(T) le nombre de segments le long du bord gauche de T. Par exemple L(Y) = 2, L( ) = 3 et L( ) = 2.

On considère alors la série génératrice raffinée

Φ = ∑_{n≥1} ∑_{[S,T]∈I_{n}} x^{L(T)}y^{n} = x^{2}y + (2x^{3} + x^{2})y^{2} + (5x^{4} + 5x^{3} + 3x^{2})y^{3} + …,

où la variable x tient compte compte du paramètre L pour le maximum T de l’intervalle [S, T]. Bien sûr, on retrouve ϕ en posant x = 1 dans Φ.

On montre de façon combinatoire dans les sections 3, 4 et 5 que Φ vérifie

Φ = x^{2}y (1 + Φ/x) (1 + (\frac{Φ − ϕ}{x − 1})) .

En isolant ϕ dans un membre, on obtient

ϕ = Φ + x − 1 + \frac{1}{y} (\frac{1}{x} − \frac{Φ + 1}{Φ + x}) ,

et comme ϕ ne dépend pas de x, le membre de droite est constant en la variable x. Il en résulte que Φ est déterminée par l’équation différentielle ordinaire

∂_{x}Φ = \frac{(x + Φ)^{2}(1/x^{2} − y) − 1 − Φ}{1 − x + y(x + Φ)^{2}}  (3)

et la condition initiale Φ = 0 en x = 0, car tout arbre binaire plan a au moins deux segments sur son bord gauche.

On en déduit que Φ vérifie l’équation algébrique suivante :

0 = x^{4}y^{4}Φ^{8} + (4 y^{3}x^{3} + 8 x^{5}y^{4} − y^{3}x^{4})Φ^{7}+

(−3 y^{2}x^{3} + 32 y^{3}x^{4} + 6 y^{2}x^{2} + 28 x^{6}y^{4} − 3 x^{5}y^{3})Φ^{6}+

(56 x^{7}y^{4} + 3 x^{6}y^{3} + (108 y^{3} − 3 y^{2})x^{5} − 39 x^{4}y^{2} + 40 y^{2}x^{3} − 3 x^{2}y + 4 xy)Φ^{5}+

(1 + 70 x^{8}y^{4} + 25 x^{7}y^{3} + (200 y^{3} − 9 y^{2})x^{6} − 146 x^{5}y^{2}+
(116 y^{2} + 21 y)x^{4} − 33 x^{3}y + 16 x^{2}y − x)Φ^{4}+
(56 x^{9}y^{4} + 45 x^{8}y^{3} + (−6 y^{2} + 220 y^{3})x^{7} + (−254 y^{2} − 3 y)x^{6}+
(184 y^{2} + 66 y)x^{5} − 77 x^{4}y + (−3 + 20 y)x^{3} + 3 x^{2})Φ^{3}+
(28 x^{10}y^{4} + 39 x^{9}y^{3} + (6 y^{2} + 144 y^{3})x^{8} + (−231 y^{2} − 5 y)x^{7}+
(166 y^{2} + 68 y)x^{6} + (−3 − 67 y)x^{5} + (3 + 8 y)x^{4})Φ^{2}+

(8 x^{11}y^{4} + 17 x^{10}y^{3} + (52 y^{3} + 9 y^{2})x^{9} + (−y − 107 y^{2})x^{8} + (−1 + 80 y^{2} + 22 y)x^{7}+

(1−20 y)x^{6})Φ+x^{12}y^{4}+3 x^{11}y^{3}+(3 y^{2}+8 y^{3})x^{10}+(y−20 y^{2})x^{9}+(16 y^{2}−y)x^{8}.(4)

En effet, la solution de cette équation algébrique vérifie l’équation différentielle (3) et la condition initiale.

On en déduit par spécialisation en x = 1 (et simplification par factorisation) que ϕ vérifie l’équation algébrique suivante :

y^{3}ϕ^{4} + (4 y + 3) y^{2}ϕ^{3} + (6 y^{2} + 17 y + 3) yϕ^{2}

+ (4 y^{3} + 25 y^{2} − 14 y + 1) ϕ + y (y^{2} + 11 y − 1) = 0. (5)

Pour en déduire les coefficients de ϕ, on peut utiliser comme suit les résultats de [3] dans le cas a = b = 1. En posant ϕ = τ(1 − τ − τ^{2}) dans (5), on obtient que τ vérifie τ = y(1 + τ)^{4}. On calcule alors les coefficients de ϕ par inversion de Lagrange. Ceci termine la démonstration du Théorème. □

3. Décomposition des intervalles

L’objet de cette section est l’obtention d’une description par récurrence sur n des intervalles.

Lemme 3.1. Il existe une unique décomposition maximale de chaque arbre binaire plan T sous la forme T_{1}/T_{2}/ … /T_{k}.

Preuve. Clair, par découpe de chaque segment le long du bord gauche. □

Fig. 2. Un intervalle dans Y_{9}

Un arbre binaire plan T est dit indécomposable si sa décomposition maximale a un seul terme. Les arbres binaires plans indécomposables sont ceux dont le bord gauche est formé de deux segments.

Étant donné un arbre binaire plan T, on définit une composition c(T) = (c_{1}, …, c_{k}) où c_{i} est le nombre de sommets internes de T_{i} dans la décomposition maximale de T. Par exemple, dans la figure 2, c(S) = (2, 7) et c(T) = (1, 1, 2, 4, 1).

Soient S et T deux arbres binaires plans, et soient (S_{i})_{i} et (T_{i})_{i} leurs décompositions maximales respectives.

Lemme 3.2. Si S ≤ T, alors ou bien la composition c(S) est strictement plus grossière que c(T) ou bien c(S) = c(T) et on a S_{i} ≤ T_{i} pour tout i.

Preuve. Il suffit de le montrer lorsque S et T sont reliés par une des relations élémentaires locales ( ≤ ) qui engendrent l’ordre dans les treillis de Tamari. Si cette relation est utilisée dans un des termes de la décomposition de T, la composition c ne change pas et l’ordre est respecté dans chaque terme, avec changement seulement dans un terme. Si la relation est utilisée à la liaison entre deux termes, le long du bord gauche, alors il y a fusion en un seul terme dans S des deux termes consécutifs de T impliqués, donc la composition devient strictement plus grossière et ne peut que le rester. □

Lemme 3.3. Soient S = S_{1}/ … /S_{k} et T = T_{1}/ … /T_{k} deux arbres binaires plans. On ne suppose pas que ces décompositions sont maximales. On suppose que |S_{i}| = |T_{i}| pour tout i. Alors S ≤ T si et seulement si S_{i} ≤ T_{i} pour tout i.

Preuve. Clairement S_{i} ≤ T_{i} pour tout i entraîne S ≤ T. Montrons la réciproque. Choisissons une chaîne de relations d’ordre élémentaires de S à T. Si une étape de cette chaîne se trouve le long du bord gauche à la liaison entre deux termes de la décomposition de T fixée, la composition associée deviendrait strictement plus grossière par le lemme précédent, donc la composition associée à S serait strictement plus grossière que celle de T, ce qui contredit l’hypothèse. Donc toutes les étapes de la chaîne se produisent à l’intérieur d’un des termes de la décomposition de T fixée et la relation d’ordre se factorise. □

Étant donné deux intervalles J et K, on peut définir un nouvel intervalle J/K avec min(J/K) = min(J)/ min(K) et max(J/K) = max(J)/ max(K).

Fig. 3. Un intervalle indécomposable

Proposition 3.4. Il existe une unique décomposition maximale de chaque intervalle I sous la forme I_{1}/I_{2}/ … /I_{k}.

Preuve. Soit S_{1}/ … /S_{k} la décomposition maximale du minimum S de I. Par le Lemme 3.2, la décomposition maximale du maximum T de I est plus fine que celle de S. Donc on peut en particulier décomposer le maximum T comme le minimum S. Alors, chaque terme de la décomposition de S est plus petit que chaque terme de T, par le Lemme 3.3.

Toute autre décomposition est un grossissement de celle-ci. En effet, elle est nécessairement un grossissement pour le minimum S. □

Dans l’exemple de la figure 2, la décomposition maximale a deux termes, ayant respectivement 2 et 7 sommets internes, de haut en bas.

On appelle intervalle indécomposable un intervalle dont la décomposition maximale a un seul terme. On remarque que les intervalles indécomposables sont exactement ceux dont le minimum est indécomposable.

4. Description des intervalles indécomposables

Étant donné un intervalle J et un segment s du bord gauche de son maximum max(J), on peut définir un nouvel intervalle Y∗_{s}J où max(Y∗_{s}J) est obtenu en rajoutant à gauche une arête sur l’arête s de max(J) et min(Y ∗_{s} J) est obtenu en rajoutant à gauche une arête sur l’arête racine de min(J). On peut aussi écrire min(Y ∗_{s} J) = Y\ min(J). Pour justifier que ceci est bien un intervalle, on a les relations

Y\ min(J) ≤ Y\ max(J) ≤ max(Y ∗_{s} J),

où la seconde relation est obtenue par une suite de relations élémentaires faisant remonter l’arête la plus à gauche le long du bord gauche de max(J), jusqu’à atteindre le segment s.

En particulier, l’élément min(Y ∗_{s} J) est indécomposable, donc l’intervalle Y ∗_{s} J est indécomposable. Voir la figure 3 pour une illustration de cette construction.

Proposition 4.1. Tout intervalle indécomposable I est ou bien [Y, Y] ou bien de la forme Y ∗_{s} J pour un certain intervalle J et un segment s du bord gauche de max(J), uniquement déterminés.

Preuve. Excluons le cas de l’intervalle [Y, Y].

Nécessairement le minimum de I est de la forme Y \S pour un certain arbre S. On peut aussi définir un arbre T en enlevant l’arête la plus à gauche dans le maximum de I.

Montrons que S ≤ T. Prenons une chaîne de relations élémentaires de min(I) à max(I). Dans cette chaîne, certaines étapes font intervenir l’arête la plus à gauche. Si on enlève ces étapes, on obtient une chaîne de relations élémentaires de S à T.

Donc on peut enlever l’arête la plus à gauche du minimum et du maximum de I pour obtenir un nouvel intervalle J = [S, T].

Pour reconstituer de manière unique I, il suffit de se donner J et le segment s sur le bord gauche de max(J) sur lequel se trouvait l’arête enlevée. □

5. Équation fonctionnelle

On déduit de la section précédente une équation fonctionnelle pour Φ.

Soit θ la série génératrice des nombres d’intervalles indécomposables :

θ = ∑_{n≥1}_{∑_{[S,T]∈I_{n}} ; indéc.}y^{n} = y + 2y^{2} + 8y^{3} + 41y^{4} + …,

et soit Θ la série génératrice raffinée correspondante :

Θ = ∑_{n≥1}_{∑_{[S,T]∈I_{n}} ; indéc.}x^{L(T)}y^{n} = x^{2}y + (x^{3} + x^{2})y^{2} + (2x^{4} + 3x^{3} + 3x^{2})y^{3} + …

Alors on a les relations suivantes. Par la décomposition unique d’un intervalle en intervalles indécomposables (Prop. 3.4), on a

Φ = Θ + Φ Θ/x.

Par la description des intervalles indécomposables (Prop. 4.1) et la définition de la fonction L, on a

Θ = x^{2}y + y Φ̃,

où Φ̃ est obtenu est remplaçant chaque x^{k} dans Φ par x^{2} + ⋯ + x^{k+1}. Ceci peut s’écrire

Θ = x^{2}y + x^{2}y (\frac{Φ − ϕ}{x − 1}) .

On a donc la relation fonctionnelle suivante :

Φ = x^{2}y (1 + Φ/x) (1 + (\frac{Φ − ϕ}{x − 1})) .  (6)

6. Séries formelles en arbres binaires plans

Cette section fait intervenir explicitement des notions algébriques plus sophistiquées : l’opérade dendriforme (due à Loday [6]) et le groupe de séries formelles associé. Les résultats de cette section ne sont pas utilisés dans le reste de l’article. On renvoie le lecteur aux articles [2, 7] pour la notion d’opérade et pour le groupe associé.

Soit Φ la série génératrice des nombres d’intervalles selon leur maximum :

Φ = ∑_{n≥1} ∑_{[S,T]∈I_{n}} T = Y + 2 + + …

et Θ la série génératrice similaire des intervalles indécomposables :

Θ = ∑_{n≥1}_{∑_{[S,T]∈I_{n}} ; [S,T] indéc.}T = Y + + + …

Par la décomposition unique en intervalles indécomposables (Prop. 3.4), on a

Φ = Θ + Φ/Θ.

Par la description des intervalles indécomposables (Prop. 4.1), on a

Θ = Y + Y ∗ Φ.

En effet, l’action du produit à gauche par Y est précisément de faire la somme sur les arbres obtenus en rajoutant un arête à gauche sur chaque segment du bord gauche.

On a obtenu la proposition ci-dessous.

Proposition 6.1. On a l’équation fonctionnelle suivante :

Φ = Y + Φ/Y + Y ∗ Φ + Φ/(Y ∗ Φ).  (7)

Cette relation caractérise la série Φ.

Ceci a pour conséquence les propositions ci-dessous.

Proposition 6.2. L’inverse de la série Y − dans le groupe G_{Dend} des séries formelles en arbres binaires plans est la série Y + ∘_{1} Φ.

Preuve. Par la définition de la loi de groupe de G_{Dend}, on doit montrer

(Y) ∘_{1} (Y + ∘_{1} Φ) − ( ∘_{2} (Y + ∘_{1} Φ)) ∘_{1} (Y + ∘_{1} Φ) = Y.

Par linéarité et comme Y est une unité pour les compositions ∘, ceci devient

Y + ∘_{1} Φ − − ∘_{1} ( ∘_{1} Φ) − ∘_{2} ( ∘_{1} Φ) − ( ∘_{2} ( ∘_{1} Φ)) ∘_{1} ( ∘_{1} Φ) = Y.

Soit encore

∘_{1} Φ = + ∘_{1} ( ∘_{1} Φ) + ∘_{2} ( ∘_{1} Φ) + ( ∘_{2} ( ∘_{1} Φ)) ∘_{1} ( ∘_{1} Φ). (8)

Comme on a

x ∘_{1} ( ∘_{1} y) = y/x,
x ∘_{1} (y ∘_{1} z) = (x ∘_{1} y) ∘_{1} z

et

∘_{2} ( ∘_{1} x) = ∘_{1} (Y ∗ x),

on peut réécrire l’équation (8) comme suit :

∘_{1} Φ = ∘_{1} (Y + Φ/Y + Y ∗ Φ + Φ/(Y ∗ Φ)).

Cette égalité résulte immédiatement de la relation fonctionnelle (7). □

Considérons maintenant la série Δ définie par

Δ = ∑_{T_{1},T_{2}}(−1)^{t_{1}+t_{2}}(t_{1} + 1) T_{1} ∨ T_{2} = Y − (2 + ) + …,  (9)

où les sommes portent cette fois sur les arbres binaires plans, y compris l’arbre trivial |, et où on note t_{i} le nombre de sommets internes de T_{i}.

Proposition 6.3. L’inverse de la série Φ dans le groupe G_{Dend} des séries formelles en arbres binaires plans est la série Δ.

Preuve. Il s’agit de montrer que ΦΔ = Y dans le groupe G_{Dend}. Par la relation (7), il suffit de calculer le produit

(Y + Φ/Y + Y ∗ Φ + Φ/(Y ∗ Φ)) Δ.

Comme le groupe G_{Dend} est contenu dans une algèbre associative et que la loi de groupe est linéaire à gauche, ceci vaut

YΔ + (Φ/Y)Δ + (Y ∗ Φ)Δ + (Φ/(Y ∗ Φ))Δ.

Posons H = ΦΔ. En utilisant la définition de la loi de groupe, on obtient la relation

H = Δ + ∑_{k}(H_{k}/Y) ∘_{k+1} Δ + (Y ∗ H) ∘_{1} Δ + ∑_{k}(H_{k}/(Y ∗ H)) ∘_{k+1} Δ, (10)

où on utilise une décomposition H = ∑_{k} H_{k} en composantes homogènes.

Cette relation caractérise uniquement la série H par récurrence. Il suffit donc de montrer que Y vérifie (10) pour pouvoir conclure que H = Y. Il faut donc calculer

Δ + ( ) ∘_{2} Δ + ( + ) ∘_{1} Δ + (Y/( + )) ∘_{2} Δ.

Ceci vaut

∑_{T_{1},T_{2}}(−1)^{t_{1}+t_{2}}(t_{1} + 1) T_{1} ∨ T_{2} + ∑_{T_{1},T_{2}}(−1)^{t_{1}+t_{2}}(t_{1} + 1) (Y ∗ T_{1}) ∨ T_{2}

+ ∑_{T_{1},T_{2}}(−1)^{t_{1}+t_{2}}(t_{1} + 1) (T_{1} ∨ T_{2})/Y + ∑_{T_{1},T_{2}}(−1)^{t_{1}+t_{2}}(t_{1} + 1) T_{1} ∨ (T_{2} ∗ Y)

+ ∑_{T_{1},T_{2}}(−1)^{t_{1}+t_{2}}(t_{1}+1) ((Y∗T_{1})∨T_{2})/Y+ ∑_{T_{1},T_{2}}(−1)^{t_{1}+t_{2}}(t_{1}+1) (Y∗T_{1})∨(T_{2}∗Y).

En utilisant le fait que

∑_{T ≠|} T = ∑_{S} Y ∗ S = ∑_{S} S ∗ Y,

on change les indices de sommation et on obtient

∑_{T_{1},T_{2}}(−1)^{t_{1}+t_{2}}(t_{1} + 1) T_{1} ∨ T_{2} − ∑_{T_{1}≠|,T_{2}}(−1)^{t_{1}+t_{2}}(t_{1}) T_{1} ∨ T_{2}

+ ∑_{T_{1},T_{2}}(−1)^{t_{1}+t_{2}}(t_{1} + 1) (T_{1} ∨ T_{2})/Y − ∑_{T_{1},T_{2}≠|}(−1)^{t_{1}+t_{2}}(t_{1} + 1) T_{1} ∨ T_{2}

− ∑_{T_{1}≠|,T_{2}}(−1)^{t_{1}+t_{2}}(t_{1}) (T_{1} ∨ T_{2})/Y + ∑_{T_{1}≠|,T_{2}≠|}(−1)^{t_{1}+t_{2}}(t_{1}) T_{1} ∨ T_{2}.

On simplifie les termes par paires (1 & 4), (2 & 6) et (3 & 5) :

∑_{T_{1}}(−1)^{t_{1}}(t_{1} + 1) T_{1}/Y − ∑_{T_{1}≠|}(−1)^{t_{1}}(t_{1}) T_{1}/Y + ∑_{T_{1},T_{2}}(−1)^{t_{1}+t_{2}}(T_{1} ∨ T_{2})/Y.

On simplifie à nouveau :

Y + ∑_{T_{1}≠|}(−1)^{t_{1}}(t_{1}) T_{1}/Y + ∑_{T_{1}≠|}(−1)^{t_{1}+1}T_{1}/Y.

Ceci donne Y, ce qui termine la démonstration. □

7. Découpage en intervalles nouveaux

Un arbre plan est un graphe fini plan connexe et simplement connexe, dont les sommets ont une valence différente de 2, muni d’un sommet de valence 1 distingué appelé la racine. Les autres sommets de valence 1 sont appelés les feuilles, les sommets de valence différente de 1 sont appelés sommets internes. On dessine les arbres plans avec les feuilles en haut et la racine en bas. Soit P_{n} l’ensemble des arbres plans à n + 1 feuilles. Les arbres binaires plans introduits précédemment sont en particulier des arbres plans.

Étant donnés un arbre plan T et, pour chaque sommet interne s de T de valence v(s), un intervalle I_{s} dans Y_{v(s)−2}, on peut définir un intervalle G(T, (I_{s})_{s}) en greffant les minimum (resp. les maximum) des intervalles I_{s} selon le schéma de greffe fourni par l’arbre plan T. La figure 2 montre cette construction pour un arbre plan à trois sommets et trois intervalles.

On dit qu’un intervalle est nouveau s’il ne peut pas s’écrire ainsi de façon non triviale, c’est-à-dire s’il n’est pas de la forme G(T, (I_{s})_{s}) avec T ayant au moins deux sommets internes.

Remarque : tout intervalle nouveau est indécomposable. En effet, un intervalle décomposable n’est évidemment pas nouveau.

On appelle découpage en nouveaux de I une écriture de I sous la forme G(T, (I_{s})_{s}) où tous les I_{s} sont nouveaux. L’existence d’une telle écriture est claire par la définition des intervalles nouveaux.

L’exemple de la figure 2 montre un intervalle et son découpage en trois intervalles nouveaux, ainsi que l’arbre plan associé à ce découpage.

Lemme 7.1. Soit K un intervalle et s un segment du bord gauche de max(K). Si Y ∗_{s} K est nouveau, alors tout découpage en nouveaux de K est de la forme K_{1}/ … /K_{k} où les K_{i} sont nouveaux.

Fig. 4. Découpage en nouveaux d’un intervalle indécomposable

Preuve. Par l’absurde. Supposons qu’il existe un découpage de K d’une autre forme. On peut donc en particulier décrire K par la greffe de K′′ sur une feuille (autre que la feuille gauche) de K′ pour certains intervalles K′ et K′′. Mais on en déduit alors un découpage de Y ∗_{s} K sous la forme d’une greffe de K′′ sur une feuille de Y ∗_{s} K′. Ceci contredit l’hypothèse. □

Proposition 7.2. Tout intervalle I a un unique découpage en nouveaux.

Preuve. Il reste à montrer l’unicité. On procède par récurrence sur n, en utilisant la description des intervalles obtenue précédemment.

Supposons d’abord que l’intervalle I est décomposable. On choisit un découpage de I en intervalles nouveaux. Ce découpage induit par regroupement une décomposition de I. Cette décomposition est nécessairement moins fine que la décomposition maximale.

Si elle est strictement moins fine, un des termes admet une décomposition non triviale. Le découpage en nouveaux de I induit un découpage en nouveaux de ce terme. L’intervalle situé à la racine de ce découpage en nouveaux est nécessairement aussi décomposable. Ce qui est absurde, car il est nouveau, donc indécomposable.

Par conséquent, la décomposition induite par le découpage est égale à la décomposition maximale. Chacun des termes de la décomposition hérite alors d’un découpage en nouveaux, ces découpages sont uniques par récurrence, donc le découpage en nouveaux de I est unique. Il s’obtient par recollement des découpages en nouveaux des termes de la décomposition maximale de I.

Supposons maintenant que l’intervalle I est indécomposable. On peut supposer que I n’est pas l’intervalle [Y, Y]. Il s’écrit donc Y ∗_{t} L pour certains t et L. On choisit un découpage de I en intervalles nouveaux. Soit J l’intervalle nouveau situé à la racine de ce découpage. Nécessairement, dans le découpage de I, il n’y a pas d’intervalle nouveau greffé sur la feuille de gauche de J, sinon I serait décomposable.

Comme J est nouveau, donc indécomposable, J s’écrit Y ∗_{s} K pour certains s, K, ou bien J = [Y, Y].

Supposons d’abord que J n’est pas [Y, Y]. Ce cas assez complexe est illustré par la figure 4. Par le Lemme 7.1, le découpage en nouveaux de K est de la forme K_{1}/ … /K_{k}. On en déduit par recollement de ce découpage de K avec la partie supérieure du découpage en nouveaux de I (les termes autres que J) un découpage en nouveaux de L. Ce découpage en nouveaux de L est unique par récurrence.

Donc le découpage en nouveaux de I est aussi unique et s’obtient à partir de celui de L par recollement des morceaux K_{1}, …, K_{k}, qui sont les morceaux situés le long du bord gauche entre le segment racine et le segment t.

Supposons maintenant que J est l’intervalle [Y, Y]. Alors I est de la forme Y\L pour un certain intervalle L, où l’opération \ sur les intervalles est définie de manière similaire à l’opération /. Prenons un autre découpage en nouveaux de I et soit J′ l’intervalle nouveau à la racine de ce découpage. Si J′ n’est pas l’intervalle trivial [Y, Y], on peut facilement construire un découpage de J′, ce qui est absurde.

Par conséquent, tout découpage en nouveaux de I induit un découpage en nouveaux de L, unique par récurrence. Donc le découpage en nouveaux de I est unique, obtenu par greffe du découpage en nouveaux de L sur la feuille droite de l’intervalle [Y, Y]. □

Remarque : une autre démonstration de la Proposition 7.2 peut sans doute être obtenue en utilisant la description géométrique du treillis de Tamari par le biais d’une forme linéaire sur le polytope de Stasheff.

8. Résultat auxiliaire

On va utiliser ici un troisième type d’arbres.

Un arbre enraciné est un graphe fini connexe et simplement connexe muni d’un sommet distingué appelé la racine. On dessine les arbres enracinés avec la racine en bas, en choisissant un plongement arbitraire dans le plan. Par convention, on oriente les arêtes de haut en bas.

Un automorphisme d’un arbre enraciné A est une permutation de ses sommets qui fixe la racine et préserve la relation d’adjacence. On note σ_{A} le cardinal du groupe d’automorphismes de A.

On considère l’espace vectoriel gradué PL ayant pour base en degré n les arbres enracinés à n sommets.

Cet espace PL est muni d’un produit bilinéaire non-associatif : si A et B sont des arbres enracinés, on pose

A ↶ B = ∑_{s∈A} A ↶_{s} B,  (11)

où la somme porte sur les sommets de A et A ↶_{s} B est l’arbre enraciné obtenu en ajoutant, dans l’union disjointe de A et de B, une arête entre la racine de B et le sommet s de A; la racine de A ↶_{s} B est la racine de A.

Soit ν une série formelle en une variable y. On associe à chaque arbre enraciné A une fonction ν_{A} définie récursivement comme suit. On écrit A comme la greffe d’arbres enracinés A_{1}, …, A_{k} (ensemble éventuellement vide) sur une racine et on pose

ν_{A} = (ν_{A_{1}} … ν_{A_{k}}) ν^{(k)},  (12)

où ν^{(k)} désigne la k-ième dérivée de ν par rapport à y. En particulier, on prend comme condition initiale ν_{•} = ν pour l’unique arbre enraciné à un sommet •. On a alors la propriété suivante.

Proposition 8.1. Pour tous les arbres enracinés A et B, on a

ν_{A↶B} = (ν_{A})′ν_{B}.  (13)

Preuve. Ceci résulte de la théorie des algèbres pré-Lie, voir [1]. □

Considérons maintenant la série

U = ∑_{A} \frac{1}{σ_{A}} A,

qu’on peut voir comme appartenant à un complété de PL. On décompose U selon le nombre de sommets dans les arbres :

U = ∑_{k≥0} \frac{U_{k+1}}{k!} ,

où le terme U_{k+1} est une combinaison linéaire d’arbres à k + 1 sommets.

La proposition ci-dessous montre que la série formelle en arbres enracinés U s’identifie, aux signes près, à l’idempotent introduit par Livernet [5] dans l’étude des algèbres pré-Lie.

Proposition 8.2. Les éléments U_{k} sont déterminés par la récurrence

U_{k+1} = ∑_{ℓ=1}^{k} \binom{k − 1}{ℓ − 1}U_{ℓ} ↶ U_{k+1−ℓ},  (14)

pour k ≥ 1 et la condition initiale que U_{1} est l’arbre enraciné à un sommet.

Preuve. Fixons un entier k positif ou nul et un entier ℓ strictement positif et inférieur ou égal à k.

Fixons un arbre enraciné A à k + 1 sommets, B un arbre enraciné à ℓ sommets, C un arbre enraciné à k + 1 − ℓ sommets,

Considérons l’ensemble E_{1}(A, B, C) des triplets (s, i, j) où s est un sommet de A distinct de la racine, i un isomorphisme entre C et le sous arbre de A de racine s et j un isomorphisme entre B et le complémentaire de ce sous-arbre de A (qui est aussi un sous-arbre).

Alors, cet ensemble E_{1}(A, B, C) est en bijection avec l’ensemble E_{2}(A, B, C) des couples (s, ε), où s est un sommet de B et ε un isomorphisme entre A et l’arbre B ↶_{s} C. La bijection utilise les isomorphismes pour identifier le sommet s de A à un sommet s de B. On déduit l’isomorphisme ε des deux isomorphismes i et j et réciproquement.

On a donc une égalité ∑_{E_{1}(A,B,C)} A = ∑_{E_{2}(A,B,C)} B ↶_{s} C.

De plus, les groupes d’automorphismes de B et C agissent librement sur E_{1}(A, B, C) et le groupe d’automorphisme de A agit librement sur E_{2}(A, B, C).

On obtient, avec la convention que le nombre de sommets de A est k + 1, celui de B est ℓ et celui de C est k + 1 − ℓ,

\frac{U_{k+1}}{k!} = ∑_{A} \frac{1}{σ_{A}} A = \frac{1}{k} ∑_{(A,s∈A)} \frac{1}{σ_{A}} A

= \frac{1}{k} ∑_{ℓ=1}^{k} ∑_{(A,B,C)} ∑_{(s,i,j)∈E_{1}(A,B,C)} \frac{1}{σ_{A}σ_{B}σ_{C}} A

= \frac{1}{k} ∑_{ℓ=1}^{k} ∑_{(A,B,C)} ∑_{(s,ε)∈E_{2}(A,B,C)} \frac{1}{σ_{A}σ_{B}σ_{C}} B ↶_{s} C

= \frac{1}{k} ∑_{ℓ=1}^{k} ∑_{(B,C,s∈B)} \frac{1}{σ_{B}σ_{C}} B ↶_{s} C

= \frac{1}{k} ∑_{ℓ=1}^{k} ∑_{(B,C)} \frac{1}{σ_{B}σ_{C}} B ↶ C

= \frac{1}{k} ∑_{ℓ=1}^{k} (∑_{B} \frac{1}{σ_{B}} B) ↶ (∑_{C} \frac{1}{σ_{C}} C)

= \frac{1}{k} ∑_{ℓ=1}^{k} \frac{U_{ℓ}}{(ℓ − 1)!} ↶ \frac{U_{k+1−ℓ}}{(k − ℓ)!}.

Ceci termine la démonstration de la proposition. □

9. Énumération des intervalles nouveaux

Si on compte les intervalles nouveaux dans les premiers treillis de Tamari, on trouve

1, 1, 3, 12, 56, 288, 1584, etc.,

pour n ≥ 1.

On est mené, par consultation de l’encyclopédie des suites d’entiers, à conjecturer le résultat suivant.

Théorème 9.1. Pour n ≥ 2, le nombre d’intervalles nouveaux dans le treillis de Tamari Y_{n} est

3 \frac{2^{n−2}(2n − 2)!}{(n − 1)!(n + 1)!}.  (15)

Fig. 5. Un arbre plan et l’arbre enraciné associé

La preuve est l’objet de la suite de cette section.

A chaque arbre plan T, on peut associer un arbre enraciné A(T) (la forme de T) de la façon suivante : les sommets de A(T) sont les sommets internes de T, les arêtes de A(T) sont les arêtes entre sommets internes de T, la racine de A(T) est le sommet interne de T qui est adjacent à la racine de T, voir la figure 5.

On introduit par commodité une version décalée de la série génératrice des intervalles :

ψ = yϕ = ∑_{n≥1} |I_{n}|y^{n+1} = y^{2} + 3y^{3} + 13y^{4} + …

et une série génératrice similaire pour les intervalles nouveaux :

ν = ∑_{n≥1}_{∑_{[S,T]∈I_{n}} ; nouveau}y^{n+1} = y^{2} + y^{3} + 3y^{4} + 12y^{5} + …

On peut déduire de l’équation algébrique (5) pour ϕ une équation algébrique pour ψ :

ψ^{4} + (4 y + 3) ψ^{3} + (6 y^{2} + 17 y + 3) ψ^{2}

+ (4 y^{3} + 25 y^{2} − 14 y + 1) ψ + y^{2} (y^{2} + 11 y − 1) = 0.

On va chercher à obtenir une équation algébrique pour ν.

Soit N_{n} le nombre d’intervalles nouveaux dans le treillis de Tamari Y_{n}. Le découpage unique d’un intervalle en intervalles nouveaux donne la relation suivante :

ψ = ∑_{n≥1} ∑_{T ∈P_{n}} N_{T} y^{n+1},  (16)

où P_{n} est l’ensemble des arbres plans à n + 1 feuilles et N_{T} est le produit sur l’ensemble des sommets internes s de T des N_{v(s)−2} (v(s) est la valence de s).

Dans cette somme, on regroupe les termes selon la valeur de A(T) :

ψ = ∑_{A} ∑_{n≥1}_{∑_{T ∈P_{n}} ; A(T)≃A}N_{T} y^{n+1},

où la somme externe porte sur les arbres enracinés.

Fixons un arbre enraciné A et soit I l’ensemble de ses sommets. Notons v_{i} le nombre d’arêtes entrantes du sommet i. La somme des v_{i} vaut |I| − 1, car chaque sommet sauf la racine a exactement une arête sortante.

On a besoin de décrire l’ensemble des arbres plans de forme isomorphe à A. On a un bijection entre d’une part l’ensemble F_{1}(A) formé par les paires (T, γ) où T est un arbre plan et γ un isomorphisme entre A(T) et A et d’autre part l’ensemble F_{2}(A) formé par les paires ((ℓ_{i})_{i}, (Z_{i})_{i}) où, pour chaque sommet i de A,

– ℓ_{i} est un nombre supérieur ou égal à 2,

– Z_{i} est une injection de l’ensemble des arêtes entrantes en i dans l’ensemble {1, …, ℓ_{i}}.

La bijection est la suivante : à la paire (T, γ), on associe les nombres ℓ_{i} tels que ℓ_{i} + 1 est la valence du sommet de T correspondant par γ au sommet i de A. Par γ, les arêtes entrantes en i dans A sont envoyées dans l’ensemble des arêtes entrantes du sommet correspondant de T, ce qui donne l’injection Z_{i} voulue.

Réciproquement, si on connaît les nombres ℓ_{i} et les injections Z_{i}, on peut aisément reconstruire un arbre plan T muni d’une bijection γ.

Le groupe des automorphismes de A agit librement sur F_{1}(A). La contribution de A à ψ est donc donnée par

\frac{1}{σ_{A}} ∑_{(ℓ_{i})_{i∈I}} ∏_{i∈I} (\frac{ℓ_{i}!}{(ℓ_{i} − v_{i})!}N_{ℓ_{i}−1}) y^{n+1},

où n est la somme des ℓ_{i} − 1. En répartissant la variable y, ceci vaut encore

\frac{1}{σ_{A}} ∑_{(ℓ_{i})_{i∈I}} ∏_{i∈I} (\frac{ℓ_{i}!}{(ℓ_{i} − v_{i})!}N_{ℓ_{i}−1}y^{ℓ_{i}−v_{i}}) ,

soit

\frac{1}{σ_{A}} ∏_{i∈I} (∑_{ℓ_{i}≥2} \frac{ℓ_{i}!}{(ℓ_{i} − v_{i})!}N_{ℓ_{i}−1}y^{ℓ_{i}−v_{i}}) .

On reconnaît dans les facteurs de cette formule les dérivées de ν, on obtient donc

\frac{1}{σ_{A}} ∏_{i∈I} ν^{(v_{i})}.

En utilisant la définition des fonctions ν_{A} comme dans la section 8, on peut donc écrire

ψ = ∑_{A} \frac{1}{σ_{A}} ν_{A} = ν + νν′ + ν(ν′)^{2} + \frac{1}{2}ν^{2}ν′′ + …,  (17)

où la somme porte sur les arbres enracinés,

Introduisons une suite de fonctions (α_{k})_{k≥1} de la variable y. Le terme initial est α_{1} = ν. Les termes suivants sont donnés pour k ≥ 1 par la récurrence

α_{k+1} = ∑_{ℓ=1}^{k} \binom{k − 1}{ℓ − 1}∂_{y}(α_{ℓ}) α_{k+1−ℓ}.

Alors, par les résultats de la section 8, l’équation (17) équivaut à

ψ = ∑_{k≥0} \frac{α_{k+1}}{k!} .

Introduisons la série génératrice double

Ψ = ∑_{k≥0} α_{k+1} \frac{z^{k}}{k!} .

La récurrence définissant les fonctions α_{k} se traduit en une équation aux dérivées partielles pour Ψ :

∂_{z}Ψ = (∂_{y}Ψ)Ψ,  (18)

avec la condition initiale

Ψ|_{z=1} = ψ.  (19)

Par conséquent, Ψ est solution de l´ équation algébrique

z^{4}Ψ^{4}+(4 zy − 8 + 11 z) z^{2}Ψ^{3}+(6 z^{2}y^{2} − z^{2} + 33 z^{2}y − 16 zy + 16 − 12 z) Ψ^{2}

+ (−8 y^{2} − 2 zy + 1 + 4 zy^{3} − 12 y + 33 zy^{2}) Ψ + 11 y^{3} + y^{4} − y^{2} = 0.

En effet, la solution de cette équation algébrique vérifie l’équation différentielle (18) et la condition initiale (19) en z = 1. En utilisant la spécialisation

Ψ|_{z=0} = α_{1} = ν,

on déduit de cette équation algébrique pour Ψ une équation algébrique pour ν :

y^{2} − 11 y^{3} − y^{4} + (−1 + 12 y + 8 y^{2}) ν − 16 ν^{2} = 0.

Donc

ν = \frac{1}{32} (−1 + 12 y + 8 y^{2} + (1 − 8 y)^{3/2}) .

On en déduit immédiatement la formule attendue pour les coefficients de ν. Ceci démontre le Théorème 9.1.

Références

[1] Frédéric Chapoton and Muriel Livernet. Pre-Lie algebras and the rooted trees operad. Internat. Math. Res. Notices, (8):395–408, 2001.

[2] Frédéric Chapoton. Rooted trees and an exponential-like series.

   arχiv:math.QA/0209104.

[3] Robert Cori and Gilles Schaeffer. Description trees and Tutte formulas. Theoret. Comput. Sci., 292(1):165–183, 2003. Selected papers in honor of Jean Berstel.

[4] Samuel Huang and Dov Tamari. Problems of associativity: A simple proof for the lattice property of systems ordered by a semi-associative law. J. Combinatorial Theory Ser. A, 13:7–13, 1972.

[5] Muriel Livernet. A rigidity theorem for preLie algebras. J. Pure Appl. Algebra 207(1), 1–18, 2006.

[6] Jean-Louis Loday. Dialgebras. In Dialgebras and related operads, volume 1763 of Lecture Notes in Math., pages 7–66. Springer, Berlin, 2001.

[7] Jean-Louis Loday. Arithmetree. J. Algebra, 258(1):275–309, 2002. Special issue in celebration of Claudio Procesi’s 60th birthday.

[8] Nathan Reading. Cambrian Lattices. Adv. Math., 205(2):313–353, 2006.

[9] N. J. A. Sloane. The On-Line Encyclopedia of Integer Sequences, 2006.

   www.research.att.com/~njas/sequences/.