ARBRES MINIMAX ET POLYNÔMES D’ANDRÉ

Dominique Foata et Guoniu Han

Abstract. On the set of minimax trees of a given order there can be defined two families of operations, the complements and the reverses. We study the actions of those operations and show that their orbits are enumerated by combinatorial objects previously introduced, such as the Hetyei-Reiner trees, the increasing trees and the André trees. Various generating functions for those trees by several statistics are also derived.

1. Introduction

Les arbres que nous appelons minimax dans cet article sont binaires (chaque sommet de l’arbre a deux, un ou zéro fils); topologiques (on distingue, pour chaque sommet, le fils à gauche et le fils à droite, s’ils existent); étiquetés (un étiquetage est une bijection de l’ensemble des sommets de l’arbre sur un ensemble fini totalement ordonné). Ils ont, de plus, la propriété suivante: (M) dans tout sous-arbre d’un arbre minimax, l’étiquette de la racine du

sous-arbre est, soit le minimum, soit le maximum des étiquettes des sommets du sous-arbre.

On note M_{n} l’ensemble des arbres minimax d’ordre n, c’est-à-dire des arbres minimax de n sommets, étiquetés 1, 2, …, n. Voir Fig. 1, où un arbre minimax d’ordre 10 est représenté.

[figure: •; •; •; •; •; •; •; •; •; •; 1; 10; 8; 9; 4; 2; 3; 6; 7; 5] Fig. 1

Les sommets sans fils d’un arbre sont appelés feuilles et les sommets ayant au moins un fils sont dits sommets intérieurs, simples s’ils n’ont qu’un fils et doubles s’ils ont deux fils. Dans un arbre minimax T, désignons par T_{g}(s) et T_{d}(s) les sous-arbres à gauche et à droite, incidents au sommet s de T. Notons également T (s) le sous-arbre de T, dont la racine est s, donc composé de cette racine et des deux sous-arbres T_{g}(s) et T_{d}(s) (voir Fig. 2). De façon évidente, T_{d}(s), T_{g}(s) et T (s) sont eux-mêmes des arbres minimax.

