% This the plain TeX file of the paper entitled
% "Arbres minimax et polynomes d'Andre'
% by Dominique Foata and Guoniu Han
% 23 pages

% le fichier grille

\def\Grille{\setbox13=\vbox to 5mm{\hrule width 110mm\vfill}
\setbox13=\vbox{\offinterlineskip
   \copy13\copy13\copy13\copy13\copy13\copy13\copy13\copy13
   \copy13\copy13\copy13\copy13\box13\hrule width 110mm}
\setbox14=\hbox to 5mm{\vrule height 65mm\hfill}
\setbox14=\hbox{\copy14\copy14\copy14\copy14\copy14\copy14
   \copy14\copy14\copy14\copy14\copy14\copy14\copy14\copy14
   \copy14\copy14\copy14\copy14\copy14\copy14\copy14\copy14\box14}
\ht14=0pt\dp14=0pt\wd14=0pt
\setbox13=\vbox to 0pt{\vss\box13\offinterlineskip\box14}
\wd13=0pt\box13}

\def\grille{\noalign{\nointerlineskip\Grille\nointerlineskip}}

%������������������������������������������������������������������

\def\fleche(#1,#2)\dir(#3,#4)\long#5{%
\noalign{\nointerlineskip\leftput(#1,#2){\vector(#3,#4){#5}}\nointerlineskip}}

%������������������������������������������������������������������

\def\diagram#1{\def\normalbaselines{\baselineskip=0pt\lineskip=5pt}
\matrix{#1}}

\def\hfl#1#2#3{\smash{\mathop{\hbox to#3{\rightarrowfill}}\limits
^{\scriptstyle#1}_{\scriptstyle#2}}}

\def\gfl#1#2#3{\smash{\mathop{\hbox to#3{\leftarrowfill}}\limits
^{\scriptstyle#1}_{\scriptstyle#2}}}

\def\vfl#1#2#3{\llap{$\scriptstyle #1$}
\left\downarrow\vbox to#3{}\right.\rlap{$\scriptstyle #2$}}

%������������������������������������������������������������������


 \message{`lline' & `vector' macros from LaTeX}
 \catcode`@=11
\def\{{\relax\ifmmode\lbrace\else$\lbrace$\fi}
\def\}{\relax\ifmmode\rbrace\else$\rbrace$\fi}
\def\newcount{\alloc@0\count\countdef\insc@unt}
\def\newdimen{\alloc@1\dimen\dimendef\insc@unt}
\def\newwrite{\alloc@7\write\chardef\sixt@@n}

\newwrite\@unused
\newcount\@tempcnta
\newcount\@tempcntb
\newdimen\@tempdima
\newdimen\@tempdimb
\newbox\@tempboxa

\def\@spaces{\space\space\space\space}
\def\@whilenoop#1{}
\def\@whiledim#1\do #2{\ifdim #1\relax#2\@iwhiledim{#1\relax#2}\fi}
\def\@iwhiledim#1{\ifdim #1\let\@nextwhile=\@iwhiledim
        \else\let\@nextwhile=\@whilenoop\fi\@nextwhile{#1}}
\def\@badlinearg{\@latexerr{Bad \string\line\space or \string\vector
   \space argument}}
\def\@latexerr#1#2{\begingroup
\edef\@tempc{#2}\expandafter\errhelp\expandafter{\@tempc}%
%% error help message pieces.
\def\@eha{Your command was ignored.
^^JType \space I <command> <return> \space to replace it
  with another command,^^Jor \space <return> \space to continue without it.}
\def\@ehb{You've lost some text. \space \@ehc}
\def\@ehc{Try typing \space <return>
  \space to proceed.^^JIf that doesn't work, type \space X <return> \space to
  quit.}
\def\@ehd{You're in trouble here.  \space\@ehc}

\typeout{LaTeX error. \space See LaTeX manual for explanation.^^J
 \space\@spaces\@spaces\@spaces Type \space H <return> \space for
 immediate help.}\errmessage{#1}\endgroup}
\def\typeout#1{{\let\protect\string\immediate\write\@unused{#1}}}

% line & circle fonts
\font\tenln    = line10
\font\tenlnw   = linew10
%\font\tencirc  = circle10
%\font\tencircw = circlew10


\newdimen\@wholewidth
\newdimen\@halfwidth
\newdimen\unitlength 

\unitlength =1pt

%\newbox\@picbox
%\newdimen\@picht

\def\thinlines{\let\@linefnt\tenln \let\@circlefnt\tencirc
  \@wholewidth\fontdimen8\tenln \@halfwidth .5\@wholewidth}
\def\thicklines{\let\@linefnt\tenlnw \let\@circlefnt\tencircw
  \@wholewidth\fontdimen8\tenlnw \@halfwidth .5\@wholewidth}

\def\linethickness#1{\@wholewidth #1\relax \@halfwidth .5\@wholewidth}



\newif\if@negarg

\def\lline(#1,#2)#3{\@xarg #1\relax \@yarg #2\relax
\@linelen=#3\unitlength
\ifnum\@xarg =0 \@vline
  \else \ifnum\@yarg =0 \@hline \else \@sline\fi
\fi}

\def\@sline{\ifnum\@xarg< 0 \@negargtrue \@xarg -\@xarg \@yyarg -\@yarg
  \else \@negargfalse \@yyarg \@yarg \fi
\ifnum \@yyarg >0 \@tempcnta\@yyarg \else \@tempcnta -\@yyarg \fi
\ifnum\@tempcnta>6 \@badlinearg\@tempcnta0 \fi
\setbox\@linechar\hbox{\@linefnt\@getlinechar(\@xarg,\@yyarg)}%
\ifnum \@yarg >0 \let\@upordown\raise \@clnht\z@
   \else\let\@upordown\lower \@clnht \ht\@linechar\fi
\@clnwd=\wd\@linechar
\if@negarg \hskip -\wd\@linechar \def\@tempa{\hskip -2\wd\@linechar}\else
     \let\@tempa\relax \fi
\@whiledim \@clnwd <\@linelen \do
  {\@upordown\@clnht\copy\@linechar
   \@tempa
   \advance\@clnht \ht\@linechar
   \advance\@clnwd \wd\@linechar}%
\advance\@clnht -\ht\@linechar
\advance\@clnwd -\wd\@linechar
\@tempdima\@linelen\advance\@tempdima -\@clnwd
\@tempdimb\@tempdima\advance\@tempdimb -\wd\@linechar
\if@negarg \hskip -\@tempdimb \else \hskip \@tempdimb \fi
\multiply\@tempdima \@m
\@tempcnta \@tempdima \@tempdima \wd\@linechar \divide\@tempcnta \@tempdima
\@tempdima \ht\@linechar \multiply\@tempdima \@tempcnta
\divide\@tempdima \@m
\advance\@clnht \@tempdima
\ifdim \@linelen <\wd\@linechar
   \hskip \wd\@linechar
  \else\@upordown\@clnht\copy\@linechar\fi}

%\def\@hline{\ifnum \@xarg <0 \hskip -\@linelen \fi
%\vrule \@height \@halfwidth \@depth \@halfwidth \@width
%\@linelen \ifnum \@xarg <0 \hskip -\@linelen \fi}


\def\@hline{\ifnum \@xarg <0 \hskip -\@linelen \fi
\vrule height \@halfwidth depth \@halfwidth width \@linelen
\ifnum \@xarg <0 \hskip -\@linelen \fi}

\def\@getlinechar(#1,#2){\@tempcnta#1\relax\multiply\@tempcnta 8
\advance\@tempcnta -9 \ifnum #2>0 \advance\@tempcnta #2\relax\else
\advance\@tempcnta -#2\relax\advance\@tempcnta 64 \fi
\char\@tempcnta}

\def\vector(#1,#2)#3{\@xarg #1\relax \@yarg #2\relax
\@linelen=#3\unitlength
\ifnum\@xarg =0 \@vvector
  \else \ifnum\@yarg =0 \@hvector \else \@svector\fi
\fi}

\def\@hvector{\@hline\hbox to 0pt{\@linefnt
\ifnum \@xarg <0 \@getlarrow(1,0)\hss\else
    \hss\@getrarrow(1,0)\fi}}

\def\@vvector{\ifnum \@yarg <0 \@downvector \else \@upvector \fi}

\def\@svector{\@sline
\@tempcnta\@yarg \ifnum\@tempcnta <0 \@tempcnta=-\@tempcnta\fi
\ifnum\@tempcnta <5
  \hskip -\wd\@linechar
  \@upordown\@clnht \hbox{\@linefnt  \if@negarg
  \@getlarrow(\@xarg,\@yyarg) \else \@getrarrow(\@xarg,\@yyarg) \fi}%
\else\@badlinearg\fi}

\def\@getlarrow(#1,#2){\ifnum #2 =\z@ \@tempcnta='33\else
\@tempcnta=#1\relax\multiply\@tempcnta \sixt@@n \advance\@tempcnta
-9 \@tempcntb=#2\relax\multiply\@tempcntb \tw@
\ifnum \@tempcntb >0 \advance\@tempcnta \@tempcntb\relax
\else\advance\@tempcnta -\@tempcntb\advance\@tempcnta 64
\fi\fi\char\@tempcnta}

\def\@getrarrow(#1,#2){\@tempcntb=#2\relax
\ifnum\@tempcntb < 0 \@tempcntb=-\@tempcntb\relax\fi
\ifcase \@tempcntb\relax \@tempcnta='55 \or
\ifnum #1<3 \@tempcnta=#1\relax\multiply\@tempcnta
24 \advance\@tempcnta -6 \else \ifnum #1=3 \@tempcnta=49
\else\@tempcnta=58 \fi\fi\or
\ifnum #1<3 \@tempcnta=#1\relax\multiply\@tempcnta
24 \advance\@tempcnta -3 \else \@tempcnta=51\fi\or
\@tempcnta=#1\relax\multiply\@tempcnta
\sixt@@n \advance\@tempcnta -\tw@ \else
\@tempcnta=#1\relax\multiply\@tempcnta
\sixt@@n \advance\@tempcnta 7 \fi\ifnum #2<0 \advance\@tempcnta 64 \fi
\char\@tempcnta}



\def\@vline{\ifnum \@yarg <0 \@downline \else \@upline\fi}


\def\@upline{\hbox to \z@{\hskip -\@halfwidth \vrule
  width \@wholewidth height \@linelen depth \z@\hss}}

\def\@downline{\hbox to \z@{\hskip -\@halfwidth \vrule
  width \@wholewidth height \z@ depth \@linelen \hss}}

\def\@upvector{\@upline\setbox\@tempboxa\hbox{\@linefnt\char'66}\raise
     \@linelen \hbox to\z@{\lower \ht\@tempboxa\box\@tempboxa\hss}}

\def\@downvector{\@downline\lower \@linelen
      \hbox to \z@{\@linefnt\char'77\hss}}

%INITIALIZATION
\thinlines

\newcount\@xarg
\newcount\@yarg
\newcount\@yyarg
\newcount\@multicnt
\newdimen\@xdim
\newdimen\@ydim
\newbox\@linechar
\newdimen\@linelen
\newdimen\@clnwd
\newdimen\@clnht
\newdimen\@dashdim
\newbox\@dashbox
\newcount\@dashcnt
 \catcode`@=12


% macros supplementaires (J.D.)

\newbox\tbox
\newbox\tboxa

%\def\picbox(#1,#2,#3)#4{\setbox\tbox=\hbox{#4}%
%     \ht\tbox=#1 \wd\tbox=#2 \dp\tbox=#3 \box\tbox}

\def\leftzer#1{\setbox\tbox=\hbox to 0pt{#1\hss}%
     \ht\tbox=0pt \dp\tbox=0pt \box\tbox}

\def\rightzer#1{\setbox\tbox=\hbox to 0pt{\hss #1}%
     \ht\tbox=0pt \dp\tbox=0pt \box\tbox}

\def\centerzer#1{\setbox\tbox=\hbox to 0pt{\hss #1\hss}%
     \ht\tbox=0pt \dp\tbox=0pt \box\tbox}

% sytaxe: \image(hauteur totale reservee, distance
%    verticale de l'origine par rapport au bas de
%    la place reservee){materiel a inserer}
% L'origine est toujours centre horizontalement
%
\def\image(#1,#2)#3{\vbox to #1{\offinterlineskip
    \vss #3 \vskip #2}}

% \leftput place le materiel avec son point de reference
%    en #1,#2 unites \unitlength
% De meme pour \centerput et \rightput

\def\leftput(#1,#2)#3{\setbox\tboxa=\hbox{%
    \kern #1\unitlength
    \raise #2\unitlength\hbox{\leftzer{#3}}}%
    \ht\tboxa=0pt \wd\tboxa=0pt \dp\tboxa=0pt\box\tboxa}

\def\rightput(#1,#2)#3{\setbox\tboxa=\hbox{%
    \kern #1\unitlength
    \raise #2\unitlength\hbox{\rightzer{#3}}}%
    \ht\tboxa=0pt \wd\tboxa=0pt \dp\tboxa=0pt\box\tboxa}

\def\centerput(#1,#2)#3{\setbox\tboxa=\hbox{%
    \kern #1\unitlength
    \raise #2\unitlength\hbox{\centerzer{#3}}}%
    \ht\tboxa=0pt \wd\tboxa=0pt \dp\tboxa=0pt\box\tboxa}

\unitlength=1mm

\let\cput=\centerput

\def\put(#1,#2)#3{\noalign{\nointerlineskip
                               \centerput(#1,#2){$#3$}
                                \nointerlineskip}}
% fin du fichier grille --------------------

\magnification=1200
\hsize=11.25cm\hoffset=1cm
\def\bfc{{\bf c}}
\def\bfr{{\bf r}}
\def\bfd{{\bf d}}
\def\bfs{{\bf s}}
\def\hr{\mathop{\rm hr}}
\def\cro{\mathop{\rm cr}}
\def\compl{\mathop{\rm compl}}
\def\sym{\mathop{\rm sym}}
\def\stat{\mathop{\rm stat}}
\def\card{\mathop{\rm card}}
%
\def\qed{\quad\raise -2pt
\hbox{\vrule\vbox to 10pt{\hrule width 4pt
\vfill\hrule}\vrule}}
% fin du format

\voffset=.5cm
\vglue 2cm
\medskip
\centerline{\bf ARBRES MINIMAX ET POLYN\^OMES D'ANDR\'E}
\medskip
\centerline{Dominique Foata et Guoniu Han}
\bigskip\bigskip
{
\narrower\narrower
\noindent
{\bf Abstract}.\quad
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\'e trees. Various generating functions for those trees by
several statistics are also derived.

}

\bigskip
\centerline{\bf 1. Introduction}
\medskip
Les arbres que nous appelons {\it minimax} dans cet article 
sont {\it binaires}\break (chaque sommet de l'arbre a deux, un ou
z\'ero fils); {\it topologiques} (on distingue, pour chaque
sommet, le fils \`a gauche et le fils \`a droite, s'ils existent);
{\it \'etiquet\'es} (un {\it\'etiquetage} est
une bijection de l'ensemble des sommets de l'arbre sur un 
ensemble fini totalement ordonn\'e). Ils ont, de plus, la
propri\'et\'e suivante:

\smallskip
\item{$(M)$}dans tout sous-arbre d'un arbre minimax, l'\'etiquette
de la racine du sous-arbre est, soit le minimum, soit le maximum
des \'etiquettes des sommets du sous-arbre.

\smallskip
\noindent
On note $M_n$ l'ensemble des arbres minimax {\it d'ordre}~$n$,
c'est-\`a-dire des arbres minimax de~$n$ sommets,
\'etiquet\'es~1, 2, \dots~, $n$. Voir Fig.~1, o\`u un arbre minimax
d'ordre~10 est repr\'esent\'e. 


\midinsert
\newbox\boxarbre

\def\segment(#1,#2)\dir(#3,#4)\long#5{%
\leftput(#1,#2){\lline(#3,#4){#5}}}

\setbox\boxarbre=\vbox{\vskip
40mm\offinterlineskip 
\centerput(0,-1){$\bullet$}
\centerput(20,9){$\bullet$}
\centerput(30,19){$\bullet$}
\centerput(35,29){$\bullet$}
\centerput(10,19){$\bullet$}
\centerput(-20,9){$\bullet$}
\centerput(-30,19){$\bullet$}
\centerput(-35,29){$\bullet$}
\centerput(-25,29){$\bullet$}
\centerput(-22.5,39){$\bullet$}
%
\centerput(0,-4){$1$}
\centerput(20,6){$10$}
\centerput(30,16){$8$}
\centerput(35.5,26){$9$}
\centerput(10,16){$4$}
\centerput(-20,6){$2$}
\centerput(-30,16){$3$}
\centerput(-35.5,26){$6$}
\centerput(-24.5,26){$7$}
\centerput(-21.5,36){$5$}
%
\segment(0,0)\dir(2,1)\long{20}
\segment(20,10)\dir(1,1)\long{10}
\segment(30,20)\dir(1,2)\long{5}
\segment(20,10)\dir(-1,1)\long{10}
%
\segment(0,0)\dir(-2,1)\long{20}
\segment(-20,10)\dir(-1,1)\long{10}
\segment(-30,20)\dir(-1,2)\long{5}
\segment(-30,20)\dir(1,2)\long{5}
\segment(-25,30)\dir(1,4)\long{2.5}
}


$$
\box\boxarbre
$$
\medskip
\centerline{Fig. 1}

\endinsert

Les sommets sans fils d'un arbre sont appel\'es {\it feuilles} et les
sommets ayant au moins un fils sont  dits sommets {\it
int\'erieurs}, {\it simples} s'ils n'ont qu'un fils et {\it doubles}
s'ils ont deux fils. Dans un arbre minimax~$T$, d\'esignons par
$T_g(s)$ et~$T_d(s)$ les sous-arbres \`a gauche et \`a droite,
incidents au sommet~$s$ de~$T$. Notons \'egalement $T(s)$ le
sous-arbre de~$T$, dont la racine est~$s$, donc compos\'e de
cette racine et des deux sous-arbres $T_g(s)$ et $T_d(s)$ (voir
Fig.~2). De fa\c con \'evidente, $T_d(s)$, $T_g(s)$ et $T(s)$ sont
eux-m\^emes des arbres minimax.

\def\segment(#1,#2)\dir(#3,#4)\long#5{%
\leftput(#1,#2){\lline(#3,#4){#5}}}

\midinsert
\newbox\boxarbre

\setbox\boxarbre=\vbox{\vskip
32mm\offinterlineskip 
\segment(0,0)\dir(-1,1)\long{30}
\segment(-17,17)\dir(1,1)\long{13} 
\segment(-30,30)\dir(1,0)\long{26}
\segment(0,0)\dir(1,1)\long{30}
\segment(17,17)\dir(-1,1)\long{13}
\segment(4.,30)\dir(1,0)\long{26}
%\segment(-40,17)\dir(1,0)\long{80}
%\segment(-40,0)\dir(1,0)\long{80}
\centerput(17,25){$T_d(s)$}
\centerput(-17,25){$T_g(s)$}
\centerput(0,-3){$s$}
\centerput(-43,14){$\left\{\vrule height 1.4cm depth 1.4cm width
0cm\right.$}
\centerput(-49,14){$T(s)$}
\centerput(0,-1){$\bullet$}}

\centerline{\box\boxarbre}

\medskip
\centerline{Fig. 2}

\endinsert

On dit qu'un arbre minimax $T$ est {\it de Hetyei-Reiner} s'il a
en plus la propri\'et\'e suivante: 

\smallskip
\item{$(H\!R)$}si $s$ est un sommet int\'erieur
et si son \'etiquette est  minimum (resp. maximum) dans le
sous-arbre $T(s)$, alors le sous-arbre \`a droite $T_d(s)$ est non
vide et contient le sommet d'\'etiquette maximum (resp. minimum)
dans $T(s)$. 

\smallskip
\noindent
Il faut noter que Hetyei et Reiner [HeRe98]
appellent ``minimax" ce que nous appelons ``de Hetyei-Reiner".
Soit $H\!R_{n}$ l'ensemble des arbres de Hetyei-Reiner
d'ordre~$n$.

On dit qu'un arbre minimax est {\it croissant} 

\item{$(C\!R)$}si les racines de
tous ses sous-arbres ont des \'etiquettes
minimum. 

\smallskip
\noindent
Il en r\'esulte que la suite des \'etiquettes des sommets
situ\'es sur le chemin conduisant de la racine d'un arbre croissant
\`a 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 {\it arbre d'Andr\'e}, s'il
a la propri\'et\'e suivante:

\item{$(A)$}pour tout sommet int\'erieur $s$, le
sous-arbre
\`a droite $T_d(s)$ est non vide et contient le sommet
d'\'etiquette maximum dans $T(s)$. 

\smallskip
\noindent
On v\'erifie imm\'ediatement qu'un arbre minimax est d'Andr\'e
s'il est \`a la fois croissant et d'Hetyei-Reiner. Notons
$A_n=C_n\cap H\!R_n$ l'ensemble des arbres d'Andr\'e d'ordre~$n$.

\smallskip
On sait d\'enombrer ces quatre familles d'arbres. D'abord,
comme d\'emontr\'e dans le
paragraphe~3, la fonction g\'en\'eratrice exponentielle des nombres
$m_n:=\# M_n$ est donn\'ee par:
$$\displaylines{(1.1)\quad
{\sqrt 2\over 2} {1+(3-2\sqrt 2)\,e^{2\sqrt 2\,u}
\over 1-(3-2\sqrt 2)\,e^{2\sqrt 2\,u}}
=\sum_{n\ge 0}{u^n\over n!}m_n\hfill\cr
\hfill{}=1+u+{u^2\over 2!}4+{u^3\over 3!}20+{u^4\over 4!}128+
{u^5\over 5!}1024+{u^6\over 6!}9856+\cdots\quad\cr}
$$
Ensuite, les arbres d'Hetyei-Reiner et les arbres croissants sont en
bijection avec les permutations, soit
$$
\#\,H\!R_n=n!\quad{\rm et}\quad \#\,C_n=n!,\leqno(1.2)
$$
un r\'esultat \'etabli par Hetyei-Reiner [HeRe98] pour les arbres de
m\^eme nom et un r\'esultat classique pour les arbres
croissants (voir, par exemple, [FoSch71]). Nous rappelons \`a la fin
du paragraphe~2 comment \'etablir g\'eom\'etriquement ces deux
faits.

Rappelons, enfin, que les nombres {\it tangents}
et {\it s\'ecants} $E_n$ sont d\'efinis comme les coefficients 
du d\'evelop\-pe\-ment de Taylor
$$
\sec u+\tan u=1+\sum_{n\ge 1}{u^{n}\over
n!}E_{n}=1+u+{u^2\over 2!}+{u^3\over 3!}2+{u^4\over 4!}5+
{u^5\over 5!}16+\cdots
$$
et que les arbres d'Andr\'e sont justement d\'enombr\'es par ces
nombres classiques 
$$
\#\,A_n=E_n,\leqno(1.3)
$$
un r\'esultat \'etabli dans [FoSch71].
Le but principal de cet article est de d\'emontrer le th\'eor\`eme
suivant.

\proclaim Th\'eor\`eme 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\'et\'e que chaque
$G_n$-orbite d'un arbre
minimax~$T\in M_n$ contient exactement un seul arbre croissant
$\bfc\,T\in C_{n}$ et chaque $R_n$-orbite un seul arbre de
Hetyei-Reiner 
$\bfr\,T\in H\!R_{n}$. De plus, les
surjections $\bfc$ et $\bfr$ ainsi d\'efinies ont la propri\'et\'e que le
diagramme suivant est commutatif:
$$\def\normalbaselines{\baselineskip 20pt\lineskip3pt
\lineskiplimit3pt}
\def\mapright#1{\smash{\mathop{\longrightarrow}\limits^{#1}}}
\def\mapdown#1{\Big\downarrow
\rlap{$\vcenter{\hbox{$\scriptstyle#1$}}$}}
\matrix{M_{n}&\mapright{\bfc}&C_{n}\cr
\mapdown{\bfr}&&\mapdown{\bfr}\cr
H\!R_{n}&\mapright{\bfc}&A_{n}\cr}
\leqno(1.4)$$
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 \'egalement tous~$k$ feuilles.

Pour comparer notre contribution \`a celles apport\'ees par les
travaux ant\'erieurs, disons que la partie concernant la surjection
$\bfr:C_n\rightarrow A_n$ est due \`a Foata-Strehl
[FoSt74] et celle concernant la surjection $\bfc:H\!R_n\rightarrow
A_n$ est due \`a Hetyei-Reiner [HeRe98]. Il nous a paru essentiel
de rassembler ces r\'esultats dans un m\^eme mod\`ele et
donc d'imaginer une classe d'arbres qui englobe \`a la fois les
arbres croissants et ceux d'Hetyei-Reiner, sur lesquels on
peut prolonger l'action des groupes jusque l\`a limit\'ee aux seuls
arbres croissants ou d'Hetyei-Reiner. D'o\`u l'introduction des
arbres minimax.

\goodbreak

Comme d\'ecrit dans le paragraphe~3, on peut introduire deux
statistiques ``$\hr$" et ``$\cro$" sur~$M_n$ qui ont la
propri\'et\'e que $\hr T=0$ (resp. $\cro T=0$) si $T$ est de
Hetyei-Reiner (resp. croissant) et donc $\hr T=\cro T=0$ si $T$
est d'Andr\'e. Soit $m_{n,k}(p,q)$ le polyn\^ome g\'en\'erateur de
$M_{n,k}$ par la statistique bivari\'ee $(\hr, \cro)$. A l'aide
d'une construction combinatoire appropri\'ee, on \'etablit au
paragraphe~3 une r\'ecurrence pour les polyn\^omes
$m_{n,k}(p,q)$. On en d\'eduit, d'abord, une expression pour la
fonction g\'en\'eratrice exponentielle des arbres minimax par la
statistique trivari\'ee $(\hbox{nombre de feuilles}, \hr,\cro)$ (voir
identit\'e (3.6)), ensuite, celle des nombres $m_n=\#\,M_n$
annonc\'ee en (1.1).

Les {\it op\'erations-compl\'ements} et les
{\it op\'erations-retournements} sont \'etu\-di\'es dans les
paragraphes~4 et~5. On \'etablit, en particulier, leur propri\'et\'es
de commutativit\'e. Dans le paragraphe~6, \`a l'aide de ces
op\'erations, on construit les deux surjections~$\bfc$ et~$\bfr$
du diagramme~(1.4), terminant ainsi la d\'emonstration du
Th\'eor\`eme~1.1.

Notons $d_{n,k}$ le cardinal de $A_{n,k}$, ou encore le nombre
d'arbres d'Andr\'e ayant~$k$ feuilles. Les polyn\^omes
$D_n(t)=\sum_{k} d_{n,k} t^k$ $(n\ge 0)$, appel\'es {\it
polyn\^omes d'Andr\'e}, ont \'et\'e introduits et \'etudi\'es dans
[FoSch73]. Dans le paragraphe~7, nous donnons deux nouvelles
m\'ethodes pour obtenir leur fonction g\'en\'eratrice exponentielle.
Enfin, dans le paragraphe~8, nous indiquons comment d\'efinir
d'autres op\'erations-compl\'ements, comme celle introduite par
Hetyei et Reiner [HeRe98], et d'autres
op\'erations-retourne\-ments, qui conduisent \`a  des r\'esultats
analogues.

Le pr\'esent article s'inscrit dans ce programme qui se propose de
trouver des interpr\'etations 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\`ere
interpr\'etation des nombres d'Euler remonte \`a Andr\'e [An79,
An81] en termes de {\it permutations alternantes}. On sait que ce
mod\`ele permet un passage \'el\'egant au $q$-calcul (voir
[AnGe78, Fo81]), mais ne permet pas, a priori, d'autres
extensions int\'eressantes. 

Dans [FoSch71, FoSch73], on a
reconsid\'er\'e l'\'equation diff\'erentielle:
$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=\sum_{n\ge
1} (u^n/n!)\,D_{n-1}$, on a pu faire
appara\^\i tre les coefficients $D_n$ comme des poly\-n\^omes 
$D_n=D_n(t)$ $(n\ge 0)$, qui sont pr\'ecis\'ement les polyn\^omes
d'Andr\'e, dont on a parl\'e plus haut. De plus, ceux-ci sont
apparus tr\`es naturellement comme les polyn\^omes
g\'en\'erateurs d'objets combinatoires, qui ne sont plus les
permutations alternantes, mais les 
permutations dites {\it d'Andr\'e} par la statistique ``nombres de
pics." 

\goodbreak
Plus tard, Foata et Strehl [FoSt74, FoSt76] ont fait appara\^\i tre
ces permutations d'An\-dr\'e comme des syst\`emes de
repr\'esentants d'orbites de groupes agissant sur l'ensemble de
toutes les permutations. Ils ont montr\'e que l'action de ces
groupes est mieux per\c cue g\'eom\'etriquement, si on les fait
agir non pas sur les permutations, mais sur des arbres binaires.

Les permutations et les polyn\^omes d'Andr\'e ont trouv\'e une
nouvelle application dans l'\'etude de la variation dite $cd$ de
certains ensembles partiellement ordonn\'es (``posets"), une \'etude
entreprise par Purtill [Pu93], Stanley [St94], qui a pu, en
particulier, faire usage des polyn\^omes d'Andr\'e {\it non
commutatifs}, par Sundaram [Su94] et plus r\'ecemment par
Hetyei [He96].


\bigskip
\centerline{\bf 2. Conventions et notations}

\medskip
Pour fixer les id\'ees, on consid\`ere que chaque arbre binaire $T$ est
des\-sin\'e dans le plan euclidien: la racine est d'ordonn\'ee~0, les fils
de la racine sont d'ordonn\'ee~1, les petits-fils d'ordonn\'ee~2, etc.
On convient que tous les sommets dans l'arbre \`a gauche~$T_g(s)$
(resp. dans l'arbre \`a droite~$T_d(s)$) ont une abs\-cisse {\it
inf\'erieure} (resp. {\it sup\'erieure}) \`a celle de~$s$. En fait, on
convient que la racine de l'arbre est \`a l'origine $(0,0)$, le fils
\`a gauche de la racine en $(-1,1)$ et le fils \`a droite en
$(1,1)$, les petits-fils respectivement en $(-3/2,2)$, $(-1/2,2)$,
$(1/2,2)$, $(3/2,2)$, les arri\`ere-petits-fils respectivement en
$(-7/4 ,3)$, $(-5/4,3)$, \dots~, $(7/4,3)$, etc. Avec cette
convention, tous les sommets de l'arbre ont des abscisses
{\it distinctes}. 

Si l'arbre binaire~$T$ a $n$ sommets, on ordonne ces 
$n$ sommets de la fa\c con suivante: la
racine est le plus petit sommet, puis vient le fils \`a gauche de
la racine, puis le fils \`a droite, puis le fils \`a gauche du fils
\`a gauche, etc. On note $<_T$ cet ordre total. 


\midinsert
\newbox\boxarbrequatre
\newbox\boxarbredixsept

\setbox\boxarbrequatre=\vbox{\vskip
25mm\offinterlineskip 
%
%
\centerput(0,-2){$\scriptstyle 1$}
\centerput(10,2){$\scriptstyle 4$}
\centerput(15,7){$\scriptstyle 8$}
\centerput(18,12){$\scriptstyle 9$}
\centerput(5,7){$\scriptstyle 10$}
\centerput(-10,2){$\scriptstyle 2$}
\centerput(-15,7){$\scriptstyle 3$}
\centerput(-19,13){$\scriptstyle 6$}
\centerput(-11.5,13){$\scriptstyle 5$}
\centerput(-10,18){$\scriptstyle 7$}
%
\centerput(0,-10){$\scriptstyle 1$}
\centerput(10,-10){$\scriptstyle 4$}
\centerput(15,-10){$\scriptstyle 8$}
\centerput(18,-10){$\scriptstyle 9$}
\centerput(5,-10){$\scriptstyle 10$}
\centerput(-9,-10){$\scriptstyle 2$}
\centerput(-16,-10){$\scriptstyle 3$}
\centerput(-19,-10){$\scriptstyle 6$}
\centerput(-13.5,-10){$\scriptstyle 5$}
\centerput(-11,-10){$\scriptstyle 7$}
%
\centerput(-26,10){$T_1={}$}
\centerput(-26,-10){$\pi(T_1)={}$}
%
\segment(0,0)\dir(2,1)\long{10}
\segment(10,5)\dir(1,1)\long{5}
\segment(15,10)\dir(1,2)\long{2.5}
\segment(10,5)\dir(-1,1)\long{5}
%
\segment(0,0)\dir(-2,1)\long{10}
\segment(-10,5)\dir(-1,1)\long{5}
\segment(-15,10)\dir(-1,2)\long{2.5}
\segment(-15,10)\dir(1,2)\long{2.5}
\segment(-12.5,15)\dir(1,4)\long{1.25}
\segment(-20,-5)\dir(1,0)\long{40}}


\setbox\boxarbredixsept=\vbox{\vskip
25mm\offinterlineskip 
%
\centerput(0,-2){$\scriptstyle 1$}
\centerput(10,2){$\scriptstyle 10$}
\centerput(15,7){$\scriptstyle 4$}
\centerput(8,12){$\scriptstyle 9$}
\centerput(5,7){$\scriptstyle 8$}
\centerput(-10,2){$\scriptstyle 2$}
\centerput(-5,7){$\scriptstyle 3$}
\centerput(-1,13){$\scriptstyle 7$}
\centerput(-9,13){$\scriptstyle 6$}
\centerput(-0,18){$\scriptstyle 5$}
%
\centerput(1,-10){$\scriptstyle 1$}
\centerput(12,-10){$\scriptstyle 10$}
\centerput(15,-10){$\scriptstyle 4$}
\centerput(8,-10){$\scriptstyle 9$}
\centerput(5,-10){$\scriptstyle 8$}
\centerput(-10,-10){$\scriptstyle 2$}
\centerput(-5,-10){$\scriptstyle 3$}
\centerput(-3,-10){$\scriptstyle 7$}
\centerput(-7.5,-10){$\scriptstyle 6$}
\centerput(-1,-10){$\scriptstyle 5$}
%
\centerput(-17,10){$T_2={}$}
\centerput(-17,-10){$\pi(T_2)={}$}
%
\segment(0,0)\dir(2,1)\long{10}
\segment(10,5)\dir(1,1)\long{5}
\segment(5,10)\dir(1,2)\long{2.5}
\segment(10,5)\dir(-1,1)\long{5}
%
\segment(0,0)\dir(-2,1)\long{10}
\segment(-10,5)\dir(1,1)\long{5}
\segment(-5,10)\dir(1,2)\long{2.5}
\segment(-5,10)\dir(-1,2)\long{2.5}
\segment(-2.5,15)\dir(1,4)\long{1.25}
\segment(-20,-5)\dir(1,0)\long{40}
}


$$\hskip1cm\box\boxarbrequatre\hskip 5cm \box\boxarbredixsept$$

\bigskip\bigskip
\centerline{Fig. 3}

\endinsert
Disposons dans le plan euclidien les sommets d'un arbre minimax
comme indiqu\'e pr\'ec\'edemment et consid\'erons la projection
orthogonale~$\pi$ sur un axe horizontal des \'etiquettes de cet
arbre. Alors $\pi$ envoie {\it bijectivement} l'ensemble des arbres
croissants (resp. de Hetyei-Reiner) ayant~$n$ sommets sur le
groupe des permutations de la suite $1,2,\ldots,n$. Voir les
d\'emonstrations dans [FoSch71, HeRe98]. Ceci montre, en
particulier, que $\card  C_{n}=
\card H\!R_{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 {\it permutation d'Andr\'e\/} l'image par la
projection~$\pi$ d'un arbre d'Andr\'e. On trouve dans [FoSch73]
une autre d\'efinition des permutations d'Andr\'e. On note
$M_{n,k}$ (resp.
$C_{n,k}$, resp.
$H\!R_{n,k}$, resp.
$A_{n,k}$) le sous-ensemble de $M_n$ (resp. $C_{n}$, resp.
$H\!R_{n}$, resp. $A_n$) form\'e par tous les arbres qui ont~$k$
feuilles.

\bigskip
\centerline{\bf 3. D\'enombrement des arbres minimax}

\medskip
Dans un arbre minimax~$T$, soit $s$ un sommet
d'\'etiquette~$a$. On note $T\{a\}$ (resp. $T_g\{a\}$, resp. $T_g\{a\}$)
l'{\it ensemble} de toutes les \'etiquettes apparaissant dans le
sous-arbre $T(s)$ (resp. $T_g(s)$, resp. $T_d(s)$). Si
l'\'etiquette~$a$ d'un sommet {\it int\'erieur}~$s$ est minimum
(resp. maximum) dans le sous-arbre~$T(s)$, on dit que le
sommet~$s$ est de {\it premi\`ere esp\`ece}, si le sous-arbre
\`a droite $T_d(s)$ est non vide et contient le sommet
d'\'etiquette
$\max T\{a\}$ (resp. $\min T\{a\}$). Un sommet int\'erieur, qui
n'est pas de premi\`ere esp\`ece, est dit de {\it seconde esp\`ece}.
Notons qu'un sommet int\'erieur simple~$s$ est de premi\`ere
esp\`ece si et seulement si $T_g(s)$ est vide et $T_d(s)$ non vide.

Par exemple, dans l'arbre minimax repr\'esent\'e dans Fig.~1, le
sommet~3 est de premi\`ere esp\`ece (l'\'etiquette maximum ``7" se
trouve \`a droite) et le sommet~10 est de seconde esp\`ece
(l'\'etiquette minimum ``4" se trouve \`a gauche). 

On d\'esigne par $\hr(T)$ le nombre de sommets int\'erieurs {\it de
seconde esp\`ece} d'un arbre minimax~$T$. Un arbre de
Hetyei-Reiner~$T$ est encore un arbre satisfaisant $\hr(T)=0$.
Notons $\cro(T)$ le nombre de sommets int\'erieurs~$s$ d'un arbre
minimax~$T$ qui sont d'\'etiquette maximum, 
(c'est-\`a-dire dont l'\'etiquette est
maximum dans le sous-arbre $T(s)$ de racine~$s$) 
de sorte qu'un arbre
croissant~$T$ est un arbre satisfaisant $\cro(T)=0$ et qu'un
arbre d'Andr\'e est tel que $\hr(T)=\cro(T)=0$. D\'esignons par
$$
m_{n,k}(p,q):=\sum_{T\in M_{n,k}} p^{\hr(T)}\,q^{\cro(T)},
\leqno(3.1)
$$
la fonction g\'en\'eratrice des arbres minimax d'ordre~$n$
ayant~$k$ feuilles par la statistique bivari\'ee $(\hr,\cro)$.


\proclaim Proposition 3.1. Les polyn\^omes $m_{n,k}(p,q)$
satisfont la r\'ecurrence:
$$
\displaylines{m_{1,1}(p,q)=1,\quad m_{n,k}(p,q)=0\ 
\ (k<0\ {\rm ou}\ n+1<2k) ;\cr
{\rm (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)\hfill\cr
({\rm pour}\ 1\le k\le \lceil
(n+1)/2\rceil\ {\rm et}\ n\ge 1).\cr}
$$

{\it D\'emonstration}.\quad
Si un arbre minimax d'ordre $n$ a~$k$ feuilles, le nombre
de ses sommets int\'erieurs {\it doubles} est forc\'ement \'egal \`a
$(k-1)$ et le nombre de ses sommets int\'erieurs {\it simples}
est donc \'egal \`a $n-k-(k-1)=n-2k+1$. Par cons\'equent, 
le facteur $n+3-2k=n-(k-1)-(k-2)$, qui intervient dans (3.1),
est le nombre de sommets int\'erieurs simples d'un arbre minimax
d'ordre~$n$ ayant $(k-1)$ feuilles. 

Partons donc d'un tel arbre $T$ et consid\'erons l'un des
$(n+3-2k)$ sommets int\'erieurs simples~$s$ de cet arbre.
Soit~$b$ son \'etiquette. Dans le chemin unique qui m\`ene de
la racine de l'arbre au sommet~$s$, il y a des sommets~$s_i$
qui sont d'\'etiquette maximum et des sommets qui sont
d'\'etiquette minimum. D\'esignons par $(s_1,s_2,\ldots, s_m)$ la
suite des sommets int\'erieurs d'\'eti\-quette maximum,
lors\-qu'on parcourt le chemin de la racine vers~$s$ et notons
$(a_1,a_2,\ldots, a_m)$ la suite (forc\'ement d\'ecroissante) de
leurs \'etiquettes. Notons encore
$s'$ l'unique fils de~$s$, d'\'etiquette~$b'$.

Dans une premi\`ere \'etape, on remplace les \'etiquettes~$a_1$,
$a_2$, \dots~, $a_{m-1}$, $a_m$ par $(n+1)$, $a_1$, 
\dots~, $a_{m-2}$, $a_{m-1}$, respectivement, puis on adjoint
une feuille \'etiquet\'ee~$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 \'etiquet\'ee~$a_m$ et le
sous-arbre $T(s')$ forment les sous-arbres incidents au
sommet~$s$. Voir Fig.~4, o\`u l'on a consid\'er\'e quatre cas,
suivant que l'\'etiquette~$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 sous-arbre \`a droite (cas (1) et (2)) ou
le sous-arbre \`a gauche (cas (3) et (4)) du sommet~$s$. Les
\'etiquettes sont \'ecrites entre crochets et l'ascendance du
sommet~$s$ (la partie basse) est repr\'esent\'ee par un trait
vertical.

Si l'\'etiquette~$b$ de~$s$ est {\it minimum} (cas (1) et (3)),
dans une seconde \'etape, on \'echange les positions des
sous-arbres $T(s')$ et de la feuille \'etiquet\'ee~$a_m$. Soit
$T''$ l'arbre obtenu. Si l'\'etiquette~$b$ est maximum, on pose
simplement: $T'':=T'$. Par ce proc\'ed\'e, on obtient un arbre
minimax $T''$ d'ordre~$(n+1)$, ayant $k$ feuilles. On observe que
dans le passage de~$T$ \`a~$T''$, le nombre de sommets
int\'erieurs n'est pas modifi\'e (on a simplement ajout\'e une
feuille), ni leur esp\`ece et que le nombre de sommets int\'erieurs
d'\'etiquette maximum n'a pas chang\'e. Ainsi
$\hr(T'')=\hr(T)$ et $\cro(T'')=\cro(T)$. 

Par exemple, dans le
cas~(1) (resp. cas~(3)), le sommet~$s$ est de premi\`ere
(resp. de seconde) esp\`ece dans~$T$ et reste de premi\`ere
(resp. de seconde) esp\`ece dans~$T''$.

\midinsert
\newbox\boxarbreun
\newbox\boxarbredeux
\newbox\boxarbretrois

\setbox\boxarbreun=\vbox{\vskip
28mm\offinterlineskip 
\segment(8,8)\dir(1,1)\long{16}
\segment(8,0)\dir(0,1)\long{8}
\segment(16,16)\dir(-1,1)\long{8}
\segment(8,24)\dir(1,0)\long{16}
\centerput(8,7){$\times$}
\centerput(16,15){$\times$}
\centerput(14,-1){$[a_m]$}
\centerput(12,7){$[b]$}
\centerput(20,14){$[b']$}
\centerput(5,7){$s$}
\centerput(13,14){$s'$}
\centerput(8,-1){$\bullet$}\centerput(28,10){$\mapsto$}
}

\setbox\boxarbredeux=\vbox{\vskip
28mm\offinterlineskip 
\segment(8,8)\dir(1,1)\long{16}
\segment(8,0)\dir(0,1)\long{8}
\segment(16,16)\dir(-1,1)\long{8}
\segment(8,24)\dir(1,0)\long{16}
\segment(8,8)\dir(-1,1)\long{8}
\centerput(0,15){$\bullet$}
\centerput(-5,15){$[a_m]$}
\centerput(8,7){$\times$}
\centerput(16,15){$\times$}
\centerput(14,-1){$[a_{m-1}]$}
\centerput(12,7){$[b]$}
\centerput(20,14){$[b']$}
\centerput(5,7){$s$}
\centerput(13,14){$s'$}
\centerput(8,-1){$\bullet$}\centerput(28,10){$\mapsto$}
}

\setbox\boxarbretrois=\vbox{\vskip
28mm\offinterlineskip 
\segment(8,8)\dir(1,1)\long{8}
\segment(8,0)\dir(0,1)\long{8}
\segment(-8,24)\dir(1,0)\long{16}
\segment(8,8)\dir(-1,1)\long{16}
\segment(0,16)\dir(1,1)\long{8}
\centerput(0,15){$\bullet$}
\centerput(-4,13){$[b']$}
\centerput(8,7){$\times$}
\centerput(16,15){$\bullet$}
\centerput(14,-1){$[a_{m-1}]$}
\centerput(12,7){$[b]$}
\centerput(21,14){$[a_m]$}
\centerput(5,7){$s$}
\centerput(13,14){$s'$}
\centerput(8,-1){$\bullet$}
}

\centerline{\box\boxarbreun\hskip4cm\box\boxarbredeux\hskip4cm
\box\boxarbretrois\hskip2cm}

\bigskip
\centerline{cas (1)}

\bigskip
\setbox\boxarbreun=\vbox{\vskip
28mm\offinterlineskip 
\segment(8,0)\dir(0,1)\long{8}
\segment(8,8)\dir(1,1)\long{16}
\segment(16,16)\dir(-1,1)\long{8}
\segment(8,24)\dir(1,0)\long{16}
\centerput(8,7){$\bullet$}
\centerput(16,15){$\times$}
\centerput(14,-1){$[a_{m-1}]$}
\centerput(18,7){$[b]=[a_m]$}
\centerput(20,14){$[b']$}
\centerput(5,7){$s$}
\centerput(13,14){$s'$}
\centerput(8,-1){$\bullet$}\centerput(28,10){$\mapsto$}
}

\setbox\boxarbredeux=\vbox{\vskip
28mm\offinterlineskip 
\segment(8,0)\dir(0,1)\long{8}
\segment(8,8)\dir(1,1)\long{16}
\segment(16,16)\dir(-1,1)\long{8}
\segment(8,24)\dir(1,0)\long{16}
\segment(8,8)\dir(-1,1)\long{8}
\centerput(0,15){$\bullet$}
\centerput(-5,15){$[a_m]$}
\centerput(8,7){$\bullet$}
\centerput(16,15){$\times$}
\centerput(14,-1){$[a_{m-2}]$}
\centerput(15,7){$[a_{m-1}]$}
\centerput(20,14){$[b']$}
\centerput(5,7){$s$}
\centerput(13,14){$s'$}
\centerput(8,-1){$\bullet$}
}

\centerline{\box\boxarbreun\hskip4cm\box\boxarbredeux\hskip5.5cm}

\bigskip
\centerline{cas (2)\hskip 4cm}

\bigskip

\setbox\boxarbreun=\vbox{\vskip
28mm\offinterlineskip 
\segment(-8,8)\dir(-1,1)\long{16}
\segment(-8,0)\dir(0,1)\long{8}
\segment(-16,16)\dir(1,1)\long{8}
\segment(-8,24)\dir(-1,0)\long{16}
\centerput(-8,7){$\times$}
\centerput(-16,15){$\times$}
\centerput(-14,-1){$[a_m]$}
\centerput(-12,7){$[b]$}
\centerput(-20,14){$[b']$}
\centerput(-5,7){$s$}
\centerput(-13,15){$s'$}
\centerput(-8,-1){$\bullet$}\centerput(10,10){$\mapsto$}
}

\setbox\boxarbredeux=\vbox{\vskip
28mm\offinterlineskip 
\segment(-8,8)\dir(-1,1)\long{16}
\segment(-8,0)\dir(0,1)\long{8}
\segment(-16,16)\dir(1,1)\long{8}
\segment(-8,24)\dir(-1,0)\long{16}
\segment(-8,8)\dir(1,1)\long{8}
\centerput(0,15){$\bullet$}
\centerput(5,15){$[a_m]$}
\centerput(-8,7){$\times$}
\centerput(-16,15){$\times$}
\centerput(-14,-1){$[a_{m-1}]$}
\centerput(-12,7){$[b]$}
\centerput(-20,14){$[b']$}
\centerput(-5,7){$s$}
\centerput(-13,15){$s'$}
\centerput(-8,-1){$\bullet$}\centerput(10,10){$\mapsto$}
}

\setbox\boxarbretrois=\vbox{\vskip
28mm\offinterlineskip 
\segment(-8,8)\dir(-1,1)\long{8}
\segment(-8,0)\dir(0,1)\long{8}
\segment(-8,24)\dir(1,0)\long{16}
\segment(-8,8)\dir(1,1)\long{16}
\segment(0,16)\dir(-1,1)\long{8}
\centerput(0,15){$\bullet$}
\centerput(4,13){$[b']$}
\centerput(-8,7){$\times$}
\centerput(-16,15){$\bullet$}
\centerput(-14,-1){$[a_{m-1}]$}
\centerput(-12,7){$[b]$}
\centerput(-21,14){$[a_m]$}
\centerput(-5,7){$s$}
\centerput(-13,15){$s'$}
\centerput(-8,-1){$\bullet$}
}

\centerline{\hskip2cm\box\boxarbreun\hskip4cm\box\boxarbredeux\hskip4cm
\box\boxarbretrois}


\bigskip
\centerline{cas (3)}

\bigskip

\setbox\boxarbreun=\vbox{\vskip
28mm\offinterlineskip 
\segment(-8,8)\dir(-1,1)\long{16}
\segment(-8,0)\dir(0,1)\long{8}
\segment(-16,16)\dir(1,1)\long{8}
\segment(-8,24)\dir(-1,0)\long{16}
\centerput(-8,7){$\bullet$}
\centerput(-16,15){$\times$}
\centerput(-14,-1){$[a_{m-1}]$}
\centerput(-18,7){$[b]=[a_m]$}
\centerput(-20,14){$[b']$}
\centerput(-5,7){$s$}
\centerput(-13,15){$s'$}
\centerput(-8,-1){$\bullet$}\centerput(10,10){$\mapsto$}
}

\setbox\boxarbredeux=\vbox{\vskip
28mm\offinterlineskip 
\segment(-8,8)\dir(-1,1)\long{16}
\segment(-8,0)\dir(0,1)\long{8}
\segment(-16,16)\dir(1,1)\long{8}
\segment(-8,24)\dir(-1,0)\long{16}
\segment(-8,8)\dir(1,1)\long{8}
\centerput(0,15){$\bullet$}
\centerput(5,15){$[a_m]$}
\centerput(-8,7){$\bullet$}
\centerput(-16,15){$\times$}
\centerput(-14,-1){$[a_{m-2}]$}
\centerput(-15,7){$[a_{m-1}]$}
\centerput(-20,14){$[b']$}
\centerput(-5,7){$s$}
\centerput(-13,15){$s'$}
\centerput(-8,-1){$\bullet$}
}

\centerline{\box\boxarbreun\hskip4cm\box\boxarbredeux\hskip2cm}



\bigskip
\centerline{cas (4)\hskip 4cm}

\bigskip
\centerline{(A gauche, l'arbre~$T$ ; \`a l'extr\^eme
droite, la partie correspondante dans~$T''$.)}
\centerline{(L'ascendance du sommet~$s$ est repr\'esent\'ee par
un trait vertical.)}
\medskip
\centerline{Fig. 4}


\endinsert

Soit maintenant $T$ un arbre minimax d'ordre~$n$ ayant $k$
feuilles et soit~$s$ l'une de ses $k$~feuilles, \'etiquet\'ee~$b$.
On d\'esigne, de m\^eme, par $(s_1,s_2,\ldots, s_m)$ la suite des
sommets int\'erieurs d'\'eti\-quette maximum, lors\-qu'on parcourt
le chemin de la racine vers la feuille et par $(a_1,a_2,\ldots,
a_m)$ la suite de leurs \'etiquettes. On construit alors quatre
arbres minimax d'ordre~$(n+1)$ ayant~$k$ feuilles, $T_1$,
$T_2$, $T_3$, $T_4$, en rempla\c cant tout d'abord les
\'etiquettes~$a_1$, $a_2$, \dots~, $a_{m-1}$, $a_m$ par 
$(n+1)$, $a_1$, \dots~, $a_{m-2}$, $a_{m-1}$, respectivement.

\vfill\eject
Ensuite, on transforme la feuille~$s$ en un sommet int\'erieur
simple, ayant soit un fils \`a gauche~$s_g$, soit un fils \`a 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'\'etiquettes $(b,a_m)$, ou
bien le couple $(a_m,b)$. On obtient bien ainsi les quatre arbres
souhait\'es. On observe qu'en transformant de la sorte la
feuille~$s$ en un somme int\'erieur simple, le mon\^ome
$p^{\hr(T)}q^{\cro(T)}$ est transform\'e en
$p^{\hr(T)}q^{\cro(T)}(p+pq+1+q)
=(1+p)(1+q)p^{\hr(T)}q^{\cro(T)}$, comme indiqu\'e dans la Fig.~5.


\midinsert
\setbox\boxarbre=\vbox{\vskip
15mm\offinterlineskip 
\segment(8,0)\dir(0,1)\long{8}
\centerput(8,-1){$\bullet$}
\centerput(8,7){$-$}
\centerput(13,-2){$[a_m]$}
%\centerput(8,7){$\times$}
\centerput(5,8){$s$}
\centerput(11,8){$[b]$}
}

\centerline{\box\boxarbre\hskip 1cm}

\medskip

\setbox\boxarbreun=\vbox{\vskip
25mm\offinterlineskip 
\segment(8,0)\dir(0,1)\long{8}
\segment(8,8)\dir(-1,1)\long{8}
\centerput(8,-1){$\bullet$}
\centerput(15,-2){$[a_{m-1}]$}
\centerput(8,7){$-$}
\centerput(4,7){$s$}
\centerput(11,8){$[b]$}
\centerput(0,15){$\bullet$}
\centerput(6,15){$[a_m]$}
\centerput(-3,15){$s_g$}
\centerput(11,-8){$T_1$}
\centerput(11,-12){$p$}
}

\setbox\boxarbredeux=\vbox{\vskip
25mm\offinterlineskip 
\segment(8,0)\dir(0,1)\long{8}
\segment(8,8)\dir(-1,1)\long{8}
\centerput(8,-1){$\bullet$}
\centerput(15,-2){$[a_{m-1}]$}
\centerput(8,7){$-$}
\centerput(4,7){$s$}
\centerput(12,8){$[a_m]$}
\centerput(0,15){$\bullet$}
\centerput(4,15){$[b]$}
\centerput(-3,15){$s_g$}
\centerput(11,-8){$T_2$}
\centerput(11,-12){$pq$}
}

\setbox\boxarbretrois=\vbox{\vskip
25mm\offinterlineskip 
\segment(8,0)\dir(0,1)\long{8}
\segment(8,8)\dir(1,1)\long{8}
\centerput(8,-1){$\bullet$}
\centerput(15,-2){$[a_{m-1}]$}
%\centerput(8,7){$\times$}
\centerput(4,7){$s$}
\centerput(8,7){$-$}
\centerput(12,6){$[b]$}
\centerput(16,15){$\bullet$}
\centerput(21,15){$[a_m]$}
\centerput(12,15){$s_d$}
\centerput(11,-8){$T_3$}
\centerput(11,-12){$1$}
}

\setbox\boxarbrequatre=\vbox{\vskip
25mm\offinterlineskip 
\segment(8,0)\dir(0,1)\long{8}
\segment(8,8)\dir(1,1)\long{8}
\centerput(8,-1){$\bullet$}
\centerput(15,-2){$[a_{m-1}]$}
%\centerput(8,7){$\times$}
\centerput(4,7){$s$}
\centerput(8,7){$-$}
\centerput(13,6){$[a_m]$}
\centerput(16,15){$\bullet$}
\centerput(20,15){$[b]$}
\centerput(12,15){$s_d$}
\centerput(11,-8){$T_4$}
\centerput(11,-12){$q$}}

\centerline{\box\boxarbreun\hskip2.7cm\box\boxarbredeux
\hskip2.7cm\box\boxarbretrois\hskip2.7cm\box\boxarbrequatre
\hskip1.8cm}

\vskip1.5cm
\centerline{Fig. 5}

\endinsert

La construction ainsi d\'ecrite est parfaitement r\'eversible.
Partons d'un arbre minimax~$T$ d'ordre $(n+1)$ ayant~$k$
feuilles ; on pose $a_1:=n+1$ ; et pour chaque $i\ge 2$ on
d\'efinit $a_i:=\max(T[a_{i-1}]\setminus \{a_{i-1}\})$, si ce
dernier ensemble est non vide. Soit
$m\ge 1$ le plus petit entier tel que
$T[a_m]\setminus \{a_m\}$ est vide. On construit ainsi une suite
strictement {\it d\'ecroissante} d'\'etiquettes 
$(a_1=n+1>a_2>\cdots>a_m)$. Soit $(s_1,s_2,\ldots, s_m)$ la
suite des sommets de~$T$ ayant ces \'etiquettes. Alors $s_m$ est
forc\'ement une feuille de l'arbre. Soit~$s$ le sommet
int\'erieur auquel elle est incidente. Selon que~$s$ est double ou
simple, on applique, en sens inverse, l'algorithme d\'ecrit dans la
Fig.~4 ou dans la Fig.~5.\qed

\medskip
Dans [FoSch73], on a not\'e $d_{n,k}$ le cardinal
de~$A_{n,k}$, \`a savoir le nombre d'arbres {\it d'Andr\'e}
d'ordre~$n$ ayant~$k$ feuilles et on a d\'emontr\'e que ces
nombres satisfaisaient la r\'ecurrence:
$$
\displaylines{
\rlap{(3.3)}\hfill 
d_{1,1}=1,\quad d_{n,k}=0\ 
\ (k<0\ {\rm ou}\ n+1<2k) ;\hfill\cr
d_{n+1,k}=k\,d_{n,k}+(n+3-2k)d_{n,k-1}\quad
(1\le k\le \lceil (n+1)/2\rceil\ {\rm et}\ n\ge 1).\cr
}
$$
Dans la table de
la Fig.~6, apparaissent les premi\`eres valeurs de ces nombres.
La comparaison de cette r\'ecurrence avec (3.2)
fournit imm\'ediate\-ment la relation:
$$
m_{n,k}(p,q)=(1+p)^{n-k}(1+q)^{n-k}\,d_{n,k}.\leqno(3.4)
$$
Notons que $\sum_k d_{n,k}=E_n$, le nombre tangent ou s\'ecant,
selon que $n$ est impair ou pair, comme d\'ej\`a \'etabli dans
[FoSch73]. La somme $\sum_k m_{n,k}(1,1)$ donne le nombre
d'arbres minimax~$m_n$ d'ordre~$n$; les premi\`eres valeurs
apparaissent dans la Fig.~7.
\midinsert

$$
\vbox{\halign{\vrule\quad \hfil#\quad \vrule
&\strut\quad \hfil$#$\hfil
&\quad \hfil$#$\hfil
&\quad \hfil$#$\hfil
&\quad \hfil$#$\hfil\quad \vrule&\quad \hfil$#$\hfil\quad \vrule\cr
\noalign{\hrule}
k={}&1&2&3&4&E_n\cr
\noalign{\hrule}
n=1&1&&&&1\cr
2&1&&&&1\cr
3&1&1&&&2\cr
4&1&4&&&5\cr
5&1&11&4&&16\cr
6&1&26&34&&61\cr
7&1&57&180&34&272\cr
8&1&120&768&496&1385\cr
\noalign{\hrule}
}}
$$
\centerline{Table des $d_{n,k}$}
\centerline{Fig. 6}
$$
\vbox{\halign{\vrule\quad \hfil$#$\quad \vrule
&\strut\quad \hfil$#$\hfil
&\quad \hfil$#$\hfil
&\quad \hfil$#$\hfil
&\quad \hfil$#$\hfil
&\quad \hfil$#$\hfil
&\quad \hfil$#$\hfil
&\quad \hfil$#$\hfil
&\quad \hfil$#$\hfil\quad \vrule\cr
\noalign{\hrule}
n&1&2&3&4&5&6&7&8\cr
\noalign{\hrule}
m_n&1&4&20&128&1024&9856&110720&1421312\cr
\noalign{\hrule}
}}
$$
\centerline{Table des $m_{n}$}
\centerline{Fig. 7}
\endinsert

Le polyn\^ome $D_n(t):=\sum_k d_{n,k}t^k$ est le polyn\^ome
g\'en\'erateur des arbres d'Andr\'e d'ordre~$n$ par nombre de
feuilles, ou, en utilisant la projection~$\pi$ d\'ecrite \`a la fin du
paragraphe~2, le polyn\^ome g\'en\'erateur des permutations
d'Andr\'e d'ordre~$n$ par nombre de pics. On appelle ces
poly\-n\^omes les {\it polyn\^omes d'Andr\'e}. Dans [FoSch73],
formule (2.14), on trouve l'expression de la fonction g\'en\'eratrice
exponentielle de ces polyn\^omes, \`a savoir:
$$
\sum_{n\ge 0} D_n(t){u^n \over n!}
=r(t){1+w(t)e^{r(t)u}\over 1-w(t)e^{r(t)u}},\leqno(3.5)
$$
o\`u $r(t):=(1-2t)^{1/2}$, $w(t):=(1-r)/(1+r)$. Deux autres
nouvelles d\'emonstrations de ce r\'esultat sont propos\'ees dans le
dernier paragraphe de cet article. 

Soit $f(T)$ le nombre de feuilles d'un arbre minimax. Si l'on
d\'esigne par $M_n(t,p,q)$ la fonction g\'en\'eratrice des arbres
minimax d'ordre~$n$ par la statistique trivari\'ee
$(f,\hr,\cro)$, on d\'eduit de (3.4):
$$
\leqalignno{M_n(t,p,q)&=\sum_kt^k\,m_{n,k}(p,q)\cr
&=\sum_k
t^k\,(1+p)^{n-k}(1+q)^{n-k}\,d_{n,k}\cr
&=(1+p)^n(1+q)^n\sum_k d_{n,k}(t/(1+p)(1+q))^k\cr
&=(1+p)^n(1+q)^n\,D_n(t/(1+p)(1+q)).\cr}
$$
Posons $t':=t/((1+p)(1+q))$ ; de (3.5) on en d\'eduit l'identit\'e:
$$
\sum_{n\ge 0} M_n(t,p,q){u^n \over n!}
=r(t'){1+w(t')e^{r(t')u(1+p)(1+q)}\over
1-w(t')e^{r(t')u(1+p)(1+q)}}.\leqno(3.6)
$$
Dans l'identit\'e (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
$\displaystyle{\sqrt 2\over 2} {1+(3-2\sqrt 2)\,e^{2\sqrt 2\,u}
\over 1-(3-2\sqrt 2)\,e^{2\sqrt 2\,u}}$, ce qui \'etablit la
formule (1.1), qui donne la fonction g\'en\'eratrice exponentielle
des arbres minimax.

\bigskip
\centerline{\bf 4. Les op\'erations-compl\'ements}
\medskip
L'une des op\'erations classiques du groupe sym\'etique ${\cal
S}_m$ est l'{\it op\'era\-tion-compl\'ement}. C'est une involution
qui envoie chaque entier~$i$ $(1\le i\le m)$ sur l'entier
$\bfc_m(i)=m+1-i$. A l'aide de celle-ci, on peut aussi d\'efinir
une op\'eration-compl\'ement sur l'ensemble des arbres minimax.
Les sommets de l'arbre restent invariants, seules certaines de
leurs {\it \'etiquettes} sont modifi\'ees.

Soit $s$ un sommet int\'erieur 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'\'etiquette de~$s$
et $a_1<a_2<\cdots<a_m$ la suite croissante des \'etiquettes du
sous-arbre $T(s)$ de racine~$s$. Par cons\'equent, $a$ est \'egal
\`a~$a_1$ ou \`a $a_m$. On note $\bfc(s)\,T$ l'arbre obtenu
de~$T$ en ne modifiant pas les \'etiquettes des sommets dans
$T\setminus T(s)$, mais en changeant chaque \'etiquette $a_i$ en
$a_{\bfc_m(i)}=a_{m+1-i}$. Si $s$ est une feuille de~$T$, on
pose $\bfc(s)\,T:=T$.

Il est \'evident que l'on a
$$
\bfc(s)\bfc(s)\,T=T \leqno(4.1)
$$
et que l'arbre $\bfc(s)\,T$ est lui-m\^eme minimax. Comme le
sous-arbre
$T\setminus T(s)$ n'est pas modifi\'e par
$\bfc(s)$, on peut \'ecrire symboliquement:
$$
\bfc(s)T:=(T\setminus T(s))+\bfc(s)T(s).\leqno(4.2)
$$
Dans l'exemple de la Fig. 1, soit $s$ le fils \`a droite de la racine
de l'arbre (donc sis en $(1,1)$ avec la convention prise pour la
position des sommets) dont l'\'etiquette est~10. Alors $\bfc(s)T$
est l'arbre repr\'esent\'e dans la Fig.~8.

\midinsert

\setbox\boxarbre=\vbox{\vskip
40mm\offinterlineskip 
\centerput(0,-1){$\bullet$}
\centerput(20,9){$\bullet$}
\centerput(30,19){$\bullet$}
\centerput(35,29){$\bullet$}
\centerput(10,19){$\bullet$}
\centerput(-20,9){$\bullet$}
\centerput(-30,19){$\bullet$}
\centerput(-35,29){$\bullet$}
\centerput(-25,29){$\bullet$}
\centerput(-22.5,39){$\bullet$}
%
\centerput(0,-4){$1$}
\centerput(20,6){$4$}
\centerput(30,16){$9$}
\centerput(35.5,26){$8$}
\centerput(9,16){$10$}
\centerput(-20,6){$2$}
\centerput(-30,16){$3$}
\centerput(-35.5,26){$6$}
\centerput(-24.5,26){$7$}
\centerput(-21.5,36){$5$}
%
\segment(0,0)\dir(2,1)\long{20}
\segment(20,10)\dir(1,1)\long{10}
\segment(30,20)\dir(1,2)\long{5}
\segment(20,10)\dir(-1,1)\long{10}
%
\segment(0,0)\dir(-2,1)\long{20}
\segment(-20,10)\dir(-1,1)\long{10}
\segment(-30,20)\dir(-1,2)\long{5}
\segment(-30,20)\dir(1,2)\long{5}
\segment(-25,30)\dir(1,4)\long{2.5}
}


$$
\box\boxarbre
$$
\medskip
\centerline{Fig. 8}

\endinsert

\proclaim Proposition 4.1. Supposons donn\'es les deux sommets
int\'erieurs $s$ et
$s'$ d'un arbre minimax~$T$. Alors
$$
\bfc(s)\bfc(s')\,T=\bfc(s')\bfc(s)\,T.\leqno(4.3)
$$

{\it D\'emonstration}.\quad
Si les sous-arbres $T(s)$ et $T(s')$ sont disjoints, la relation
(4.3) est \'evidente.  Si les sous-arbres ne sont pas
disjoints, alors forc\'ement 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 \'etiquettes de $T(s)$ sont $a_1<a_2<\cdots
<a_{m}$. Alors les \'etiquettes de $T(s')$ sont $a_{i (1)}<\cdots
<a_{i(m')}$, o\`u $(i(1),\ldots, i(m'))$ est une sous-suite de
$(1,2,\ldots, m)$. Les sommets de~$T$ sont de trois sortes~: les
sommets de $T(s')$, ceux de $T(s)\setminus T(s')$ et ceux de
$T\setminus T(s)$, comme indiqu\'e sch\'ematiquement dans la
Fig.~9.

\midinsert
\newbox\boxarbre

\setbox\boxarbre=\vbox{\vskip
37mm\offinterlineskip 
\segment(0,0)\dir(-1,1)\long{30}
\segment(0,0)\dir(1,1)\long{30}
\segment(0,10)\dir(-1,1)\long{20}
\segment(0,10)\dir(1,1)\long{20}
\segment(-8,18)\dir(1,1)\long{12}
\segment(-30,30)\dir(1,0)\long{60}
\centerput(-8,25){$T(s')$}
\centerput(0,7){$s$}
\centerput(-9,14){$s'$}
\centerput(-33,19){$\left\{\vrule height .9cm depth .9cm width
0cm\right.$ }
\centerput(-39,19){$T(s)$}
\centerput(0,9){$\bullet$}
\centerput(-8,17){$\bullet$}
\centerput(20,13){${}\longleftarrow T\setminus T(s)$}
\centerput(12,35){$T(s)\setminus T(s')$}
\centerput(12,32){\hbox to 1.5cm{\downbracefill}}
\centerput(35,14){$\left.\vrule height 1.4cm depth 1.4cm width
0cm\right\}$ }
\centerput(38,14){$T$}
}

$$
\box\boxarbre
$$
\smallskip
\centerline{Fig. 9}

\endinsert
Les \'etiquettes des sommets de $T\setminus T(s)$ ne sont jamais
modifi\'ees lorsqu'on applique les op\'erations $\bfc(s)$,
$\bfc(s')$.  Lorsqu'on applique $\bfc(s')$ \`a~$T$, seul l'ordre des
\'etiquettes des sommets de $T(s')$ est renvers\'e: l'\'etiquette
$a_{i(k)}$ est remplac\'ee par $a_{i(m'+1-k)}$. Si on applique
ensuite
$\bfc(s)$ \`a l'arbre transform\'e $\bfc(s')\,T$, alors
$a_{i(m'+1-k)}$ est chang\'ee en $a_{m+1-i(m'+1-k)}$ et
l'\'etiquette $a_j$ de $T(s)\setminus T(s')$ en $a_{m+1-j}$.

Par ailleurs, si on applique $\bfc(s)$ \`a $T$, la suite des
\'etiquettes $a_{i(1)}<\cdots<a_{i(m')}$ de $T(s')$ est chang\'ee,
terme \`a terme, en la suite des \'etiquettes
$a_{m+1-i(1)}>\cdots>a_{m+1-i(m')}$ du sous-arbre
$\bigl(\bfc(s)\,T\bigr)(s')$. Chaque \'eti\-quette $a_j$ de
$T(s)\setminus T(s')$ est chang\'ee en $a_{m+1-j}$ et n'est plus
chang\'ee par l'application ult\'erieure de~$\bfc(s')$. 

En revanche, quand on applique $\bfc(s')$ \`a ce sous-arbre
$\bigl(\bfc(s)\,T\bigr)(s')$, la suite
$a_{m+1-i(1)}>\cdots>a_{m+1-i(m')}$ est chang\'ee, terme \`a
terme, en $a_{m+1-i(m')}>\cdots>a_{m+1-i(1)}$.\qed

\medskip
Soit $s$ un sommet int\'erieur d'un arbre minimax~$T$;
l'involution $\bfc(s)$ change l'\'etiquette maximum (resp.
minimum) du sommet~$s$ en une \'eti\-quette minimum (resp.
maximum). On dit qu'elle change la {\it valeur extremum} de son
\'etiquette. L'involution $\bfc(s)$ change \'egalement la
valeur extremum de l'\'etiquette de tout sommet int\'erieur
$s'\in T(s)$. Notons~$s_g$ et~$s_d$ les fils \`a gauche et \`a
droite (s'ils existent) du sommet~$s$ et posons:
$$
\bfd(s):=\cases{\bfc(s)\bfc(s_g)\bfc(s_d),&si $s$ a deux fils ;\cr
\bfc(s)\bfc(s_g),&si $s$ a un seul fils \`a gauche ;\cr
\bfc(s)\bfc(s_d),&si $s$ a un seul fils \`a droite.\cr}
\leqno(4.4)
$$
Alors $\bfd(s)$ change la valeur extremum de l'\'etiquette du
sommet~$s$, mais conserve le caract\`ere extremum des autres
\'etiquettes dans l'arbre~$T$.

Soit $s_1$, $s_2$, \dots~, $s_n$ la suite croissante des $n$
sommets d'un arbre mini\-max~$T$ d'ordre~$n$ suivant
l'ordre~$<_T$. Pour tout $i=1,2,\ldots,n$, on pose
$\bfc_i\,T:=\bfc(s_i)\,T$. Alors $\bfc_i$ est une involution
agissant sur l'ensemble~$M_n$ des arbres minimax d'ordre~$n$.
Soit $G_n$ le groupe engendr\'e par ces involutions. 

\proclaim 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\^ome
g\'en\'erateur de la $G_n$-orbite de~$T_0$ par la statistique
$(\hr,\cro)$ est donn\'e par:
$p^{\hr(T_0)}(1+q)^{n-k}$. En particulier, l'orbite contient
$2^{n-k}$ arbres minimax.

{\it D\'emonstration}.\quad 
L'esp\`ece de chaque sommet d'un arbre minimax reste invariante
sous l'action de toute involution
$\bfc_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'\'etiquette maximum, \`a savoir $s_{i_1}$, $s_{i_2}$, \dots~,
$s_{i_l}$, l'arbre
$T_0:=\bfd(s_{i_1})\bfd(s_{i_2})\cdots \bfd(s_{i_l})\,T$ n'a alors
que des \'etiquettes mimimum. Il est donc croissant. D\'esignons
par $(s_1,s_2,\ldots, s_{n-k})$ la suite croissante, pour l'ordre
$<_{T_0}$, des sommets int\'erieurs de~$T_0$. 
Dans l'alg\`ebre du groupe~$G_n$, le d\'eveloppement de
$(1+\bfd(s_1))(1+\bfd(s_2))\cdots (1+\bfd(s_{n-k}))\,T_0$ 
donne $2^{n-k}$ termes. Chaque terme de cette somme peut
s'exprimer comme $\prod_{j\in A}\bfd(s_j)\,T_0$, o\`u $A$ est un
sous-ensemble de $\{1,2,\ldots,n-k\}$. De plus, 
$\{s_j:j\in A\}$ est l'ensemble des sommets maximum de l'arbre.
Ces termes sont donc tous distincts.
 Posons aussi
$W(T):=p^{\hr(T)}q^{\cro(T)}$ et prolongeons la d\'efinition
de~$W$ \`a l'alg\`ebre du groupe, de sorte que
$W(1+\bfd(s_i))(T)=p^{\hr(T)}(1+q)q^{\cro(T)}$. Alors 
$$\eqalignno{
\sum_{T\in {\rm orbite\ de}\ T_0} W(T)
&=W(1+\bfd(s_1))(1+\bfd(s_2))\cdots (1+\bfd(s_{n-k}))(T_0)\cr
&=p^{\hr(T_0)}(1+q)^{n-k}.\qed\cr}
$$

\medskip 
{\it Notation}.\quad Pour tout arbre
minimax $T$, on note $\bfc\,T$ l'{\it unique} arbre minimax
croissant contenu dans sa $G_n$-orbite. L'application~$\bfc$ est
donc une {\it surjection} de $M_{n,k}$ sur $C_{n,k}$.

\bigskip
\centerline{\bf 5. Les op\'erations-retournements}
\medskip
Dans les op\'erations-compl\'ements d\'ecrites dans le paragraphe
pr\'ec\'e\-dent, la position des sommets de l'arbre reste inchang\'ee,
mais les \'etiquettes sont permut\'ees. Pour les
op\'erations-retournements, la position de certains sommets est
modifi\'ee, pas leurs \'etiquettes.

Pour d\'ecrire ces nouvelles op\'erations, il est commode de noter
$T[a]$ le sous-arbre dont la racine est  d'\'etiquette~$a$. De
m\^eme, les sous-arbres \`a gauche et \`a droite incidents au
sommet \'etiquet\'e~$a$ sont d\'esign\'es par $T_g[a]$ et
$T_d[a]$, respectivement.

Soit $s$ un sommet int\'erieur, \'etiquet\'e~$a$, d'un arbre
minimax~$T$. On d\'esigne par
$$
\bfr[a]\,T
$$
l'arbre d\'eduit de $T$ en faisant pivoter le sous-arbre $T[a]$
autour d'un axe vertical passant par le sommet~$s$. Si le
sommet~$s$ \'etiquet\'e~$a$ est une feuille, on pose
$\bfr[a]\,T=T$.

Par exemple, l'op\'eration $\bfr[3]$, appliqu\'ee \`a l'arbre de la
Fig.~1, donne l'arbre repr\'esent\'e dans la Fig.~10.

\midinsert
\newbox\boxarbre

\def\segment(#1,#2)\dir(#3,#4)\long#5{%
\leftput(#1,#2){\lline(#3,#4){#5}}}

\setbox\boxarbre=\vbox{\vskip
40mm\offinterlineskip 
\centerput(0,-1){$\bullet$}
\centerput(20,9){$\bullet$}
\centerput(30,19){$\bullet$}
\centerput(35,29){$\bullet$}
\centerput(10,19){$\bullet$}
\centerput(-20,9){$\bullet$}
\centerput(-30,19){$\bullet$}
\centerput(-35,29){$\bullet$}
\centerput(-25,29){$\bullet$}
\centerput(-37.5,39){$\bullet$}
%
\centerput(0,-4){$1$}
\centerput(20,6){$10$}
\centerput(30,16){$8$}
\centerput(35.5,26){$9$}
\centerput(10,16){$4$}
\centerput(-20,6){$2$}
\centerput(-30,16){$3$}
\centerput(-35.5,26){$7$}
\centerput(-24.5,26){$6$}
\centerput(-38.5,36){$5$}
%
\segment(0,0)\dir(2,1)\long{20}
\segment(20,10)\dir(1,1)\long{10}
\segment(30,20)\dir(1,2)\long{5}
\segment(20,10)\dir(-1,1)\long{10}
%
\segment(0,0)\dir(-2,1)\long{20}
\segment(-20,10)\dir(-1,1)\long{10}
\segment(-30,20)\dir(-1,2)\long{5}
\segment(-30,20)\dir(1,2)\long{5}
\segment(-35,30)\dir(-1,4)\long{2.5}
}


$$
\box\boxarbre
$$
\medskip
\centerline{Fig. 10}

\endinsert

Les propri\'et\'es suivantes, valables pour les op\'erations
$\bfr[a]$, sont \'evi\-dentes:

(1) l'op\'eration $\bfr[a]$ change non seulement l'esp\`ece d'un
sommet int\'e\-rieur d'\'etiquette~$a$, mais \'egalement l'esp\`ece
de chaque sommet int\'erieur du sous-arbre $T[a]$ ;
\goodbreak
(2) les op\'erations $\bfr[a]$
$(a=1,2,\ldots, n)$ agissent sur l'ensemble~$M_n$ et sont des {\it
involutions}, {\it commutant} deux \`a deux ; soit $R_n$ le
groupe engendr\'e par ces involutions ;

\medskip
Soit $s$ un sommet int\'erieur d'\'etiquette~$a$ d'un arbre
minimax ; si ce sommet est double, on note $\{a',a''\}$ l'ensemble
des \'etiquettes des deux fils du sommet~$s$ ; s'il est
simple, on d\'esigne par~$a'$ l'\'etiquette de son fils unique.
Posons
$$
\bfs[a]:=\cases{\bfr[a]\,\bfr[a']\,\bfr[a''],&si le sommet
d'\'etiquette~$a$ est double ;\cr
\bfr[a]\,\bfr[a'],&si le sommet
d'\'etiquette~$a$ est simple.\cr}
$$
Il r\'esulte de la propri\'et\'e (1) ci-dessus que si dans un
arbre~$T$, le sommet d'\'etiquette~$a$ est int\'erieur,
l'op\'eration $\bfs[a]$, appliqu\'ee \`a~$T$, change {\it
uniquement} l'esp\`ece du sommet d'\'etiquette~$a$.


\proclaim 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\^ome g\'en\'erateur de la $R_n$-orbite de~$T_1$ par la
statistique $(\hr,\cro)$ est donn\'e par:
$(1+p)^{n-k}q^{\cro(T_1)}$. En particulier, la
$R_n$-orbite de~$T$ contient exactement $2^{n-k}$ arbres
minimax.


{\it D\'emonstration}.\quad
Il suffit de reprendre la d\'emonstration de la Proposition 4.2, en
faisant jouer \`a~$\bfs$ le r\^ole jou\'e par~$\bfd$ et \`a la
stastique~``$\cro$" celui jou\'e par~``$\hr$".\qed

{\it Notation}.\quad
Pour tout arbre minimax $T$, on note $\bfr\,T$ l'{\it unique}
arbre de Heytei-Reiner contenu dans sa $R_n$-orbite.
L'application~$\bfr$ est donc une {\it surjection} de $M_{n,k}$
sur $H\!R_{n,k}$.



\bigskip
\centerline{\bf 6. Arbres d'Andr\'e}
\medskip
Les groupes $G_n$ et $R_n$ ont exactement
$n!$ orbites. En effet, comme indiqu\'e dans le troisi\`eme
paragraphe, la projection orthogonale sur un axe horizontal des
\'etiquettes d'un arbre croissant (resp. de Hetyei-Reiner) est une
bijection de~$C_n$ (resp. de~$H\!R_n$) sur l'ensemble des
permutations de $1,2,\ldots, n$. 

Si maintenant on applique l'op\'eration $\bfc$ \`a un arbre de
Hetyei-Reiner, ou bien si on applique $\bfr$ \`a un arbre croissant,
on obtient, dans les deux cas, un arbre de Hetyei-Reiner croissant,
c'est-\`a-dire un {\it arbre d'Andr\'e}.
Nous avons vu pr\'ec\'edemment que les op\'erations $\bfc(s)$,
commutent entre elles ; il en est de m\^eme pour les
op\'erations~$\bfr[a]$. Il s'agit maintenant de d\'emontrer que les
$\bfc(s)$ et les $\bfr[a]$ commutent mutuellement. Ce r\'esultat
doit s'\'etablir avec quelques pr\'ecautions de langage que nous
allons d\'evelop\-per. 

Soit $a$ l'\'etiquette d'un sommet int\'erieur~$s$ d'un arbre
minimax~$T$. Les sommets de~$T$ et de l'arbre transform\'e
$T'=\bfc(s)\,T$ sont identiques. Seules les \'etiquettes des sous-arbres
$T(s)$ et $T'(s)$ diff\`erent. En particulier, l'\'etiquette~$a$ du
sommet~$s$ dans~$T$ se transforme en une \'etiquette $a'\not=a$
dans $T'$. Posons:
$$
\bfc[a]\,T:=\bfc(s)\,T.
$$
De m\^eme, posons:
$$\bfr(s)\,T:=\bfr[a]\,T.
$$
Autrement dit, les op\'erations $\bfc(\cdot)$ et $\bfr(\cdot)$
(avec des parenth\`eses) s'appli\-quent \`a des sommets, alors que
$\bfc[\cdot]$ et $\bfr[\cdot]$ (avec des crochets) s'appliquent aux
\'etiquettes.

\proclaim 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\'e:
$$
\bfr(s)\bfc[a']\,T=\bfc[a']\bfr(s)\,T.\leqno(6.1)
$$

{\it D\'emonstration}.\quad 
G\'eom\'etriquement, la relation (6.1) est tout \`a fait \'evidente. 
Partant d'un arbre minimax, il s'agit de changer les \'etiquettes du
sous-arbre dont la racine est d'\'etiquette 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\'erations peuvent
\^etre faites dans un ordre arbitraire.\qed

\medskip
{\it Remarque}.\quad Notons que si la relation (6.1) est vraie, on
a, en g\'en\'eral,
$$
\bfc(s)\bfr[a']\,T\not=\bfr[a']\bfc(s)\,T.
$$

Soit $T_{0,0}$ un arbre minimax ;
l'unique arbre croissant $T_{0,l}:=\bfc\,T_{0,0}$ de son
$G_n$-orbite peut s'exprimer comme $\bfc[a_l]\cdots
\bfc[a_1]\,T_{0,0}$, o\`u 
$(a_1,\ldots, a_l)$ est une suite d'entiers. De m\^eme, l'unique
arbre de Hetyei-Reiner $T_{l',0}:=\bfr\,T_{0,0}$ de son
$R_n$-orbite peut s'exprimer comme $\bfr(s_{l'})\cdots
\bfr(s_1)\,T_{0,0}$, o\`u
$s_1$ est un sommet de~$T_{0,0}$, puis $s_2$ un sommet
de
$T_{1,0}:=\bfr(s_1)\,T_{0,0}$, \dots~, enfin, $s_{l'}$ un sommet de
$T_{l'-1,0}:=\bfr(s_{l'-1})\cdots \bfr(s_1)\,T_{0,0}$.

Consid\'erons le diagramme:
$$\def\normalbaselines{\baselineskip 20pt\lineskip3pt
\lineskiplimit3pt}
\def\mapright#1{\smash{\mathop{\longrightarrow}\limits^{#1}}}
\def\mapdown#1{\Big\downarrow
\rlap{$\vcenter{\hbox{$\scriptstyle#1$}}$}}
\matrix{T_{0,0}&\mapright{\bfc[a_1]}&T_{0,1}
&\mapright{\bfc[a_2]}&\cdots&\mapright{\bfc[a_l]}
&T_{0,l}\cr
\mapdown{\bfr(s_1)}&&\mapdown{\bfr(s_1)}&&
&&\mapdown{\bfr(s_1)}\cr
T_{1,0}&\mapright{\bfc[a_1]}&T_{1,1}
&\mapright{\bfc[a_2]}&\cdots&\mapright{\bfc[a_l]}
&T_{1,l}\cr
\mapdown{\bfr(s_2)}&&\mapdown{\bfr(s_2)}&&
&&\mapdown{\bfr(s_2)}\cr
\vdots&&\vdots&&
&&\vdots\cr
\mapdown{\bfr(s_{l'})}&&\mapdown{\bfr(s_{l'})}&&
&&\mapdown{\bfr(s_{l'})}\cr
T_{l',0}&\mapright{\bfc[a_1]}&T_{l',1}
&\mapright{\bfc[a_2]}&\cdots&\mapright{\bfc[a_l]}
&T_{l',l}\cr
}
$$
Comme les involutions $\bfc[a_i]$ ne modifient pas la position
des sommets, le sommet~$s_1$ est un sommet de tous les arbres de
la premi\`ere 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\`es la Proposition~6.1.

D'autre part, si un arbre $T$ est croissant (resp. de
Hetyei-Reiner) et si $s$ est un sommet d'\'etiquette~$a$, alors
$\bfr(s)\,T$ (resp. $\bfc[a]\,T$) est aussi croissant (resp. de
Hetyei-Reiner). Il en r\'esulte que, dans le diagramme, tous les
arbres de la colonne de droite sont croissants et tous les arbres de
la derni\`ere ligne sont de Hetyei-Reiner. De plus, $T_{l',l}$ est un
arbre d'Andr\'e. Enfin, tous les arbres d'une m\^eme ligne
(resp. colonne) appartiennent \`a la m\^eme $G_n$-orbite (resp.
$R_n$-orbite).

Puisque $\bfc\,T_{0,0}=\bfc[a_l]\cdots \bfc[a_1]\,T_{0,0}$
et $\bfr\,T_{0,0}=\bfr(s_{l'})\cdots \bfr(s_1)\,T_{0,0}$,
on a donc aussi
$\bfc\,T_{i,0}=\bfc[a_l]\cdots \bfc[a_1]\,T_{i,0}$
et $\bfr\,T_{0,j}=\bfr(s_{l'})\cdots \bfc(s_1)\,T_{0,j}$
pour tout $i=1,\ldots,l$ et $j=1,\ldots,l'$ ; d'o\`u le diagramme
commutatif:
$$\def\normalbaselines{\baselineskip 20pt\lineskip3pt
\lineskiplimit3pt}
\def\mapright#1{\smash{\mathop{\longrightarrow}\limits^{#1}}}
\def\mapdown#1{\Big\downarrow
\rlap{$\vcenter{\hbox{$\scriptstyle#1$}}$}}
\matrix{T_{0,0}&\mapright{\bfc}&T_{0,1}\cr
\mapdown{\bfr}&&\mapdown{\bfr}\cr
T_{l',0}&\mapright{\bfc}&T_{l',l}\cr}
\leqno(6.2)$$

Soit $T_0$ un arbre d'Andr\'e d'ordre~$n$ ayant $k$ feuilles.
La somme $\sum_T T$, \'etendue \`a tous les~$T$ tels que
$\bfc\,\bfr\,T=\bfr\,\bfc\,T=T_0$, peut s'\'ecrire:
$$
\sum_{\bfc\,\bfr\,T=T_0}T=(1+\bfd(s_1))\cdots(1+\bfd(s_{n-k}))
(1+\bfs[a_1])\cdots(1+\bfs[a_{n-k}])\,T_0,
$$
en utilisant les op\'erateurs $\bfd(s_i)$ et $\bfs[a_i]$ introduits
dans les paragraphes~4 et~5. D'o\`u, en posant toujours 
$W(T)=p^{\hr(T)}q^{\cro(T)}$,
$$\eqalignno{
\sum_{\bfc\,\bfr\,T=T_0} W(T)
&=W(1+\bfd(s_1))\cdots (1+\bfd(s_{n-k}))\cr
\noalign{\vskip-12pt}
&\qquad{}\times
(1+\bfs[a_1])\cdots (1+\bfs[a_{n-k}])(T_0)\cr
&=(1+p)^{n-k}(1+q)^{n-k}.\cr}
$$

\bigskip
\centerline{\bf 7. Fonctions g\'en\'eratrices}

\medskip
Dans le troisi\`eme paragraphe, on  a montr\'e que la fonction
g\'en\'eratrice exponentielle des polyn\^omes g\'en\'erateurs des
arbres minimax pouvait se d\'eduire de la fonction g\'en\'eratrice
exponentielle des polyn\^omes d'Andr\'e $D_n(t)=\sum_k
d_{n,k}t^k$, o\`u $d_{n,k}$ d\'esigne le nombre d'arbres d'Andr\'e
d'ordre~$n$ ayant~$k$ feuilles. L'identit\'e (3.3) a \'et\'e obtenue
dans [FoSch73] par des technique analytiques. Nous nous proposons
de l'\'etablir par les techniques classiques de l'alg\`ebre
combinatoire.

La r\'ecurrence (3.3) pour les nombres
$d_{n,k}$ est \'equivalente \`a la relation
$$
D_n(t)=nt\,D_{n-1}(t)+t(1-2t)D'_{n-1}(t)\ (n\ge 1),\quad
D_0(t)=1,\leqno(7.1)
$$
o\`u $D'_{n-1}(t)$ d\'esigne la d\'eriv\'ee du polyn\^ome 
$D_{n-1}(t)$. Posons:
$$r(t):=(1-2t)^{1/2};\ 
w(t):={1-r(t)\over 1+r(t)};\ 
F_n(t):={D_n(t)\over r(t)^{n+1}}\ (n=0,1,2,\ldots\,).
$$
Puisque $r'(t)=-r(t)^{-1}$, la relation (7.1)
entra\^\i ne:
$$
F_n(t)=t\,r(t)\, F'_{n-1}(t)\ (n\ge 1),\quad
F_0(t)=r(t)^{-1}.\leqno(7.2)
$$
Pour r\'esoudre cette \'equation faisant intervenir
l'op\'erateur diff\'erentiel et celui aux diff\'erences, on s'inspire
des techniques connues utilis\'ees pour les polyn\^omes eul\'eriens
(voir [Ri58], Exercice~2, pp. 14-15). 

\proclaim Proposition 7.1. On a l'identit\'e:
$$
F_n(t)=2\sum_{j\ge 1} w(t)^j\,j^n\quad (n\ge 1).\leqno(7.3)
$$

{\it D\'emonstration}.\quad
Posons, pour simplifier, $r:=r(t)$ et $w:=w(t)$.
Il faut v\'erifier que le membre de droite de (7.3) satisfait
l'\'equation (7.2). Or
$\sum_{j\ge 0}w^j =(1+r^{-1})/2$ et par d\'erivation
$\sum_{j\ge 1}j\,w^{j-1}\,w'=r^{-3}/2$, d'o\`u
$2\sum_{j\ge 1}w^j=t\,r^{-2}=t\,r(r^{-1})'$. L'\'equation (7.3)
est donc satisfaite pour $n=1$.

Pour $n\ge 2$, on a, en partant de la relation (7.3) avec $n$
remplac\'e par $(n-1)$, l'identit\'e
$F'_{n-1}(t)=2\sum\limits_{j\ge 1}j\,w^{j-1}w'\,j^{n-1}
=2\sum\limits_{j\ge 1}w^{j-1}\displaystyle{2\over r(1+r)^2}j^n$.
Or, $2t=(1-r)(1+r)$. On en tire:
$$
t\,r\,F'_{n-1}(t)=2\sum_{j\ge 1}\Bigl({1-r\over 1+r}\Bigr)^{j-1}
{(1-r)(1+r)\over (1+r)^2}j^n
=2\sum_{j\ge 1}w^jj^n.\qed$$

\medskip
La relation (7.3) se r\'ecrit \`a l'aide des polyn\^omes $D_n(t)$
comme:
$$
{D_n(t)\over (1-2t)^{(n+1)/2}}
=2\sum_{j\ge 1}
\Bigl({1-(1-2t)^{1/2}\over 1+(1-2t)^{1/2}}\Bigr)^jj^n.\leqno(7.4)
$$

De la Proposition 7.1 on peut alors obtenir la fonction
g\'en\'eratrice exponentielle des s\'eries $F_n(t)$ et des
polyn\^omes $D_n(t)$ par une simple manipulation. Comme
$1+2w/(1-w)=r^{-1}$, on a:
$$
\leqalignno{
\sum_{n\ge 0}{u^n\over n!}F_n(t)
&=r^{-1}+2\sum_{n\ge 1} {u^n\over n!}\sum_{j\ge 1} w^j j^n
=1+2\sum_{j\ge 1} w^j+2\sum_{n\ge 1} {u^n\over n!}
\sum_{j\ge 1} w^j j^n\cr 
&=1+2\sum_{n\ge 0} {u^n\over n!}\sum_{j\ge 1} w^jj^n
=1+2\sum_{j\ge 1} w^j\sum_{n\ge 0} {(uj)^n\over n!}\cr 
&=1+2\sum_{j\ge 1}(we^u)^j=1+2{we^u\over 1-we^u}.\cr}
$$
Soit
$$\leqalignno{
\sum_{n\ge 0}{u^n\over n!}F_n(t)
&={1+w(t)e^u\over 1-w(t)e^u}.&(7.5)\cr
\noalign{\hbox{Et par cons\'equent:}}
\sum_{n\ge 0}{u^n\over n!}D_n(t)
&=\sum_{n\ge 0}r^{n+1}{u^n\over n!}F_n(t)\cr
&=r(t){1+w(t)e^{r(t)u}\over 1-w(t)e^{r(t)u}}.&(7.6)\cr
}
$$
Notons qu'en posant $t=1$ dans la pr\'ec\'edente identit\'e et en
notant que $r(1)=i$ et $w(1)=-i$, on trouve
$$
\sum_{n\ge 0}{u^n\over n!}D_n(1)=\tan u+\sec u,
$$
une mani\`ere de retrouver que le nombre d'arbres d'Andr\'e
d'ordre~$n$ est \'egal au nombre tangent ou au nombre s\'ecant.

\medskip
Une autre technique pour obtenir l'identit\'e (7.5) \`a partir
de l'\'equation diff\'erentielle et aux diff\'erences (7.2) est de poser
$$F:=F(t,u):=\sum_{n\ge 0}{u^n\over n!}\,F_n(t)
$$
et de v\'erifier
qu'en d\'esignant par $D_u$ et $D_t$ les d\'eriv\'ees partielles par
rapport \`a~$u$ et~$t$, respectivement, on peut r\'ecrire (7.2)
sous la forme:
$$
D_u\,F=tr\,D_t F,\quad F(t,0)=r(t)^{-1}.\leqno(7.7)
$$
On cherche alors des solutions de la forme
$F=f(g(t)h(u))$, s'imposant que $F$ est fonction de~$t$ et~$u$
\`a travers un {\it produit} de fonctions $g(t)\cdot h(u)$.
Alors (7.7) se r\'ecrit
$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\'eduit l'\'equation diff\'erentielle:
$g'(t)/g(t)=1/tr=1/(t(1-2t)^{1/2})$. Or
$$\displaylines{
\int {1\over t(1-2t)^{1/2}}\,dt={\rm ln}\,\Bigl(C\,
{(1-2t)^{1/2}-1
\over (1-2t)^{1/2}+1}\Bigr)={\rm ln}\,Cw(t),\cr
\noalign{\hbox{o\`u $C$ est une constante; de l\`a}}
g(t)=C\,w(t).\cr}
$$
D'o\`u 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)={1+w(t)e^u\over 1-w(t)e^u}.
$$
\bigskip

\centerline{\bf 8. Autres op\'erations-compl\'ements et
retournements}

\medskip
Plut\^ot que de faire une \'etude abstraite, nous avons
pr\'ef\'er\'e obtenir les r\'esultats ci-dessus sur les arbres
minimax \`a l'aide d'une seule classe
d'op\'erations-compl\'ements et une seule classe
d'op\'erations-retournements. Naturellement il existe d'autres
telles op\'erations qui conduisent aux\break m\^emes r\'esultats.
Nous nous contentons d'abord de signaler deux autres
op\'era\-tions-compl\'ements, not\'ees
$\bfc'(s)$ et $\bfc''(s)$.

Soit $s$ un sommet int\'erieur 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'\'etiquette de~$s$ ; si
elle est minimum (resp. maximum) dans le sous-arbre $T(s)$, on
note~$\overline s$ le sommet d'\'etiquette maximum (resp.
minimum) dans $T(s)$ et on d\'esigne par~$\overline a$ son
\'etiquette. Ce sommet appartient soit \`a $T_g(s)$, soit \`a
$T_d(s)$. La premi\`ere op\'eration-compl\'ement est donn\'ee par:
$$
\bfc'(s)T:=\cases{T\setminus (\{s\}\cup T_g(s))
+\bfc(s)(\{s\}\cup T_g(s)),&si $\overline s\in T_g(s)$ ;\cr
\noalign{\medskip}
T\setminus (\{s\}\cup T_d(s))+\bfc(s)(\{s\}\cup T_d(s)),&si
$\overline s\in T_d(s)$.\cr}
$$
Autrement dit, on applique l'op\'eration-compl\'ement $\bfc(s)$ au
seul sous-arbre $\{s\}\cup T_g(s))$ (resp. $\{s\}\cup T_d(s))$) et
on laisse invariantes les autres \'etiquettes.


Soit maintenant $f(s)$ la racine du sous-arbre $T_g(s)$ (resp.
$T_d(s)$) si $\overline s\in T_g(s)$ (resp. si
$\overline s\in T_d(s)$). On d\'efinit $\bfc''(s)$ par:
$$
\bfc''(s)T:=\cases{T\setminus (\{s\}\cup T_g(s))+\bfc(f(s))\bfc(s)(\{s\}\cup
T_g(s)),&si
$\overline s\in T_g(s)$ ;\cr
\noalign{\medskip}
T\setminus (\{s\}\cup T_d(s))+\bfc(f(s))\bfc(s)(\{s\}\cup T_d(s)),&si
$\overline s\in T_d(s)$.\cr}
$$
Dans cette derni\`ere op\'eration, l'application de $\bfc(f(s))$ a
pour effet de r\'epartir les nouvelles \'etiquettes du sous-arbre
contenant~$\overline s$ dans leur ordre originel. Lorsqu'on
applique les op\'erations $\bfc''(s)$ aux seuls arbres de Hetyei-Reiner,
on retrouve les op\'erations $\psi_k$ introduites par
ces auteurs [HeRe98].

\medskip
On peut aussi d\'efinir directement les
op\'erations-compl\'ements
$\bfc'(s)$ et $\bfc''(s)$ de la fa\c con suivante.
D\'esignons par $a_1<a_2<\cdots<a_{m'}$ la suite croissante des
\'etiquettes dans le sous-arbre  $\{s\}\cup T_g(s)$ ou le
sous-arbre $\{s\}\cup T_d(s)$ suivant que $\overline s\in T_g(s)$
ou non.

Pour obtenir $\bfc'(s)T$, on ne modifie pas les \'etiquettes des
sommets dans $T\setminus (\{s\}\cup T_g(s))$
(resp. dans $T\setminus (\{s\}\cup T_d(s))$), mais on change
chaque \'etiquette $a_i$ en $a_{m'+1-i}$.

Pour obtenir $\bfc''(s)T$, on ne modifie pas les \'etiquettes des
sommets dans $T\setminus (\{s\}\cup T_g(s))$
(resp. dans $T\setminus (\{s\}\cup T_d(s))$), on change ensuite
l'\'etiquette $a$ de $s$ en $\overline a$ et enfin on remplace
chaque \'etiquette $a_i$ par $a_{i-1}$ $(i=2,3,\ldots, m')$ si $s$
est d'\'etiquette minimum dans $T(s)$ et par $a_{i+1}$
$(i=1,2,\ldots, m'-1)$ si $s$ est d'\'etiquette maximum. 

\medskip
Pour les retournements, il s'agit de prendre un {\it ordre total sur
les sous-arbres}. Au lieu de la d\'efinition prise au d\'ebut du
troisi\`eme paragraphe, on peut prendre la convention suvante:
dans un arbre minimax~$T$, soit $s$ un sommet
d'\'etiquette~$a$ ; si l'\'etiquette~$a$ d'un sommet {\it
int\'erieur}~$s$ est minimum (resp. maximum) dans le sous-arbre
$T(s)$, on dit que le sommet~$s$ est de {\it premi\`ere esp\`ece}
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\`ere
esp\`ece sont dits {\it arbres de Hetyei-Reiner~II}. Un arbre
croissant, qui est aussi de Hetyei-Reiner~II est alors un {\it arbre
d'Andr\'e~II}, d\'ej\`a consid\'er\'e dans [FoSch73].


\bigskip
{\bf Appendice}.\quad
Dans la Fig. 11, le coin sup\'erieur gauche est occup\'e par un arbre
minimax~$T$ d'ordre $n=10$. Pour obtenir l'arbre
croissant~$\bfc\,T$, il suffit d'appliquer la suite des
op\'erations-compl\'ements $\bfc[10]$, $\bfc[9]$,
$\bfc[7]$. On obtient l'arbre situ\'e dans le coin sup\'erieur
droit. L'arbre de Hetyei-Reiner $\bfr\,T$ appara\^\i t dans le
coin inf\'erieur gauche. Enfin l'arbre d'Andr\'e
$T_0:=\bfc\,\bfr\,T=\bfr\,\bfc\,T$ est dans le coin inf\'erieur droit.
Il faut noter que tous les arbres de la colonne la plus \`a 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 $\bfc\,\bfr\,T'=T_0$ contient donc $4^{n-k}=4^{6}=4.096$
\'el\'ements, dont les 20 repr\'esent\'es dans ce tableau.

\midinsert
\newbox\boxarbreun
\newbox\boxarbredeux
\newbox\boxarbretrois
\newbox\boxarbrequatre
\newbox\boxarbrecinq
\newbox\boxarbresix
\newbox\boxarbresept
\newbox\boxarbrehuit
\newbox\boxarbreneuf
\newbox\boxarbredix
\newbox\boxarbreonze
\newbox\boxarbredouze
\newbox\boxarbretreize
\newbox\boxarbrequatorze
\newbox\boxarbrequinze
\newbox\boxarbreseize
\newbox\boxarbredixsept
\newbox\boxarbredixhuit
\newbox\boxarbredixneuf
\newbox\boxarbrevingt

\def\mapdown#1{\big\downarrow
\rlap{$\vcenter{\hbox{$\scriptstyle #1$}}$}}

\def\segment(#1,#2)\dir(#3,#4)\long#5{%
\leftput(#1,#2){\lline(#3,#4){#5}}}

\setbox\boxarbreun=\vbox{\vskip
28mm\offinterlineskip 
%
\centerput(0,-2){$\scriptstyle 1$}
\centerput(10,2){$\scriptstyle 10$}
\centerput(15,7){$\scriptstyle 8$}
\centerput(18,12){$\scriptstyle 9$}
\centerput(5,7){$\scriptstyle 4$}
\centerput(-10,2){$\scriptstyle 2$}
\centerput(-15,7){$\scriptstyle 3$}
\centerput(-19,13){$\scriptstyle 6$}
\centerput(-11.5,13){$\scriptstyle 7$}
\centerput(-10,18){$\scriptstyle 5$}
%
\segment(0,0)\dir(2,1)\long{10}
\segment(10,5)\dir(1,1)\long{5}
\segment(15,10)\dir(1,2)\long{2.5}
\segment(10,5)\dir(-1,1)\long{5}
%
\segment(0,0)\dir(-2,1)\long{10}
\segment(-10,5)\dir(-1,1)\long{5}
\segment(-15,10)\dir(-1,2)\long{2.5}
\segment(-15,10)\dir(1,2)\long{2.5}
\segment(-12.5,15)\dir(1,4)\long{1.25}
\centerput(20,0){$\buildrel \bfc[10]\over \longrightarrow$}
\centerput(0,-7){$\mapdown{\bfr(-1,1)}$}
}

\setbox\boxarbredeux=\vbox{\vskip
28mm\offinterlineskip 
%
\centerput(0,-2){$\scriptstyle 1$}
\centerput(10,2){$\scriptstyle 4$}
\centerput(15,7){$\scriptstyle 9$}
\centerput(18,12){$\scriptstyle 8$}
\centerput(5,7){$\scriptstyle 10$}
\centerput(-10,2){$\scriptstyle 2$}
\centerput(-15,7){$\scriptstyle 3$}
\centerput(-19,13){$\scriptstyle 6$}
\centerput(-11.5,13){$\scriptstyle 7$}
\centerput(-10,18){$\scriptstyle 5$}
%
\segment(0,0)\dir(2,1)\long{10}
\segment(10,5)\dir(1,1)\long{5}
\segment(15,10)\dir(1,2)\long{2.5}
\segment(10,5)\dir(-1,1)\long{5}
%
\segment(0,0)\dir(-2,1)\long{10}
\segment(-10,5)\dir(-1,1)\long{5}
\segment(-15,10)\dir(-1,2)\long{2.5}
\segment(-15,10)\dir(1,2)\long{2.5}
\segment(-12.5,15)\dir(1,4)\long{1.25}
\centerput(20,0){$\buildrel \bfc[9]\over \longrightarrow$}
\centerput(0,-7){$\mapdown{\bfr(-1,1)}$}}

\setbox\boxarbretrois=\vbox{\vskip
28mm\offinterlineskip 
%
%
\centerput(0,-2){$\scriptstyle 1$}
\centerput(10,2){$\scriptstyle 4$}
\centerput(15,7){$\scriptstyle 8$}
\centerput(18,12){$\scriptstyle 9$}
\centerput(5,7){$\scriptstyle 10$}
\centerput(-10,2){$\scriptstyle 2$}
\centerput(-15,7){$\scriptstyle 3$}
\centerput(-19,13){$\scriptstyle 6$}
\centerput(-11.5,13){$\scriptstyle 7$}
\centerput(-10,18){$\scriptstyle 5$}
%
\segment(0,0)\dir(2,1)\long{10}
\segment(10,5)\dir(1,1)\long{5}
\segment(15,10)\dir(1,2)\long{2.5}
\segment(10,5)\dir(-1,1)\long{5}
%
\segment(0,0)\dir(-2,1)\long{10}
\segment(-10,5)\dir(-1,1)\long{5}
\segment(-15,10)\dir(-1,2)\long{2.5}
\segment(-15,10)\dir(1,2)\long{2.5}
\segment(-12.5,15)\dir(1,4)\long{1.25}
\centerput(20,0){$\buildrel \bfc[7]\over \longrightarrow$}
\centerput(0,-7){$\mapdown{\bfr(-1,1)}$}}

\setbox\boxarbrequatre=\vbox{\vskip
28mm\offinterlineskip 
%
%
\centerput(0,-2){$\scriptstyle 1$}
\centerput(10,2){$\scriptstyle 4$}
\centerput(15,7){$\scriptstyle 8$}
\centerput(18,12){$\scriptstyle 9$}
\centerput(5,7){$\scriptstyle 10$}
\centerput(-10,2){$\scriptstyle 2$}
\centerput(-15,7){$\scriptstyle 3$}
\centerput(-19,13){$\scriptstyle 6$}
\centerput(-11.5,13){$\scriptstyle 5$}
\centerput(-10,18){$\scriptstyle 7$}
%
\segment(0,0)\dir(2,1)\long{10}
\segment(10,5)\dir(1,1)\long{5}
\segment(15,10)\dir(1,2)\long{2.5}
\segment(10,5)\dir(-1,1)\long{5}
%
\segment(0,0)\dir(-2,1)\long{10}
\segment(-10,5)\dir(-1,1)\long{5}
\segment(-15,10)\dir(-1,2)\long{2.5}
\segment(-15,10)\dir(1,2)\long{2.5}
\segment(-12.5,15)\dir(1,4)\long{1.25}
\centerput(0,-7){$\mapdown{\bfr(-1,1)}$}}

\centerline{\box\boxarbreun\hskip4cm\box\boxarbredeux
\hskip4cm\box\boxarbretrois\hskip4cm\box\boxarbrequatre}

\medskip



\setbox\boxarbrecinq=\vbox{\vskip
28mm\offinterlineskip 
%
\centerput(0,-2){$\scriptstyle 1$}
\centerput(10,2){$\scriptstyle 10$}
\centerput(15,7){$\scriptstyle 8$}
\centerput(18,12){$\scriptstyle 9$}
\centerput(5,7){$\scriptstyle 4$}
\centerput(-10,2){$\scriptstyle 2$}
\centerput(-5,7){$\scriptstyle 3$}
\centerput(-1,13){$\scriptstyle 6$}
\centerput(-9,13){$\scriptstyle 7$}
\centerput(-10,18){$\scriptstyle 5$}
%
\segment(0,0)\dir(2,1)\long{10}
\segment(10,5)\dir(1,1)\long{5}
\segment(15,10)\dir(1,2)\long{2.5}
\segment(10,5)\dir(-1,1)\long{5}
%
\segment(0,0)\dir(-2,1)\long{10}
\segment(-10,5)\dir(1,1)\long{5}
\segment(-5,10)\dir(1,2)\long{2.5}
\segment(-5,10)\dir(-1,2)\long{2.5}
\segment(-7.5,15)\dir(-1,4)\long{1.25}
\centerput(20,0){$\buildrel \bfc[10]\over \longrightarrow$}
\centerput(0,-7){$\mapdown{\bfr(1,1)}$}}

\setbox\boxarbresix=\vbox{\vskip
28mm\offinterlineskip 
%
\centerput(0,-2){$\scriptstyle 1$}
\centerput(10,2){$\scriptstyle 4$}
\centerput(15,7){$\scriptstyle 9$}
\centerput(18,12){$\scriptstyle 8$}
\centerput(5,7){$\scriptstyle 10$}
\centerput(-10,2){$\scriptstyle 2$}
\centerput(-5,7){$\scriptstyle 3$}
\centerput(-1,13){$\scriptstyle 6$}
\centerput(-9,13){$\scriptstyle 7$}
\centerput(-10,18){$\scriptstyle 5$}
%
\segment(0,0)\dir(2,1)\long{10}
\segment(10,5)\dir(1,1)\long{5}
\segment(15,10)\dir(1,2)\long{2.5}
\segment(10,5)\dir(-1,1)\long{5}
%
\segment(0,0)\dir(-2,1)\long{10}
\segment(-10,5)\dir(1,1)\long{5}
\segment(-5,10)\dir(1,2)\long{2.5}
\segment(-5,10)\dir(-1,2)\long{2.5}
\segment(-7.5,15)\dir(-1,4)\long{1.25}
\centerput(20,0){$\buildrel \bfc[9]\over \longrightarrow$}
\centerput(0,-7){$\mapdown{\bfr(1,1)}$}}

\setbox\boxarbresept=\vbox{\vskip
28mm\offinterlineskip 
%
\centerput(0,-2){$\scriptstyle 1$}
\centerput(10,2){$\scriptstyle 4$}
\centerput(15,7){$\scriptstyle 8$}
\centerput(18,12){$\scriptstyle 9$}
\centerput(5,7){$\scriptstyle 10$}
\centerput(-10,2){$\scriptstyle 2$}
\centerput(-5,7){$\scriptstyle 3$}
\centerput(-1,13){$\scriptstyle 6$}
\centerput(-9,13){$\scriptstyle 7$}
\centerput(-10,18){$\scriptstyle 5$}
%
\segment(0,0)\dir(2,1)\long{10}
\segment(10,5)\dir(1,1)\long{5}
\segment(15,10)\dir(1,2)\long{2.5}
\segment(10,5)\dir(-1,1)\long{5}
%
\segment(0,0)\dir(-2,1)\long{10}
\segment(-10,5)\dir(1,1)\long{5}
\segment(-5,10)\dir(1,2)\long{2.5}
\segment(-5,10)\dir(-1,2)\long{2.5}
\segment(-7.5,15)\dir(-1,4)\long{1.25}
\centerput(20,0){$\buildrel \bfc[7]\over \longrightarrow$}
\centerput(0,-7){$\mapdown{\bfr(1,1)}$}}

\setbox\boxarbrehuit=\vbox{\vskip
28mm\offinterlineskip 
%
\centerput(0,-2){$\scriptstyle 1$}
\centerput(10,2){$\scriptstyle 4$}
\centerput(15,7){$\scriptstyle 8$}
\centerput(18,12){$\scriptstyle 9$}
\centerput(5,7){$\scriptstyle 10$}
\centerput(-10,2){$\scriptstyle 2$}
\centerput(-5,7){$\scriptstyle 3$}
\centerput(-1,13){$\scriptstyle 6$}
\centerput(-9,13){$\scriptstyle 5$}
\centerput(-10,18){$\scriptstyle 7$}
%
\segment(0,0)\dir(2,1)\long{10}
\segment(10,5)\dir(1,1)\long{5}
\segment(15,10)\dir(1,2)\long{2.5}
\segment(10,5)\dir(-1,1)\long{5}
%
\segment(0,0)\dir(-2,1)\long{10}
\segment(-10,5)\dir(1,1)\long{5}
\segment(-5,10)\dir(1,2)\long{2.5}
\segment(-5,10)\dir(-1,2)\long{2.5}
\segment(-7.5,15)\dir(-1,4)\long{1.25}
\centerput(0,-7){$\mapdown{\bfr(1,1)}$}}

\centerline{\box\boxarbrecinq\hskip4cm\box\boxarbresix
\hskip4cm\box\boxarbresept\hskip4cm\box\boxarbrehuit}



\medskip


\setbox\boxarbreneuf=\vbox{\vskip
28mm\offinterlineskip 
%
\centerput(0,-2){$\scriptstyle 1$}
\centerput(10,2){$\scriptstyle 10$}
\centerput(15,7){$\scriptstyle 4$}
\centerput(2,12){$\scriptstyle 9$}
\centerput(5,7){$\scriptstyle 8$}
\centerput(-10,2){$\scriptstyle 2$}
\centerput(-5,7){$\scriptstyle 3$}
\centerput(-1,13){$\scriptstyle 6$}
\centerput(-9,13){$\scriptstyle 7$}
\centerput(-10,18){$\scriptstyle 5$}
%
\segment(0,0)\dir(2,1)\long{10}
\segment(10,5)\dir(1,1)\long{5}
\segment(5,10)\dir(-1,2)\long{2.5}
\segment(10,5)\dir(-1,1)\long{5}
%
\segment(0,0)\dir(-2,1)\long{10}
\segment(-10,5)\dir(1,1)\long{5}
\segment(-5,10)\dir(1,2)\long{2.5}
\segment(-5,10)\dir(-1,2)\long{2.5}
\segment(-7.5,15)\dir(-1,4)\long{1.25}
\centerput(20,0){$\buildrel \bfc[10]\over \longrightarrow$}
\centerput(0,-7){$\mapdown{\bfr(-{1\over 2},2)}$}}


\setbox\boxarbredix=\vbox{\vskip
28mm\offinterlineskip 
%
\centerput(0,-2){$\scriptstyle 1$}
\centerput(10,2){$\scriptstyle 4$}
\centerput(15,7){$\scriptstyle 10$}
\centerput(2,12){$\scriptstyle 8$}
\centerput(5,7){$\scriptstyle 9$}
\centerput(-10,2){$\scriptstyle 2$}
\centerput(-5,7){$\scriptstyle 3$}
\centerput(-1,13){$\scriptstyle 6$}
\centerput(-9,13){$\scriptstyle 7$}
\centerput(-10,18){$\scriptstyle 5$}
%
\segment(0,0)\dir(2,1)\long{10}
\segment(10,5)\dir(1,1)\long{5}
\segment(5,10)\dir(-1,2)\long{2.5}
\segment(10,5)\dir(-1,1)\long{5}
%
\segment(0,0)\dir(-2,1)\long{10}
\segment(-10,5)\dir(1,1)\long{5}
\segment(-5,10)\dir(1,2)\long{2.5}
\segment(-5,10)\dir(-1,2)\long{2.5}
\segment(-7.5,15)\dir(-1,4)\long{1.25}
\centerput(20,0){$\buildrel \bfc[9]\over \longrightarrow$}
\centerput(0,-7){$\mapdown{\bfr(-{1\over 2},2)}$}}

\setbox\boxarbreonze=\vbox{\vskip
28mm\offinterlineskip 
%
\centerput(0,-2){$\scriptstyle 1$}
\centerput(10,2){$\scriptstyle 4$}
\centerput(15,7){$\scriptstyle 10$}
\centerput(2,12){$\scriptstyle 9$}
\centerput(5,7){$\scriptstyle 8$}
\centerput(-10,2){$\scriptstyle 2$}
\centerput(-5,7){$\scriptstyle 3$}
\centerput(-1,13){$\scriptstyle 6$}
\centerput(-9,13){$\scriptstyle 7$}
\centerput(-10,18){$\scriptstyle 5$}
%
\segment(0,0)\dir(2,1)\long{10}
\segment(10,5)\dir(1,1)\long{5}
\segment(5,10)\dir(-1,2)\long{2.5}
\segment(10,5)\dir(-1,1)\long{5}
%
\segment(0,0)\dir(-2,1)\long{10}
\segment(-10,5)\dir(1,1)\long{5}
\segment(-5,10)\dir(1,2)\long{2.5}
\segment(-5,10)\dir(-1,2)\long{2.5}
\segment(-7.5,15)\dir(-1,4)\long{1.25}
\centerput(20,0){$\buildrel \bfc[7]\over \longrightarrow$}
\centerput(0,-7){$\mapdown{\bfr(-{1\over 2},2)}$}}

\setbox\boxarbredouze=\vbox{\vskip
28mm\offinterlineskip 
%
\centerput(0,-2){$\scriptstyle 1$}
\centerput(10,2){$\scriptstyle 4$}
\centerput(15,7){$\scriptstyle 10$}
\centerput(2,12){$\scriptstyle 9$}
\centerput(5,7){$\scriptstyle 8$}
\centerput(-10,2){$\scriptstyle 2$}
\centerput(-5,7){$\scriptstyle 3$}
\centerput(-1,13){$\scriptstyle 6$}
\centerput(-9,13){$\scriptstyle 5$}
\centerput(-10,18){$\scriptstyle 7$}
%
\segment(0,0)\dir(2,1)\long{10}
\segment(10,5)\dir(1,1)\long{5}
\segment(5,10)\dir(-1,2)\long{2.5}
\segment(10,5)\dir(-1,1)\long{5}
%
\segment(0,0)\dir(-2,1)\long{10}
\segment(-10,5)\dir(1,1)\long{5}
\segment(-5,10)\dir(1,2)\long{2.5}
\segment(-5,10)\dir(-1,2)\long{2.5}
\segment(-7.5,15)\dir(-1,4)\long{1.25}
\centerput(0,-7){$\mapdown{\bfr(-{1\over 2},2)}$}}

\centerline{\box\boxarbreneuf\hskip4cm\box\boxarbredix
\hskip4cm\box\boxarbreonze\hskip4cm\box\boxarbredouze}


\medskip

\setbox\boxarbretreize=\vbox{\vskip
28mm\offinterlineskip 
%
\centerput(0,-2){$\scriptstyle 1$}
\centerput(10,2){$\scriptstyle 10$}
\centerput(15,7){$\scriptstyle 4$}
\centerput(2,12){$\scriptstyle 9$}
\centerput(5,7){$\scriptstyle 8$}
\centerput(-10,2){$\scriptstyle 2$}
\centerput(-5,7){$\scriptstyle 3$}
\centerput(-1,13){$\scriptstyle 7$}
\centerput(-9,13){$\scriptstyle 6$}
\centerput(-0,18){$\scriptstyle 5$}
%
\segment(0,0)\dir(2,1)\long{10}
\segment(10,5)\dir(1,1)\long{5}
\segment(5,10)\dir(-1,2)\long{2.5}
\segment(10,5)\dir(-1,1)\long{5}
%
\segment(0,0)\dir(-2,1)\long{10}
\segment(-10,5)\dir(1,1)\long{5}
\segment(-5,10)\dir(1,2)\long{2.5}
\segment(-5,10)\dir(-1,2)\long{2.5}
\segment(-2.5,15)\dir(1,4)\long{1.25}
\centerput(20,0){$\buildrel \bfc[10]\over \longrightarrow$}
\centerput(0,-7){$\mapdown{\bfr({1\over 2},2)}$}}

\setbox\boxarbrequatorze=\vbox{\vskip
28mm\offinterlineskip 
%
\centerput(0,-2){$\scriptstyle 1$}
\centerput(10,2){$\scriptstyle 4$}
\centerput(15,7){$\scriptstyle 10$}
\centerput(2,12){$\scriptstyle 8$}
\centerput(5,7){$\scriptstyle 9$}
\centerput(-10,2){$\scriptstyle 2$}
\centerput(-5,7){$\scriptstyle 3$}
\centerput(-1,13){$\scriptstyle 7$}
\centerput(-9,13){$\scriptstyle 6$}
\centerput(-0,18){$\scriptstyle 5$}
%
\segment(0,0)\dir(2,1)\long{10}
\segment(10,5)\dir(1,1)\long{5}
\segment(5,10)\dir(-1,2)\long{2.5}
\segment(10,5)\dir(-1,1)\long{5}
%
\segment(0,0)\dir(-2,1)\long{10}
\segment(-10,5)\dir(1,1)\long{5}
\segment(-5,10)\dir(1,2)\long{2.5}
\segment(-5,10)\dir(-1,2)\long{2.5}
\segment(-2.5,15)\dir(1,4)\long{1.25}
\centerput(20,0){$\buildrel \bfc[9]\over \longrightarrow$}
\centerput(0,-7){$\mapdown{\bfr({1\over 2},2)}$}}

\setbox\boxarbrequinze=\vbox{\vskip
28mm\offinterlineskip 
%
%
\centerput(0,-2){$\scriptstyle 1$}
\centerput(10,2){$\scriptstyle 4$}
\centerput(15,7){$\scriptstyle 10$}
\centerput(2,12){$\scriptstyle 9$}
\centerput(5,7){$\scriptstyle 8$}
\centerput(-10,2){$\scriptstyle 2$}
\centerput(-5,7){$\scriptstyle 3$}
\centerput(-1,13){$\scriptstyle 7$}
\centerput(-9,13){$\scriptstyle 6$}
\centerput(-0,18){$\scriptstyle 5$}
%
\segment(0,0)\dir(2,1)\long{10}
\segment(10,5)\dir(1,1)\long{5}
\segment(5,10)\dir(-1,2)\long{2.5}
\segment(10,5)\dir(-1,1)\long{5}
%
\segment(0,0)\dir(-2,1)\long{10}
\segment(-10,5)\dir(1,1)\long{5}
\segment(-5,10)\dir(1,2)\long{2.5}
\segment(-5,10)\dir(-1,2)\long{2.5}
\segment(-2.5,15)\dir(1,4)\long{1.25}
\centerput(20,0){$\buildrel \bfc[7]\over \longrightarrow$}
\centerput(0,-7){$\mapdown{\bfr({1\over 2},2)}$}}

\setbox\boxarbreseize=\vbox{\vskip
28mm\offinterlineskip 
%
\centerput(0,-2){$\scriptstyle 1$}
\centerput(10,2){$\scriptstyle 4$}
\centerput(15,7){$\scriptstyle 10$}
\centerput(2,12){$\scriptstyle 9$}
\centerput(5,7){$\scriptstyle 8$}
\centerput(-10,2){$\scriptstyle 2$}
\centerput(-5,7){$\scriptstyle 3$}
\centerput(-1,13){$\scriptstyle 5$}
\centerput(-9,13){$\scriptstyle 6$}
\centerput(-0,18){$\scriptstyle 7$}
%
\segment(0,0)\dir(2,1)\long{10}
\segment(10,5)\dir(1,1)\long{5}
\segment(5,10)\dir(-1,2)\long{2.5}
\segment(10,5)\dir(-1,1)\long{5}
%
\segment(0,0)\dir(-2,1)\long{10}
\segment(-10,5)\dir(1,1)\long{5}
\segment(-5,10)\dir(1,2)\long{2.5}
\segment(-5,10)\dir(-1,2)\long{2.5}
\segment(-2.5,15)\dir(1,4)\long{1.25}
\centerput(0,-7){$\mapdown{\bfr({1\over 2},2)}$}}

\centerline{\box\boxarbretreize\hskip4cm\box\boxarbrequatorze
\hskip4cm\box\boxarbrequinze\hskip4cm\box\boxarbreseize}

\medskip

\setbox\boxarbredixsept=\vbox{\vskip
28mm\offinterlineskip 
%
\centerput(0,-2){$\scriptstyle 1$}
\centerput(10,2){$\scriptstyle 10$}
\centerput(15,7){$\scriptstyle 4$}
\centerput(8,12){$\scriptstyle 9$}
\centerput(5,7){$\scriptstyle 8$}
\centerput(-10,2){$\scriptstyle 2$}
\centerput(-5,7){$\scriptstyle 3$}
\centerput(-1,13){$\scriptstyle 7$}
\centerput(-9,13){$\scriptstyle 6$}
\centerput(-0,18){$\scriptstyle 5$}
%
\segment(0,0)\dir(2,1)\long{10}
\segment(10,5)\dir(1,1)\long{5}
\segment(5,10)\dir(1,2)\long{2.5}
\segment(10,5)\dir(-1,1)\long{5}
%
\segment(0,0)\dir(-2,1)\long{10}
\segment(-10,5)\dir(1,1)\long{5}
\segment(-5,10)\dir(1,2)\long{2.5}
\segment(-5,10)\dir(-1,2)\long{2.5}
\segment(-2.5,15)\dir(1,4)\long{1.25}
\centerput(20,0){$\buildrel \bfc[10]\over \longrightarrow$}
}

\setbox\boxarbredixhuit=\vbox{\vskip
28mm\offinterlineskip 
%
\centerput(0,-2){$\scriptstyle 1$}
\centerput(10,2){$\scriptstyle 4$}
\centerput(15,7){$\scriptstyle 10$}
\centerput(8,12){$\scriptstyle 8$}
\centerput(5,7){$\scriptstyle 9$}
\centerput(-10,2){$\scriptstyle 2$}
\centerput(-5,7){$\scriptstyle 3$}
\centerput(-1,13){$\scriptstyle 7$}
\centerput(-9,13){$\scriptstyle 6$}
\centerput(-0,18){$\scriptstyle 5$}
%
\segment(0,0)\dir(2,1)\long{10}
\segment(10,5)\dir(1,1)\long{5}
\segment(5,10)\dir(1,2)\long{2.5}
\segment(10,5)\dir(-1,1)\long{5}
%
\segment(0,0)\dir(-2,1)\long{10}
\segment(-10,5)\dir(1,1)\long{5}
\segment(-5,10)\dir(1,2)\long{2.5}
\segment(-5,10)\dir(-1,2)\long{2.5}
\segment(-2.5,15)\dir(1,4)\long{1.25}
\centerput(20,0){$\buildrel \bfc[9]\over \longrightarrow$}}

\setbox\boxarbredixneuf=\vbox{\vskip
28mm\offinterlineskip 
%
\centerput(0,-2){$\scriptstyle 1$}
\centerput(10,2){$\scriptstyle 4$}
\centerput(15,7){$\scriptstyle 10$}
\centerput(8,12){$\scriptstyle 9$}
\centerput(5,7){$\scriptstyle 8$}
\centerput(-10,2){$\scriptstyle 2$}
\centerput(-5,7){$\scriptstyle 3$}
\centerput(-1,13){$\scriptstyle 7$}
\centerput(-9,13){$\scriptstyle 6$}
\centerput(-0,18){$\scriptstyle 5$}
%
\segment(0,0)\dir(2,1)\long{10}
\segment(10,5)\dir(1,1)\long{5}
\segment(5,10)\dir(1,2)\long{2.5}
\segment(10,5)\dir(-1,1)\long{5}
%
\segment(0,0)\dir(-2,1)\long{10}
\segment(-10,5)\dir(1,1)\long{5}
\segment(-5,10)\dir(1,2)\long{2.5}
\segment(-5,10)\dir(-1,2)\long{2.5}
\segment(-2.5,15)\dir(1,4)\long{1.25}
\centerput(20,0){$\buildrel \bfc[7]\over \longrightarrow$}
}

\setbox\boxarbrevingt=\vbox{\vskip
28mm\offinterlineskip 
%
%
\centerput(0,-2){$\scriptstyle 1$}
\centerput(10,2){$\scriptstyle 4$}
\centerput(15,7){$\scriptstyle 10$}
\centerput(8,12){$\scriptstyle 9$}
\centerput(5,7){$\scriptstyle 8$}
\centerput(-10,2){$\scriptstyle 2$}
\centerput(-5,7){$\scriptstyle 3$}
\centerput(-1,13){$\scriptstyle 5$}
\centerput(-9,13){$\scriptstyle 6$}
\centerput(-0,18){$\scriptstyle 7$}
%
\segment(0,0)\dir(2,1)\long{10}
\segment(10,5)\dir(1,1)\long{5}
\segment(5,10)\dir(1,2)\long{2.5}
\segment(10,5)\dir(-1,1)\long{5}
%
\segment(0,0)\dir(-2,1)\long{10}
\segment(-10,5)\dir(1,1)\long{5}
\segment(-5,10)\dir(1,2)\long{2.5}
\segment(-5,10)\dir(-1,2)\long{2.5}
\segment(-2.5,15)\dir(1,4)\long{1.25}
}
\centerline{\box\boxarbredixsept\hskip4cm\box\boxarbredixhuit
\hskip4cm\box\boxarbredixneuf\hskip4cm\box\boxarbrevingt}

\bigskip
\centerline{Fig. 11}
\endinsert
\medskip


\bigskip
{\bf Remerciements}. Les auteurs tiennent \`a remercier Gabor
Hetyei pour d'utiles discussions et aussi pour leur avoir donn\'e
les r\'ef\'erences essentielles dans l'\'etude de la variation~$cd$
des ensembles partiellement ordonn\'es.

Ils remercient aussi l'arbitre anonyme pour sa lecture 
attentive et ses remarques judicieuses. En particulier,
celui-ci a indiqu\'e une autre m\'ethode pour obtenir 
la fonction g\'en\'eratrice (7.5),
qui utilise la r\'eversion des s\'eries formelles et la 
s\'erie g\'en\'eratrice des nombres de Catalan.

\vfill\eject
\bigskip\bigskip\bigskip
\centerline{\bf Bibliographie}

\nobreak
\bigskip
[An79] D. Andr\'e, D\'eveloppements de $\sec x$ et de $\tan x$,
{\sl C. R. Acad. Sc. Paris}, {\bf 88} (1879), 965-967.

[An79] D. Andr\'e, Sur les permutations altern\'ees, {\it J. Math.
Pures Appl.}, {\bf 7} (1881), 167-184. 

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

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

[FoSch71] D. Foata et
M.-P. Sch\"utzenberger, Nombres d'Euler et permutations alternantes.
Manuscrit, 71 pages, University of Florida, Gainesville, 1971.

[FoSch71] D. Foata et M.-P. Sch\"utzenberger, Nombres d'Euler et
permutations alternantes, in J. N. Srivastava et {\it al.} (eds.), {\it
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, {\it Math. Z.}, {\bf 137} (1974), 257-264.

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

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

[He96] G. Hetyei, On the $cd$-Variation Polynomials of Andr\'e
and Simsun Permutations, {\it Discrete \& Computational
Geometry}, {\bf 16} (1996), 259-276. 

[Pu93] M. Purtill, Andr\'e permutations, lexicographic shellability
and the {\it cd}-index of a convex polytope, {\it Trans. Amer.
Math. Soc.}, {\bf 338} (1993), 77-104.

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

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

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

\font\emailfont=cmtt8
\vskip 2cm
\line{\vbox{\halign{#\hfil\cr
Dominique Foata\cr
D\'epartement de math\'ematique\cr
Universit\'e Louis Pasteur\cr
7, rue Ren\'e-Descartes\cr
F-67084 Strasbourg\cr
\noalign{\smallskip}
{\sevenrm email}: {\emailfont foata@math.u-strasbg.fr}\cr
\noalign{\vskip-2pt}
{\emailfont http://cartan.u-strasbg.fr/$\sim$foata}\cr}}
\hfil
\vbox{\halign{#\hfil\cr
Guo-Niu Han\cr
{\sevenrm I.R.M.A.-C.N.R.S.}\cr
Universit\'e Louis Pasteur\cr
7, rue Ren\'e-Descartes\cr
F-67084 Strasbourg\cr
\noalign{\smallskip}
{\sevenrm email}: {\emailfont guoniu@math.u-strasbg.fr}\cr
\noalign{\vskip-2pt}
{\emailfont http://cartan.u-strasbg.fr/$\sim$guoniu}\cr}}}



\bye