[figure: T_{d}(s); T_{g}(s); s; {; T (s); •] Fig. 2

On dit qu’un arbre minimax T est de Hetyei-Reiner s’il a en plus la propriété suivante: (HR) si s est un sommet intérieur et si son étiquette est minimum (resp.

maximum) dans le sous-arbre T (s), alors le sous-arbre à droite T_{d}(s) est non vide et contient le sommet d’étiquette maximum (resp. minimum) dans T (s).

Il faut noter que Hetyei et Reiner [HeRe98] appellent “minimax” ce que nous appelons “de Hetyei-Reiner”. Soit HR_{n} l’ensemble des arbres de Hetyei-Reiner d’ordre n.

On dit qu’un arbre minimax est croissant (CR) si les racines de tous ses sous-arbres ont des étiquettes minimum. Il en résulte que la suite des étiquettes des sommets situés sur le chemin conduisant de la racine d’un arbre croissant à l’une des feuilles est toujours (strictement) croissante. Soit C_{n} l’ensemble des arbres minimax croissants d’ordre n.

Enfin, on dit qu’un arbre minimax est un arbre d’André, s’il a la propriété suivante: (A) pour tout sommet intérieur s, le sous-arbre à droite T_{d}(s) est non vide

et contient le sommet d’étiquette maximum dans T (s). On vérifie immédiatement qu’un arbre minimax est d’André s’il est à la fois croissant et d’Hetyei-Reiner. Notons A_{n} = C_{n} ∩ HR_{n} l’ensemble des arbres d’André d’ordre n.

On sait dénombrer ces quatre familles d’arbres. D’abord, comme démontré dans le paragraphe 3, la fonction génératrice exponentielle des nombres m_{n} := #M_{n} est donnée par:

(1.1) \frac{\sqrt{2}}{2} \frac{1 + (3 − 2\sqrt{2}) e^{2\sqrt{2} u}}{1 − (3 − 2\sqrt{2}) e^{2\sqrt{2} u}} = ∑_{n≥0} \frac{u^{n}}{n!} m_{n}

= 1 + u + \frac{u^{2}}{2!} 4 + \frac{u^{3}}{3!} 20 + \frac{u^{4}}{4!} 128 + \frac{u^{5}}{5!} 1024 + \frac{u^{6}}{6!} 9856 + ⋯

Ensuite, les arbres d’Hetyei-Reiner et les arbres croissants sont en bijection avec les permutations, soit

(1.2)  # HR_{n} = n! et # C_{n} = n!,

un résultat établi par Hetyei-Reiner [HeRe98] pour les arbres de même nom et un résultat classique pour les arbres croissants (voir, par exemple, [FoSch71]). Nous rappelons à la fin du paragraphe 2 comment établir géométriquement ces deux faits.

Rappelons, enfin, que les nombres tangents et sécants E_{n} sont définis comme les coefficients du développement de Taylor

sec u + tan u = 1 + ∑_{n≥1} \frac{u^{n}}{n!} E_{n} = 1 + u + \frac{u^{2}}{2!} + \frac{u^{3}}{3!} 2 + \frac{u^{4}}{4!} 5 + \frac{u^{5}}{5!} 16 + ⋯

et que les arbres d’André sont justement dénombrés par ces nombres classiques

(1.3)  # A_{n} = E_{n},

un résultat établi dans [FoSch71]. Le but principal de cet article est de démontrer le théorème suivant.

Théorème 1.1. On peut construire deux groupes G_{n} et R_{n}, agissant sur l’ensemble M_{n} des arbres minimax d’ordre n, ayant la propriété que chaque G_{n}-orbite d’un arbre minimax T ∈ M_{n} contient exactement un seul arbre croissant c T ∈ C_{n} et chaque R_{n}-orbite un seul arbre de Hetyei-Reiner r T ∈ HR_{n}. De plus, les surjections c et r ainsi définies ont la propriété que le diagramme suivant est commutatif:

(1.4)  \begin{matrix}M_{n} & ⟶^{c} & C_{n} \\ ↓^{r} & & ↓^{r} \\ HR_{n} & ⟶^{c} & A_{n} \end{matrix}

Enfin, si T est un arbre minimax ayant k feuilles, il y a exactement 2^{n−k} arbres dans sa G_{n}-orbite (resp. sa R_{n}-orbite) et ils ont également tous k feuilles.

Pour comparer notre contribution à celles apportées par les travaux antérieurs, disons que la partie concernant la surjection r : C_{n} → A_{n} est due à Foata-Strehl [FoSt74] et celle concernant la surjection c : HR_{n} → A_{n} est due à Hetyei-Reiner [HeRe98]. Il nous a paru essentiel de rassembler ces résultats dans un même modèle et donc d’imaginer une classe d’arbres qui englobe à la fois les arbres croissants et ceux d’Hetyei-Reiner, sur lesquels on peut prolonger l’action des groupes jusque là limitée aux seuls arbres croissants ou d’Hetyei-Reiner. D’où l’introduction des arbres minimax.

Comme décrit dans le paragraphe 3, on peut introduire deux statistiques “hr” et “cr” sur M_{n} qui ont la propriété que hr T = 0 (resp. cr T = 0) si T est de Hetyei-Reiner (resp. croissant) et donc hr T = cr T = 0 si T est d’André. Soit m_{n,k}(p, q) le polynôme générateur de M_{n,k} par la statistique bivariée (hr, cr). A l’aide d’une construction combinatoire appropriée, on établit au paragraphe 3 une récurrence pour les polynômes m_{n,k}(p, q). On en déduit, d’abord, une expression pour la fonction génératrice exponentielle des arbres minimax par la statistique trivariée (nombre de feuilles, hr, cr) (voir identité (3.6)), ensuite, celle des nombres m_{n} = # M_{n} annoncée en (1.1).

Les opérations-compléments et les opérations-retournements sont étudiés dans les paragraphes 4 et 5. On établit, en particulier, leur propriétés de commutativité. Dans le paragraphe 6, à l’aide de ces opérations, on construit les deux surjections c et r du diagramme (1.4), terminant ainsi la démonstration du Théorème 1.1.

Notons d_{n,k} le cardinal de A_{n,k}, ou encore le nombre d’arbres d’André ayant k feuilles. Les polynômes D_{n}(t) = ∑_{k} d_{n,k}t^{k} (n ≥ 0), appelés polynômes d’André, ont été introduits et étudiés dans [FoSch73]. Dans le paragraphe 7, nous donnons deux nouvelles méthodes pour obtenir leur fonction génératrice exponentielle. Enfin, dans le paragraphe 8, nous indiquons comment définir d’autres opérations-compléments, comme celle introduite par Hetyei et Reiner [HeRe98], et d’autres opérations-retourne-ments, qui conduisent à des résultats analogues.

Le présent article s’inscrit dans ce programme qui se propose de trouver des interprétations combinatoires aux suites de nombres classiques, ici les nombres d’Euler, afin, notamment, de pouvoir obtenir des q-analogues utiles de ceux-ci. La première interprétation des nombres d’Euler remonte à André [An79, An81] en termes de permutations alternantes. On sait que ce modèle permet un passage élégant au q-calcul (voir [AnGe78, Fo81]), mais ne permet pas, a priori, d’autres extensions intéressantes.

Dans [FoSch71, FoSch73], on a reconsidéré l’équation différentielle: D′′′ = D′D′′, satisfaite par la fonction sec u + tan u, mais en s’imposant d’autres conditions intiales: D(0) = 0, D′(0) = 1, D′′(0) = t. En cherchant des solutions de la forme D = ∑_{n≥1}(u^{n}/n!) D_{n−1}, on a pu faire apparaître les coefficients D_{n} comme des polynômes D_{n} = D_{n}(t) (n ≥ 0), qui sont précisément les polynômes d’André, dont on a parlé plus haut. De plus, ceux-ci sont apparus très naturellement comme les polynômes générateurs d’objets combinatoires, qui ne sont plus les permutations alternantes, mais les permutations dites d’André par la statistique “nombres de pics.”

Plus tard, Foata et Strehl [FoSt74, FoSt76] ont fait apparaître ces permutations d’André comme des systèmes de représentants d’orbites de groupes agissant sur l’ensemble de toutes les permutations. Ils ont montré que l’action de ces groupes est mieux perçue géométriquement, si on les fait agir non pas sur les permutations, mais sur des arbres binaires.

Les permutations et les polynômes d’André ont trouvé une nouvelle application dans l’étude de la variation dite cd de certains ensembles partiellement ordonnés (“posets”), une étude entreprise par Purtill [Pu93], Stanley [St94], qui a pu, en particulier, faire usage des polynômes d’André non commutatifs, par Sundaram [Su94] et plus récemment par Hetyei [He96].

2. Conventions et notations

Pour fixer les idées, on considère que chaque arbre binaire T est dessiné dans le plan euclidien: la racine est d’ordonnée 0, les fils de la racine sont d’ordonnée 1, les petits-fils d’ordonnée 2, etc. On convient que tous les sommets dans l’arbre à gauche T_{g}(s) (resp. dans l’arbre à droite T_{d}(s)) ont une abscisse inférieure (resp. supérieure) à celle de s. En fait, on convient que la racine de l’arbre est à l’origine (0, 0), le fils à gauche de la racine en (−1, 1) et le fils à droite en (1, 1), les petits-fils respectivement en (−3/2, 2), (−1/2, 2), (1/2, 2), (3/2, 2), les arrière-petits-fils respectivement en (−7/4, 3), (−5/4, 3), …, (7/4, 3), etc. Avec cette convention, tous les sommets de l’arbre ont des abscisses distinctes.

Si l’arbre binaire T a n sommets, on ordonne ces n sommets de la façon suivante: la racine est le plus petit sommet, puis vient le fils à gauche de la racine, puis le fils à droite, puis le fils à gauche du fils à gauche, etc. On note <_{T} cet ordre total.

[figure: 1; 4; 8; 9; 10; 2; 3; 6; 5; 7; 1; 4; 8; 9; 10; 2; 3; 6; 5; 7; T_{1} =; π(T_{1}) =; 1; 10; 4; 9; 8; 2; 3; 7; 6; 5; 1; 10; 4; 9; 8; 2; 3; 7; 6; 5; T_{2} =; π(T_{2}) =] Fig. 3

Disposons dans le plan euclidien les sommets d’un arbre minimax comme indiqué précédemment et considérons la projection orthogonale π sur un axe horizontal des étiquettes de cet arbre. Alors π envoie bijectivement l’ensemble des arbres croissants (resp. de Hetyei-Reiner) ayant n sommets sur le groupe des permutations de la suite 1, 2, …, n. Voir les démonstrations dans [FoSch71, HeRe98]. Ceci montre, en particulier, que card C_{n} = card HR_{n} = n! Dans la Fig. 3, on donne l’exemple d’un arbre croissant T_{1} et d’un arbre d’Hetyei-Reiner T_{2} avec leurs projections.

On appelle permutation d’André l’image par la projection π d’un arbre d’André. On trouve dans [FoSch73] une autre définition des permutations d’André. On note M_{n,k} (resp. C_{n,k}, resp. HR_{n,k}, resp. A_{n,k}) le sous-ensemble de M_{n} (resp. C_{n}, resp. HR_{n}, resp. A_{n}) formé par tous les arbres qui ont k feuilles.

3. Dénombrement des arbres minimax

Dans un arbre minimax T, soit s un sommet d’étiquette a. On note T {a} (resp. T_{g}{a}, resp. T_{g}{a}) l’ensemble de toutes les étiquettes apparaissant dans le sous-arbre T (s) (resp. T_{g}(s), resp. T_{d}(s)). Si l’étiquette a d’un sommet intérieur s est minimum (resp. maximum) dans le sousarbre T (s), on dit que le sommet s est de première espèce, si le sous-arbre à droite T_{d}(s) est non vide et contient le sommet d’étiquette max T {a} (resp. min T {a}). Un sommet intérieur, qui n’est pas de première espèce, est dit de seconde espèce. Notons qu’un sommet intérieur simple s est de première espèce si et seulement si T_{g}(s) est vide et T_{d}(s) non vide.

Par exemple, dans l’arbre minimax représenté dans Fig. 1, le sommet 3 est de première espèce (l’étiquette maximum “7” se trouve à droite) et le sommet 10 est de seconde espèce (l’étiquette minimum “4” se trouve à gauche).

On désigne par hr(T) le nombre de sommets intérieurs de seconde espèce d’un arbre minimax T. Un arbre de Hetyei-Reiner T est encore un arbre satisfaisant hr(T) = 0. Notons cr(T) le nombre de sommets intérieurs s d’un arbre minimax T qui sont d’étiquette maximum, (c’està-dire dont l’étiquette est maximum dans le sous-arbre T (s) de racine s) de sorte qu’un arbre croissant T est un arbre satisfaisant cr(T) = 0 et qu’un arbre d’André est tel que hr(T) = cr(T) = 0. Désignons par

(3.1)  m_{n,k}(p, q) := ∑_{T ∈M_{n,k}} p^{hr(T)} q^{cr(T)},

la fonction génératrice des arbres minimax d’ordre n ayant k feuilles par la statistique bivariée (hr, cr).

Proposition 3.1. Les polynômes m_{n,k}(p, q) satisfont la récurrence:

m_{1,1}(p, q) = 1, m_{n,k}(p, q) = 0 (k < 0 ou n + 1 < 2k); (3.2) m_{n+1,k}(p, q) = (1 + p)(1 + q) k m_{n,k}(p, q) + (n + 3 − 2k)m_{n,k−1}(p, q)

(pour 1 ≤ k ≤ ⌈(n + 1)/2⌉ et n ≥ 1).

Démonstration. Si un arbre minimax d’ordre n a k feuilles, le nombre de ses sommets intérieurs doubles est forcément égal à (k −1) et le nombre de ses sommets intérieurs simples est donc égal à n − k − (k − 1) = n − 2k + 1. Par conséquent, le facteur n + 3 − 2k = n − (k − 1) − (k − 2), qui intervient dans (3.1), est le nombre de sommets intérieurs simples d’un arbre minimax d’ordre n ayant (k − 1) feuilles.

Partons donc d’un tel arbre T et considérons l’un des (n + 3 − 2k) sommets intérieurs simples s de cet arbre. Soit b son étiquette. Dans le chemin unique qui mène de la racine de l’arbre au sommet s, il y a des sommets s_{i} qui sont d’étiquette maximum et des sommets qui sont d’étiquette minimum. Désignons par (s_{1}, s_{2}, …, s_{m}) la suite des sommets intérieurs d’étiquette maximum, lorsqu’on parcourt le chemin de la racine vers s et notons (a_{1}, a_{2}, …, a_{m}) la suite (forcément décroissante) de leurs étiquettes. Notons encore s′ l’unique fils de s, d’étiquette b′.

Dans une première étape, on remplace les étiquettes a_{1}, a_{2}, …, a_{m−1}, a_{m} par (n + 1), a_{1}, …, a_{m−2}, a_{m−1}, respectivement, puis on adjoint une feuille étiquetée a_{m} au sommet s, ce qui donne un arbre minimax T′ d’ordre (n + 1) ayant k feuilles. Dans ce dernier arbre, la feuille étiquetée a_{m} et le sous-arbre T (s′) forment les sous-arbres incidents au sommet s. Voir Fig. 4, où l’on a considéré quatre cas, suivant que l’étiquette b de s est minimum (simple trait, cas (1) et (3)) ou maximum (gros point, cas (2) et (4)), et suivant que l’arbre T (s′) est le sousarbre à droite (cas (1) et (2)) ou le sous-arbre à gauche (cas (3) et (4)) du sommet s. Les étiquettes sont écrites entre crochets et l’ascendance du sommet s (la partie basse) est représentée par un trait vertical.

Si l’étiquette b de s est minimum (cas (1) et (3)), dans une seconde étape, on échange les positions des sous-arbres T (s′) et de la feuille étiquetée a_{m}. Soit T′′ l’arbre obtenu. Si l’étiquette b est maximum, on pose simplement: T′′ := T′. Par ce procédé, on obtient un arbre minimax T′′ d’ordre (n + 1), ayant k feuilles. On observe que dans le passage de T à T′′, le nombre de sommets intérieurs n’est pas modifié (on a simplement ajouté une feuille), ni leur espèce et que le nombre de sommets intérieurs d’étiquette maximum n’a pas changé. Ainsi hr(T′′) = hr(T) et cr(T′′) = cr(T).

Par exemple, dans le cas (1) (resp. cas (3)), le sommet s est de première (resp. de seconde) espèce dans T et reste de première (resp. de seconde) espèce dans T′′.

Soit maintenant T un arbre minimax d’ordre n ayant k feuilles et soit s l’une de ses k feuilles, étiquetée b. On désigne, de même, par (s_{1}, s_{2}, …, s_{m}) la suite des sommets intérieurs d’étiquette maximum, lorsqu’on parcourt le chemin de la racine vers la feuille et par (a_{1}, a_{2}, …, a_{m}) la suite de leurs étiquettes. On construit alors quatre arbres minimax d’ordre (n+1) ayant k feuilles, T_{1}, T_{2}, T_{3}, T_{4}, en remplaçant tout d’abord les étiquettes a_{1}, a_{2}, …, a_{m−1}, a_{m} par (n + 1), a_{1}, …, a_{m−2}, a_{m−1}, respectivement.

[figure: ×; ×; [a_{m}]; [b]; [b′]; s; s′; •; ↦; •; [a_{m}]; ×; ×; [a_{m−1}]; [b]; [b′]; s; s′; •; ↦; •; [b′]; ×; •; [a_{m−1}]; [b]; [a_{m}]; s; s′; •]

cas (1)

[figure: •; ×; [a_{m−1}]; [b] = [a_{m}]; [b′]; s; s′; •; ↦; •; [a_{m}]; •; ×; [a_{m−2}]; [a_{m−1}]; [b′]; s; s′; •]

cas (2)

[figure: ×; ×; [a_{m}]; [b]; [b′]; s; s′; •; ↦; •; [a_{m}]; ×; ×; [a_{m−1}]; [b]; [b′]; s; s′; •; ↦; •; [b′]; ×; •; [a_{m−1}]; [b]; [a_{m}]; s; s′; •]

cas (3)

[figure: •; ×; [a_{m−1}]; [b] = [a_{m}]; [b′]; s; s′; •; ↦; •; [a_{m}]; •; ×; [a_{m−2}]; [a_{m−1}]; [b′]; s; s′; •]

cas (4)

(A gauche, l’arbre T ; à l’extrême droite, la partie correspondante dans T′′.)

(L’ascendance du sommet s est représentée par un trait vertical.) Fig. 4

Ensuite, on transforme la feuille s en un sommet intérieur simple, ayant soit un fils à gauche s_{g}, soit un fils à droite s_{d} et l’on donne au couple de sommets (s, s_{g}) (resp. au couple (s, s_{d})) ou bien le couple d’étiquettes (b, a_{m}), ou bien le couple (a_{m}, b). On obtient bien ainsi les quatre arbres souhaités. On observe qu’en transformant de la sorte la feuille s en un somme intérieur simple, le monôme p^{hr(T)}q^{cr(T)} est transformé en p^{hr(T)}q^{cr(T)}(p + pq + 1 + q) = (1 + p)(1 + q)p^{hr(T)}q^{cr(T)}, comme indiqué dans la Fig. 5.

• −[a_{m}] s [b]

[figure: •; [a_{m−1}]; −; s; [b]; •; [a_{m}]; s_{g}; T_{1}; p; •; [a_{m−1}]; −; s; [a_{m}]; •; [b]; s_{g}; T_{2}; pq; •; [a_{m−1}]; s; −; [b]; •; [a_{m}]; s_{d}; T_{3}; 1; •; [a_{m−1}]; s; −; [a_{m}]; •; [b]; s_{d}; T_{4}; q]

Fig. 5

La construction ainsi décrite est parfaitement réversible. Partons d’un arbre minimax T d’ordre (n + 1) ayant k feuilles ; on pose a_{1} := n + 1 ; et pour chaque i ≥ 2 on définit a_{i} := max(T [a_{i−1}] \ {a_{i−1}}), si ce dernier ensemble est non vide. Soit m ≥ 1 le plus petit entier tel que T [a_{m}]\{a_{m}} est vide. On construit ainsi une suite strictement décroissante d’étiquettes (a_{1} = n + 1 > a_{2} > ⋯ > a_{m}). Soit (s_{1}, s_{2}, …, s_{m}) la suite des sommets de T ayant ces étiquettes. Alors s_{m} est forcément une feuille de l’arbre. Soit s le sommet intérieur auquel elle est incidente. Selon que s est double ou simple, on applique, en sens inverse, l’algorithme décrit dans la Fig. 4 ou dans la Fig. 5.

Dans [FoSch73], on a noté d_{n,k} le cardinal de A_{n,k}, à savoir le nombre d’arbres d’André d’ordre n ayant k feuilles et on a démontré que ces nombres satisfaisaient la récurrence:

(3.3) d_{1,1} = 1, d_{n,k} = 0 (k < 0 ou n + 1 < 2k); d_{n+1,k} = k d_{n,k} + (n + 3 − 2k)d_{n,k−1} (1 ≤ k ≤ ⌈(n + 1)/2⌉ et n ≥ 1).

Dans la table de la Fig. 6, apparaissent les premières valeurs de ces nombres. La comparaison de cette récurrence avec (3.2) fournit immédiatement la relation:

(3.4)  m_{n,k}(p, q) = (1 + p)^{n−k}(1 + q)^{n−k} d_{n,k}.

Notons que ∑_{k} d_{n,k} = E_{n}, le nombre tangent ou sécant, selon que n est impair ou pair, comme déjà établi dans [FoSch73]. La somme ∑_{k} m_{n,k}(1, 1) donne le nombre d’arbres minimax m_{n} d’ordre n; les premières valeurs apparaissent dans la Fig. 7.

k=  1 2  3  4  E_{n}
n=1  1  1
2  1  1
3  1 1  2
4  1 4  5
5  1 11 4  16
6  1 26 34  61
7  1 57 180 34  272
8  1 120 768 496  1385
Table des d_{n,k}

Fig. 6

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ m_{n} & 1 & 4 & 20 & 128 & 1024 & 9856 & 110720 & 1421312 \end{matrix}

Table des m_{n}

Fig. 7

Le polynôme D_{n}(t) := ∑_{k} d_{n,k}t^{k} est le polynôme générateur des arbres d’André d’ordre n par nombre de feuilles, ou, en utilisant la projection π décrite à la fin du paragraphe 2, le polynôme générateur des permutations d’André d’ordre n par nombre de pics. On appelle ces polynômes les polynômes d’André. Dans [FoSch73], formule (2.14), on trouve l’expression de la fonction génératrice exponentielle de ces polynômes, à savoir:

(3.5)  ∑_{n≥0} D_{n}(t)\frac{u^{n}}{n!} = r(t)\frac{1 + w(t)e^{r(t)u}}{1 − w(t)e^{r(t)u}} ,

où r(t) := (1 − 2t)^{1/2}, w(t) := (1 − r)/(1 + r). Deux autres nouvelles démonstrations de ce résultat sont proposées dans le dernier paragraphe de cet article.

Soit f(T) le nombre de feuilles d’un arbre minimax. Si l’on désigne par M_{n}(t, p, q) la fonction génératrice des arbres minimax d’ordre n par la statistique trivariée (f, hr, cr), on déduit de (3.4):

M_{n}(t, p, q) = ∑_{k} t^{k} m_{n,k}(p, q)

= ∑_{k} t^{k} (1 + p)^{n−k}(1 + q)^{n−k} d_{n,k}

= (1 + p)^{n}(1 + q)^{n} ∑_{k} d_{n,k}(t/(1 + p)(1 + q))^{k}

= (1 + p)^{n}(1 + q)^{n} D_{n}(t/(1 + p)(1 + q)).

Posons t′ := t/((1 + p)(1 + q)) ; de (3.5) on en déduit l’identité:

(3.6)  ∑_{n≥0} M_{n}(t, p, q)\frac{u^{n}}{n!} = r(t′)\frac{1 + w(t′)e^{r(t′)u(1+p)(1+q)}}{1 − w(t′)e^{r(t′)u(1+p)(1+q)}} .

Dans l’identité (3.6), posons t := 1, p := 1 et q := 1. Alors M_{n}(1, 1, 1) =

m_{n} et le membre de droite prend la forme \frac{\sqrt{2}}{2} \frac{1 + (3 − 2\sqrt{2}) e^{2\sqrt{2} u}}{1 − (3 − 2\sqrt{2}) e^{2\sqrt{2} u}}, ce qui

établit la formule (1.1), qui donne la fonction génératrice exponentielle des arbres minimax.

4. Les opérations-compléments

L’une des opérations classiques du groupe symétique S_{m} est l’opération-complément. C’est une involution qui envoie chaque entier i (1 ≤ i ≤ m) sur l’entier c_{m}(i) = m + 1 − i. A l’aide de celle-ci, on peut aussi définir une opération-complément sur l’ensemble des arbres minimax. Les sommets de l’arbre restent invariants, seules certaines de leurs étiquettes sont modifiées.

Soit s un sommet intérieur d’un arbre minimax T ayant n sommets, de sorte que l’un au moins des sous-arbres T_{g}(s), T_{d}(s) est non vide. Soient a l’étiquette de s et a_{1} < a_{2} < ⋯ < a_{m} la suite croissante des étiquettes du sous-arbre T (s) de racine s. Par conséquent, a est égal à a_{1} ou à a_{m}. On note c(s) T l’arbre obtenu de T en ne modifiant pas les étiquettes des sommets dans T \ T (s), mais en changeant chaque étiquette a_{i} en a_{c_{m}(i)} = a_{m+1−i}. Si s est une feuille de T, on pose c(s) T := T.

Il est évident que l’on a

(4.1)  c(s)c(s) T = T

et que l’arbre c(s) T est lui-même minimax. Comme le sous-arbre T \T (s) n’est pas modifié par c(s), on peut écrire symboliquement:

(4.2)  c(s)T := (T \ T (s)) + c(s)T (s).

Dans l’exemple de la Fig. 1, soit s le fils à droite de la racine de l’arbre (donc sis en (1, 1) avec la convention prise pour la position des sommets) dont l’étiquette est 10. Alors c(s)T est l’arbre représenté dans la Fig. 8.

[figure: •; •; •; •; •; •; •; •; •; •; 1; 4; 9; 8; 10; 2; 3; 6; 7; 5] Fig. 8

Proposition 4.1. Supposons donnés les deux sommets intérieurs s et s′ d’un arbre minimax T. Alors

(4.3)  c(s)c(s′) T = c(s′)c(s) T.

Démonstration. Si les sous-arbres T (s) et T (s′) sont disjoints, la relation (4.3) est évidente. Si les sous-arbres ne sont pas disjoints, alors forcément l’un d’eux est un sous-arbre de l’autre. Convenons, par exemple, que T (s′) est un sous-arbre de T (s) et que dans T les étiquettes de T (s) sont a_{1} < a_{2} < ⋯ < a_{m}. Alors les étiquettes de T (s′) sont a_{i(1)} < ⋯ < a_{i(m′)}, où (i(1), …, i(m′)) est une sous-suite de (1, 2, …, m). Les sommets de T sont de trois sortes : les sommets de T (s′), ceux de T (s) \ T (s′) et ceux de T \ T (s), comme indiqué schématiquement dans la Fig. 9.

[figure: T (s′); s; s′; {; T (s); •; •; ⟵ T \ T (s); T (s) \ T (s′); ; }; T] Fig. 9

Les étiquettes des sommets de T \ T (s) ne sont jamais modifiées lorsqu’on applique les opérations c(s), c(s′). Lorsqu’on applique c(s′) à T, seul l’ordre des étiquettes des sommets de T (s′) est renversé: l’étiquette a_{i(k)} est remplacée par a_{i(m′+1−k)}. Si on applique ensuite c(s) à l’arbre transformé c(s′) T, alors a_{i(m′+1−k)} est changée en a_{m+1−i(m′+1−k)} et l’étiquette a_{j} de T (s) \ T (s′) en a_{m+1−j}.

Par ailleurs, si on applique c(s) à T, la suite des étiquettes a_{i(1)} < ⋯ < a_{i(m′)} de T (s′) est changée, terme à terme, en la suite des étiquettes a_{m+1−i(1)} > ⋯ > a_{m+1−i(m′)} du sous-arbre (c(s) T )(s′). Chaque étiquette a_{j} de T (s) \ T (s′) est changée en a_{m+1−j} et n’est plus changée par l’application ultérieure de c(s′).

En revanche, quand on applique c(s′) à ce sous-arbre (c(s) T )(s′), la suite a_{m+1−i(1)} > ⋯ > a_{m+1−i(m′)} est changée, terme à terme, en a_{m+1−i(m′)} > ⋯ > a_{m+1−i(1)}.

Soit s un sommet intérieur d’un arbre minimax T; l’involution c(s) change l’étiquette maximum (resp. minimum) du sommet s en une étiquette minimum (resp. maximum). On dit qu’elle change la valeur extremum de son étiquette. L’involution c(s) change également la valeur extremum de l’étiquette de tout sommet intérieur s′ ∈ T (s). Notons s_{g} et s_{d} les fils à gauche et à droite (s’ils existent) du sommet s et posons:

(4.4)  d(s) := \{ \begin{matrix}c(s)c(s_{g})c(s_{d}), & si s a deux fils ; \\ c(s)c(s_{g}), & si s a un seul fils à gauche ; \\ c(s)c(s_{d}), & si s a un seul fils à droite. \end{matrix}

Alors d(s) change la valeur extremum de l’étiquette du sommet s, mais conserve le caractère extremum des autres étiquettes dans l’arbre T.

Soit s_{1}, s_{2}, …, s_{n} la suite croissante des n sommets d’un arbre minimax T d’ordre n suivant l’ordre <_{T}. Pour tout i = 1, 2, …, n, on pose c_{i} T := c(s_{i}) T. Alors c_{i} est une involution agissant sur l’ensemble M_{n} des arbres minimax d’ordre n. Soit G_{n} le groupe engendré par ces involutions.

Proposition 4.2. Chaque orbite de G_{n} contient un et un seul arbre binaire croissant. Soit T_{0} cet arbre croissant et soit k le nombre de ses feuilles. Alors le polynôme générateur de la G_{n}-orbite de T_{0} par la statistique (hr, cr) est donné par: p^{hr(T_{0})}(1 + q)^{n−k}. En particulier, l’orbite contient 2^{n−k} arbres minimax.

Démonstration. L’espèce de chaque sommet d’un arbre minimax reste invariante sous l’action de toute involution c_{i}. La statistique “hr” garde donc une valeur constante dans chaque G_{n}-orbite.

Soit T un arbre minimax ayant k feuilles. S’il a l sommets d’étiquette maximum, à savoir s_{i_{1}}, s_{i_{2}}, …, s_{i_{l}}, l’arbre T_{0} := d(s_{i_{1}})d(s_{i_{2}}) ⋯ d(s_{i_{l}}) T n’a alors que des étiquettes mimimum. Il est donc croissant. Désignons par (s_{1}, s_{2}, …, s_{n−k}) la suite croissante, pour l’ordre <_{T_{0}}, des sommets intérieurs de T_{0}. Dans l’algèbre du groupe G_{n}, le développement de (1 + d(s_{1}))(1 + d(s_{2})) ⋯ (1 + d(s_{n−k})) T_{0} donne 2^{n−k} termes. Chaque terme de cette somme peut s’exprimer comme ∏_{j∈A} d(s_{j}) T_{0}, où A est un sousensemble de {1, 2, …, n − k}. De plus, {s_{j} : j ∈ A} est l’ensemble des sommets maximum de l’arbre. Ces termes sont donc tous distincts. Posons aussi W (T) := p^{hr(T)}q^{cr(T)} et prolongeons la définition de W à l’algèbre du groupe, de sorte que W (1 + d(s_{i}))(T) = p^{hr(T)}(1 + q)q^{cr(T)}. Alors

∑_{T ∈orbite de T_{0}} W (T) = W (1 + d(s_{1}))(1 + d(s_{2})) ⋯ (1 + d(s_{n−k}))(T_{0})
= p^{hr(T_{0})}(1 + q)^{n−k}.

Notation. Pour tout arbre minimax T, on note c T l’unique arbre minimax croissant contenu dans sa G_{n}-orbite. L’application c est donc une surjection de M_{n,k} sur C_{n,k}.

5. Les opérations-retournements

Dans les opérations-compléments décrites dans le paragraphe précédent, la position des sommets de l’arbre reste inchangée, mais les étiquettes sont permutées. Pour les opérations-retournements, la position de certains sommets est modifiée, pas leurs étiquettes.

Pour décrire ces nouvelles opérations, il est commode de noter T [a] le sous-arbre dont la racine est d’étiquette a. De même, les sous-arbres à gauche et à droite incidents au sommet étiqueté a sont désignés par T_{g}[a] et T_{d}[a], respectivement.

Soit s un sommet intérieur, étiqueté a, d’un arbre minimax T. On désigne par

r[a] T

l’arbre déduit de T en faisant pivoter le sous-arbre T [a] autour d’un axe vertical passant par le sommet s. Si le sommet s étiqueté a est une feuille, on pose r[a] T = T.

Par exemple, l’opération r[3], appliquée à l’arbre de la Fig. 1, donne l’arbre représenté dans la Fig. 10.

[figure: •; •; •; •; •; •; •; •; •; •; 1; 10; 8; 9; 4; 2; 3; 7; 6; 5] Fig. 10

Les propriétés suivantes, valables pour les opérations r[a], sont évidentes:

(1) l’opération r[a] change non seulement l’espèce d’un sommet intérieur d’étiquette a, mais également l’espèce de chaque sommet intérieur du sous-arbre T [a] ;

(2) les opérations r[a] (a = 1, 2, …, n) agissent sur l’ensemble M_{n} et sont des involutions, commutant deux à deux ; soit R_{n} le groupe engendré par ces involutions ;

Soit s un sommet intérieur d’étiquette a d’un arbre minimax ; si ce sommet est double, on note {a′, a′′} l’ensemble des étiquettes des deux fils du sommet s ; s’il est simple, on désigne par a′ l’étiquette de son fils unique. Posons

s[a] := \{ \begin{matrix}r[a] r[a′] r[a′′], & si le sommet d’étiquette a est double ; \\ r[a] r[a′], & si le sommet d’étiquette a est simple. \end{matrix}

Il résulte de la propriété (1) ci-dessus que si dans un arbre T, le sommet d’étiquette a est intérieur, l’opération s[a], appliquée à T, change uniquement l’espèce du sommet d’étiquette a.

Proposition 5.1. Chaque orbite de R_{n} contient un et un seul arbre binaire de Hetyei-Reiner. Soit T_{1} cet arbre de Hetyei-Reiner et soit k le nombre de ses feuilles. Alors le polynôme générateur de la R_{n}-orbite de T_{1} par la statistique (hr, cr) est donné par: (1 + p)^{n−k}q^{cr(T_{1})}. En particulier, la R_{n}-orbite de T contient exactement 2^{n−k} arbres minimax.

Démonstration. Il suffit de reprendre la démonstration de la Proposition 4.2, en faisant jouer à s le rôle joué par d et à la stastique “cr” celui joué par “hr”.

Notation. Pour tout arbre minimax T, on note r T l’unique arbre de Heytei-Reiner contenu dans sa R_{n}-orbite. L’application r est donc une surjection de M_{n,k} sur HR_{n,k}.

6. Arbres d’André

Les groupes G_{n} et R_{n} ont exactement n! orbites. En effet, comme indiqué dans le troisième paragraphe, la projection orthogonale sur un axe horizontal des étiquettes d’un arbre croissant (resp. de Hetyei-Reiner) est une bijection de C_{n} (resp. de HR_{n}) sur l’ensemble des permutations de 1, 2, …, n.

Si maintenant on applique l’opération c à un arbre de Hetyei-Reiner, ou bien si on applique r à un arbre croissant, on obtient, dans les deux cas, un arbre de Hetyei-Reiner croissant, c’est-à-dire un arbre d’André. Nous avons vu précédemment que les opérations c(s), commutent entre elles ; il en est de même pour les opérations r[a]. Il s’agit maintenant de démontrer que les c(s) et les r[a] commutent mutuellement. Ce résultat doit s’établir avec quelques précautions de langage que nous allons développer.

Soit a l’étiquette d’un sommet intérieur s d’un arbre minimax T. Les sommets de T et de l’arbre transformé T′ = c(s) T sont identiques. Seules les étiquettes des sous-arbres T (s) et T′(s) diffèrent. En particulier, l’étiquette a du sommet s dans T se transforme en une étiquette a′ ≠ a dans T′. Posons:

c[a] T := c(s) T.

De même, posons:

r(s) T := r[a] T.

Autrement dit, les opérations c(·) et r(·) (avec des parenthèses) s’appliquent à des sommets, alors que c[·] et r[·] (avec des crochets) s’appliquent aux étiquettes.

Proposition 6.1. Soient s un sommet d’un arbre minimax T d’ordre n et a′ un entier compris entre 1 et n. Alors on a l’identité:

(6.1)  r(s)c[a′] T = c[a′]r(s) T.

Démonstration. Géométriquement, la relation (6.1) est tout à fait évidente. Partant d’un arbre minimax, il s’agit de changer les étiquettes du sous-arbre dont la racine est d’étiquette est a′, d’une part, et de faire pivoter autour de l’axe vertical le sous-arbre de sommet s. Il est clair que ces deux opérations peuvent être faites dans un ordre arbitraire.

Remarque. Notons que si la relation (6.1) est vraie, on a, en général,

c(s)r[a′] T ≠ r[a′]c(s) T.

Soit T_{0,0} un arbre minimax ; l’unique arbre croissant T_{0,l} := c T_{0,0} de son G_{n}-orbite peut s’exprimer comme c[a_{l}] ⋯ c[a_{1}] T_{0,0}, où (a_{1}, …, a_{l}) est une suite d’entiers. De même, l’unique arbre de Hetyei-Reiner T_{l′,0} := r T_{0,0} de son R_{n}-orbite peut s’exprimer comme r(s_{l′}) ⋯ r(s_{1}) T_{0,0}, où s_{1} est un sommet de T_{0,0}, puis s_{2} un sommet de T_{1,0} := r(s_{1}) T_{0,0}, …, enfin, s_{l′} un sommet de T_{l′−1,0} := r(s_{l′−1}) ⋯ r(s_{1}) T_{0,0}.

Considérons le diagramme:

T_{0,0} ⟶^{c[a_{1}]} T_{0,1} ⟶^{c[a_{2}]} ⋯ ⟶^{c[a_{l}]} T_{0,l}
↓^{r(s_{1})}  ↓^{r(s_{1})}  ↓^{r(s_{1})}
T_{1,0} ⟶^{c[a_{1}]} T_{1,1} ⟶^{c[a_{2}]} ⋯ ⟶^{c[a_{l}]} T_{1,l}
↓^{r(s_{2})}  ↓^{r(s_{2})}  ↓^{r(s_{2})}
⋮  ⋮  ⋮
↓^{r(s_{l′})}  ↓^{r(s_{l′})}  ↓^{r(s_{l′})}
T_{l′,0} ⟶^{c[a_{1}]} T_{l′,1} ⟶^{c[a_{2}]} ⋯ ⟶^{c[a_{l}]} T_{l′,l}

Comme les involutions c[a_{i}] ne modifient pas la position des sommets, le sommet s_{1} est un sommet de tous les arbres de la première ligne. Comme s_{2} est un sommet de l’arbre T_{1,0}, il est aussi un sommet de tous les arbres de la seconde ligne, et ainsi de suite. Le diagramme a bien un sens. Il est enfin commutatif d’après la Proposition 6.1.

D’autre part, si un arbre T est croissant (resp. de Hetyei-Reiner) et si s est un sommet d’étiquette a, alors r(s) T (resp. c[a] T) est aussi croissant (resp. de Hetyei-Reiner). Il en résulte que, dans le diagramme, tous les arbres de la colonne de droite sont croissants et tous les arbres de la dernière ligne sont de Hetyei-Reiner. De plus, T_{l′,l} est un arbre d’André. Enfin, tous les arbres d’une même ligne (resp. colonne) appartiennent à la même G_{n}-orbite (resp. R_{n}-orbite).

Puisque c T_{0,0} = c[a_{l}] ⋯ c[a_{1}] T_{0,0} et r T_{0,0} = r(s_{l′}) ⋯ r(s_{1}) T_{0,0}, on a donc aussi c T_{i,0} = c[a_{l}] ⋯ c[a_{1}] T_{i,0} et r T_{0,j} = r(s_{l′}) ⋯ c(s_{1}) T_{0,j} pour tout i = 1, …, l et j = 1, …, l′ ; d’où le diagramme commutatif:

(6.2)  \begin{matrix}T_{0,0} & ⟶^{c} & T_{0,1} \\ ↓^{r} & & ↓^{r} \\ T_{l′,0} & ⟶^{c} & T_{l′,l} \end{matrix}

Soit T_{0} un arbre d’André d’ordre n ayant k feuilles. La somme ∑_{T} T, étendue à tous les T tels que c r T = r c T = T_{0}, peut s’écrire:

∑_{c r T =T_{0}} T = (1 + d(s_{1})) ⋯ (1 + d(s_{n−k}))(1 + s[a_{1}]) ⋯ (1 + s[a_{n−k}]) T_{0},

en utilisant les opérateurs d(s_{i}) et s[a_{i}] introduits dans les paragraphes 4 et 5. D’où, en posant toujours W (T) = p^{hr(T)}q^{cr(T)},

∑_{c r T =T_{0}} W (T) = W (1 + d(s_{1})) ⋯ (1 + d(s_{n−k}))

× (1 + s[a_{1}]) ⋯ (1 + s[a_{n−k}])(T_{0}) = (1 + p)^{n−k}(1 + q)^{n−k}.

7. Fonctions génératrices

Dans le troisième paragraphe, on a montré que la fonction génératrice exponentielle des polynômes générateurs des arbres minimax pouvait se déduire de la fonction génératrice exponentielle des polynômes d’André D_{n}(t) = ∑_{k} d_{n,k}t^{k}, où d_{n,k} désigne le nombre d’arbres d’André d’ordre n ayant k feuilles. L’identité (3.3) a été obtenue dans [FoSch73] par des technique analytiques. Nous nous proposons de l’établir par les techniques classiques de l’algèbre combinatoire.

La récurrence (3.3) pour les nombres d_{n,k} est équivalente à la relation

(7.1) D_{n}(t) = nt D_{n−1}(t) + t(1 − 2t)D′_{n−1}(t) (n ≥ 1), D_{0}(t) = 1,

où D′_{n−1}(t) désigne la dérivée du polynôme D_{n−1}(t). Posons:

r(t) := (1 − 2t)^{1/2}; w(t) := \frac{1 − r(t)}{1 + r(t)}; F_{n}(t) := \frac{D_{n}(t)}{r(t)^{n+1}} (n = 0, 1, 2, …).

Puisque r′(t) = −r(t)^{−1}, la relation (7.1) entraîne:

(7.2)  F_{n}(t) = t r(t) F′_{n−1}(t) (n ≥ 1), F_{0}(t) = r(t)^{−1}.

Pour résoudre cette équation faisant intervenir l’opérateur différentiel et celui aux différences, on s’inspire des techniques connues utilisées pour les polynômes eulériens (voir [Ri58], Exercice 2, pp. 14-15).

Proposition 7.1. On a l’identité:

(7.3)  F_{n}(t) = 2 ∑_{j≥1} w(t)^{j} j^{n} (n ≥ 1).

Démonstration. Posons, pour simplifier, r := r(t) et w := w(t). Il faut vérifier que le membre de droite de (7.3) satisfait l’équation (7.2). Or ∑_{j≥0} w^{j} = (1 + r^{−1})/2 et par dérivation ∑_{j≥1} j w^{j−1} w′ = r^{−3}/2, d’où 2 ∑_{j≥1} w^{j} = t r^{−2} = t r(r^{−1})′. L’équation (7.3) est donc satisfaite pour n = 1.

Pour n ≥ 2, on a, en partant de la relation (7.3) avec n remplacé par

(n − 1), l’identité F′_{n−1}(t) = 2 ∑_{j≥1} j w^{j−1}w′ j^{n−1} = 2 ∑_{j≥1} w^{j−1} \frac{2}{r(1 + r)^{2}} j^{n}.

Or, 2t = (1 − r)(1 + r). On en tire:

t r F′_{n−1}(t) = 2 ∑_{j≥1}(\frac{1 − r}{1 + r} )^{j−1} \frac{(1 − r)(1 + r)}{(1 + r)^{2}}j^{n} = 2 ∑_{j≥1} w^{j}j^{n}.

La relation (7.3) se récrit à l’aide des polynômes D_{n}(t) comme:

(7.4)  \frac{D_{n}(t)}{(1 − 2t)^{(n+1)/2}} = 2 ∑_{j≥1}(\frac{1 − (1 − 2t)^{1/2}}{1 + (1 − 2t)^{1/2}} )^{j}j^{n}.

De la Proposition 7.1 on peut alors obtenir la fonction génératrice exponentielle des séries F_{n}(t) et des polynômes D_{n}(t) par une simple manipulation. Comme 1 + 2w/(1 − w) = r^{−1}, on a:

∑_{n≥0} \frac{u^{n}}{n!} F_{n}(t) = r^{−1} + 2 ∑_{n≥1} \frac{u^{n}}{n!} ∑_{j≥1} w^{j}j^{n} = 1 + 2 ∑_{j≥1} w^{j} + 2 ∑_{n≥1} \frac{u^{n}}{n!} ∑_{j≥1} w^{j}j^{n}

= 1 + 2 ∑_{n≥0} \frac{u^{n}}{n!} ∑_{j≥1} w^{j}j^{n} = 1 + 2 ∑_{j≥1} w^{j} ∑_{n≥0} \frac{(uj)^{n}}{n!}

= 1 + 2 ∑_{j≥1}(we^{u})^{j} = 1 + 2\frac{we^{u}}{1 − we^{u}} .

Soit

(7.5)  ∑_{n≥0} \frac{u^{n}}{n!} F_{n}(t) = \frac{1 + w(t)e^{u}}{1 − w(t)e^{u}} .

Et par conséquent:

∑_{n≥0} \frac{u^{n}}{n!} D_{n}(t) = ∑_{n≥0} r^{n+1} \frac{u^{n}}{n!} F_{n}(t)

= r(t)\frac{1 + w(t)e^{r(t)u}}{1 − w(t)e^{r(t)u}} . (7.6)

Notons qu’en posant t = 1 dans la précédente identité et en notant que r(1) = i et w(1) = −i, on trouve

∑_{n≥0} \frac{u^{n}}{n!} D_{n}(1) = tan u + sec u,

une manière de retrouver que le nombre d’arbres d’André d’ordre n est égal au nombre tangent ou au nombre sécant.

Une autre technique pour obtenir l’identité (7.5) à partir de l’équation différentielle et aux différences (7.2) est de poser

F := F (t, u) := ∑_{n≥0} \frac{u^{n}}{n!} F_{n}(t)

et de vérifier qu’en désignant par D_{u} et D_{t} les dérivées partielles par rapport à u et t, respectivement, on peut récrire (7.2) sous la forme:

(7.7)  D_{u} F = tr D_{t}F, F (t, 0) = r(t)^{−1}.

On cherche alors des solutions de la forme F = f(g(t)h(u)), s’imposant que F est fonction de t et u à travers un produit de fonctions g(t) · h(u). Alors (7.7) se récrit tr f′(g(t)h(u)) g′(t)h(u) = f′(g(t)h(u)) g(t)h′(u). En prenant maintenant h(u) = e^{u}, on en déduit l’équation différentielle: g′(t)/g(t) = 1/tr = 1/(t(1 − 2t)^{1/2}). Or

∫ \frac{1}{t(1 − 2t)^{1/2}} dt = ln (C \frac{(1 − 2t)^{1/2} − 1}{(1 − 2t)^{1/2} + 1}) = ln Cw(t),

où C est une constante; de là

g(t) = C w(t).

D’où une solution de la forme F (t, u) = f(Cw(t)e^{u}). Comme F (t, 0) = r(t)^{−1} = (1 + w(t))/(1 − w(t)) = f(Cw(t)), on obtient:

F (t, u) = f(Cw(t)e^{u}) = \frac{1 + w(t)e^{u}}{1 − w(t)e^{u}} .

8. Autres opérations-compléments et retournements

Plutôt que de faire une étude abstraite, nous avons préféré obtenir les résultats ci-dessus sur les arbres minimax à l’aide d’une seule classe d’opérations-compléments et une seule classe d’opérations-retournements. Naturellement il existe d’autres telles opérations qui conduisent aux mêmes résultats. Nous nous contentons d’abord de signaler deux autres opérations-compléments, notées c′(s) et c′′(s).

Soit s un sommet intérieur d’un arbre minimax T ayant n sommets, de sorte que l’un au moins des sous-arbres T_{g}(s), T_{d}(s) est non vide. Soit a l’étiquette de s ; si elle est minimum (resp. maximum) dans le sous-arbre T (s), on note \overline{s} le sommet d’étiquette maximum (resp. minimum) dans T (s) et on désigne par \overline{a} son étiquette. Ce sommet appartient soit à T_{g}(s), soit à T_{d}(s). La première opération-complément est donnée par:

c′(s)T := \{ \begin{matrix}T \ (\{s\} ∪ T_{g}(s)) + c(s)(\{s\} ∪ T_{g}(s)), & si \overline{s} ∈ T_{g}(s) ; \\ T \ (\{s\} ∪ T_{d}(s)) + c(s)(\{s\} ∪ T_{d}(s)), & si \overline{s} ∈ T_{d}(s). \end{matrix}

Autrement dit, on applique l’opération-complément c(s) au seul sous-arbre {s}∪T_{g}(s)) (resp. {s}∪T_{d}(s))) et on laisse invariantes les autres étiquettes.

Soit maintenant f(s) la racine du sous-arbre T_{g}(s) (resp. T_{d}(s)) si \overline{s} ∈ T_{g}(s) (resp. si \overline{s} ∈ T_{d}(s)). On définit c′′(s) par:

c′′(s)T := \{ \begin{matrix}T \ (\{s\} ∪ T_{g}(s)) + c(f(s))c(s)(\{s\} ∪ T_{g}(s)), & si \overline{s} ∈ T_{g}(s) ; \\ T \ (\{s\} ∪ T_{d}(s)) + c(f(s))c(s)(\{s\} ∪ T_{d}(s)), & si \overline{s} ∈ T_{d}(s). \end{matrix}

Dans cette dernière opération, l’application de c(f(s)) a pour effet de répartir les nouvelles étiquettes du sous-arbre contenant \overline{s} dans leur ordre originel. Lorsqu’on applique les opérations c′′(s) aux seuls arbres de Hetyei-Reiner, on retrouve les opérations ψ_{k} introduites par ces auteurs [HeRe98].

On peut aussi définir directement les opérations-compléments c′(s) et c′′(s) de la façon suivante. Désignons par a_{1} < a_{2} < ⋯ < a_{m′} la suite croissante des étiquettes dans le sous-arbre {s} ∪ T_{g}(s) ou le sous-arbre \{s\} ∪ T_{d}(s) suivant que \overline{s} ∈ T_{g}(s) ou non.

Pour obtenir c′(s)T, on ne modifie pas les étiquettes des sommets dans T \ ({s} ∪ T_{g}(s)) (resp. dans T \ ({s} ∪ T_{d}(s))), mais on change chaque étiquette a_{i} en a_{m′+1−i}.

Pour obtenir c′′(s)T, on ne modifie pas les étiquettes des sommets dans T \ ({s} ∪ T_{g}(s)) (resp. dans T \ ({s} ∪ T_{d}(s))), on change ensuite l’étiquette a de s en \overline{a} et enfin on remplace chaque étiquette a_{i} par a_{i−1} (i = 2, 3, …, m′) si s est d’étiquette minimum dans T (s) et par a_{i+1} (i = 1, 2, …, m′ − 1) si s est d’étiquette maximum.

Pour les retournements, il s’agit de prendre un ordre total sur les sous-arbres. Au lieu de la définition prise au début du troisième paragraphe, on peut prendre la convention suvante: dans un arbre minimax T, soit s un sommet d’étiquette a ; si l’étiquette a d’un sommet intérieur s est minimum (resp. maximum) dans le sous-arbre T (s), on dit que le sommet s est de première espèce si min T_{g}{a} < min T_{d}{a} (resp. max T_{g}{a} < max T_{d}{a}). Les arbres dont les sommets sont tous de première espèce sont dits arbres de Hetyei-Reiner II. Un arbre croissant, qui est aussi de Hetyei-Reiner II est alors un arbre d’André II, déjà considéré dans [FoSch73].

Appendice. Dans la Fig. 11, le coin supérieur gauche est occupé par un arbre minimax T d’ordre n = 10. Pour obtenir l’arbre croissant c T, il suffit d’appliquer la suite des opérations-compléments c[10], c[9], c[7]. On obtient l’arbre situé dans le coin supérieur droit. L’arbre de Hetyei-Reiner r T apparaît dans le coin inférieur gauche. Enfin l’arbre d’André T_{0} := c r T = r c T est dans le coin inférieur droit. Il faut noter que tous les arbres de la colonne la plus à droite sont croissants, ceux de la ligne tout en bas sont de Hetyei-Reiner. Les arbres ont k = 4 feuilles. La classe des arbres minimax T′ tels que c r T′ = T_{0} contient donc 4^{n−k} = 4^{6} = 4.096 éléments, dont les 20 représentés dans ce tableau.

Remerciements. Les auteurs tiennent à remercier Gabor Hetyei pour d’utiles discussions et aussi pour leur avoir donné les références essentielles dans l’étude de la variation cd des ensembles partiellement ordonnés.

Ils remercient aussi l’arbitre anonyme pour sa lecture attentive et ses remarques judicieuses. En particulier, celui-ci a indiqué une autre méthode pour obtenir la fonction génératrice (7.5), qui utilise la réversion des séries formelles et la série génératrice des nombres de Catalan.

[figure: 1; 10; 8; 9; 4; 2; 3; 6; 7; 5; ⟶^{c[10]}; _{↓_{r(−1,1)}}] [figure: 1; 4; 9; 8; 10; 2; 3; 6; 7; 5; ⟶^{c[9]}; _{↓_{r(−1,1)}}] [figure: 1; 4; 8; 9; 10; 2; 3; 6; 7; 5; ⟶^{c[7]}; _{↓_{r(−1,1)}}] [figure: 1; 4; 8; 9; 10; 2; 3; 6; 5; 7; _{↓_{r(−1,1)}}]

[figure: 1; 10; 8; 9; 4; 2; 3; 6; 7; 5; ⟶^{c[10]}; _{↓_{r(1,1)}}; 1; 4; 9; 8; 10; 2; 3; 6; 7; 5; ⟶^{c[9]}; _{↓_{r(1,1)}}; 1; 4; 8; 9; 10; 2; 3; 6; 7; 5; ⟶^{c[7]}; _{↓_{r(1,1)}}; 1; 4; 8; 9; 10; 2; 3; 6; 5; 7; _{↓_{r(1,1)}}]

[figure: 1; 10; 4; 9; 8; 2; 3; 6; 7; 5; ⟶^{c[10]}; _{↓_{r(− \frac{1}{2} ,2)}}; 1; 4; 10; 8; 9; 2; 3; 6; 7; 5; ⟶^{c[9]}; _{↓_{r(− \frac{1}{2} ,2)}}; 1; 4; 10; 9; 8; 2; 3; 6; 7; 5; ⟶^{c[7]}; _{↓_{r(− \frac{1}{2} ,2)}}; 1; 4; 10; 9; 8; 2; 3; 6; 5; 7; _{↓_{r(− \frac{1}{2} ,2)}}]

[figure: 1; 10; 4; 9; 8; 2; 3; 7; 6; 5; ⟶^{c[10]}; _{↓_{r( \frac{1}{2} ,2)}}; 1; 4; 10; 8; 9; 2; 3; 7; 6; 5; ⟶^{c[9]}; _{↓_{r( \frac{1}{2} ,2)}}; 1; 4; 10; 9; 8; 2; 3; 7; 6; 5; ⟶^{c[7]}; _{↓_{r( \frac{1}{2} ,2)}}; 1; 4; 10; 9; 8; 2; 3; 5; 6; 7; _{↓_{r( \frac{1}{2} ,2)}}]

[figure: 1; 10; 4; 9; 8; 2; 3; 7; 6; 5; ⟶^{c[10]}; 1; 4; 10; 8; 9; 2; 3; 7; 6; 5; ⟶^{c[9]}; 1; 4; 10; 9; 8; 2; 3; 7; 6; 5; ⟶^{c[7]}; 1; 4; 10; 9; 8; 2; 3; 5; 6; 7]

Fig. 11 Bibliographie

[An79] D. André, Développements de sec x et de tan x, C. R. Acad. Sc. Paris, 88 (1879), 965-967.

[An79] D. André, Sur les permutations alternées, J. Math. Pures Appl., 7 (1881), 167-184.

[AnGe79] G. E. Andrews and I. Gessel, Divisibility properties of the q-tangent numbers, Proc. Amer. Math. Soc., 68 (1978), 380-384.

[Fo81] D. Foata, Further divisibility of the q-tangent numbers, Proc. Amer. Math. Soc., 81 (1981), 143-148.

[FoSch71] D. Foata et M.-P. Schützenberger, Nombres d’Euler et permutations alternantes. Manuscrit, 71 pages, University of Florida, Gainesville, 1971.

[FoSch71] D. Foata et M.-P. Schützenberger, Nombres d’Euler et permutations alternantes, in J. N. Srivastava et al. (eds.), A Survey of Combinatorial Theory, NortHolland, Amsterdam, 1973, pp. 173-187.

[FoSt74] D. Foata and V. Strehl, Rearrangements of the symmetric group and enumerative properties of the tangent and secant numbers, Math. Z., 137 (1974), 257-264.

[FoSt76] D. Foata and V. Strehl, Euler numbers and variations of permutations, in Colloquio Internazionale sulle Teorie Combinatorie, 1973, Tome I (Atti dei Convegni Lincei, 17, 119-131). Accademia Nazionale dei Lincei, 1976.

[HeRe98] G. Hetyei and E. Reiner, Permutation Trees and Variation Statistics, Europ. J. Combinatorics, 19 (1998), 847-866.

[He96] G. Hetyei, On the cd-Variation Polynomials of André and Simsun Permutations, Discrete & Computational Geometry, 16 (1996), 259-276.

[Pu93] M. Purtill, André permutations, lexicographic shellability and the cd-index of a convex polytope, Trans. Amer. Math. Soc., 338 (1993), 77-104.

[Ri58] J. Riordan, An Introduction to Combinatorial Analysis. New York, John Wiley, 1958.

[St94] R. P. Stanley, Flag f-vectors and the cd-index, Math. Z., 216 (1994), 483-499.

[Su94] S. Sundaram, The homology representations of the symmetric group on Cohen-Macaulay subposets of the partition lattice, Adv. in Math., 104 (1994), 225-296.

Dominique Foata Département de mathématique Université Louis Pasteur 7, rue René-Descartes F-67084 Strasbourg

email: foata@math.u-strasbg.fr
http://cartan.u-strasbg.fr/∼foata

Guo-Niu Han

I.R.M.A.-C.N.R.S.

Université Louis Pasteur 7, rue René-Descartes F-67084 Strasbourg

                                         email: guoniu@math.u-strasbg.fr
                                         http://cartan.u-strasbg.fr/∼guoniu