%this is a LaTeX file
%\input tex8bits
%\input OTTfont
%\input Oa4.tex
\documentstyle [12pt]{article}
\parindent=0pt
\topmargin=0cm
\textwidth=152mm
%\headheight=1cm
%\footheight=0.5cm
%\footskip=1cm
\textheight=20cm
\hoffset=-10mm
\font\sme=cmr10 at 8pt
\font\smt=cmr10 at 10pt
\def\ds{\mathop{\begin{picture}(14,2)
\setlength{\unitlength}{8mm}
\thinlines
\put(0.1,0.41){\line(1,-1){0.5}} 
\end{picture}}\nolimits}
\def\mt{\mathop{\begin{picture}(14,2)
\setlength{\unitlength}{8mm}
\thinlines
\put(0.1,-0.1){\line(1,1){0.5}} 
\end{picture}}\nolimits}
\def\hc{\mathop{\begin{picture}(14,2)
\setlength{\unitlength}{8mm}
\thinlines
\put(0.1,0.13){\line(1,0){0.5}} 
\end{picture}}\nolimits}
\def\tr{\vbox{\hrule height 0.1 pt depth 0pt width 0.8mm}}
\def\trd{\tr\,\tr\,\tr}
\def\trp{\vbox{\hrule height 0.1 pt depth 0pt width 0.4mm}}
\def\trpd{\trp\,\trp\,\trp}
\def\hd{\mathop{\begin{picture}(14,2)
\setlength{\unitlength}{8mm}
\thinlines
\put(0.1,0.14){\trd} 
\end{picture}}\nolimits}
\def\hdp{\mathop{\begin{picture}(14,2)
\setlength{\unitlength}{8mm}
\thinlines
\put(0.1,0.09){\trpd} 
\end{picture}}\nolimits}

\begin{document}
\centerline{\Large
Correspondances entre les diff\'erents types}
\vskip 2mm
\centerline{\Large  de bijections
entre le groupe sym\'etrique}
\vskip 2mm
\centerline{\Large  et les chemins de Motzkin valu\'es}
\vskip 2mm
\centerline{\bf par}
\vskip 2mm
\centerline{ Arthur RANDRIANARIVONY{\footnote
{D\'epartement de Math\'ematiques, Universit\'e Louis-Pasteur,
7, rue Ren\'e Descartes, 67084 Strasbourg Cedex, France}}}
\vskip 10mm
{\small R\'esum\'e. -- Le but de cette note est de trouver les liens entre 
les diff\'erents types de bijections entre le groupe sym\'etrique et les chemins
de Motzkin valu\'es.}
\vskip 3mm
{\bf 1. -- Introduction.}\\
Depuis quelques ann\'ees, les dev\'eloppements en fractions
continues des fonctions g\'en\'eratrices font 
l'objet d'un regain d'attention par certains combinatoristes. La th\'eorie
combinatoire des fractions continues de Flajolet [3] et l'existence des bijections entre les 
chemins de Motzkin valu\'es et le groupe sym\'etrique ([1], [4],
[5], [6]) permettent  de dev\'elopper la fonction g\'en\'eratrice
de certains polyn\^omes g\'en\'erateurs  du groupe sym\'etrique en
fraction continue de type Jacobi ou de type  Stieltjes.

En 1979, Fran\c con et Viennot [5] ont construit une bijection
entre le groupe  sym\'etrique et un ensemble de chemins de Motzkin
valu\'es app\'el\'es  {\it histoires de Laguerre}. Dix ans plus
tard, Foata et Zeilberger [4] ont  construit eux-aussi une autre
bijection entre ces deux ensembles. R\'ecemment, Clarke,
Steingr\'imsson et Zeng [2] ont trouv\'e une correspondance entre
ces  deux bijections, dont nous rappelons la construction dans le
paragraphe  suivant.

Dans cette note, nous essayons de trouver les liens
entre les autres bijections.

Rappelons qu'un chemin de Motzkin de longueur $n$ est un mot de l'alphabet 
$$\{\hc,\hd,\mt, \ds\}$$
tel que si l'on note 
$$h_i(c)= \#\{j\leq i/ \ c_j=\mt\}-\#\{j\leq i/ \ c_j=\ds\},$$ 
alors
$h_{i}(c)\geq 0$ pour tout $i$ et $h_n(c)=0$ (avec la convention $h_0(c)=0$).

$h_{i-1}(c)$ est app\'el\'e {\it niveau} du $i$-\`eme pas $c_i$ du chemin.

Le chemin $c=\mt\mt\ds\mt\mt\hc\hc\ds\hd\ds$ peut \^etre repr\'esent\'e par la figure 1.

Si un chemin de Motzkin ne poss\`ede pas de pas horizontal, on dit que c'est un chemin de Dyck.
\vskip 15mm
\hskip 2cm\begin{picture}(80,45)
\setlength{\unitlength}{8mm}
\thinlines
\put(0,0){\vector(1,0){12}}
\put(0,0){\vector(0,1){3.5}}
\multiput(1,0)(1,0){11}{\line(0,1){0.2}}
\multiput(0,1)(0,1){3}{\line(1,0){0.2}}

\put(-0.5,1){1} 
\put(-0.5,2){2} 
\put(-0.5,3){3} 

\put(-0.18,-0.75){0} 
\put(0.82,-0.75){1} 
\put(1.82,-0.75){2} 
\put(2.82,-0.75){3} 
\put(3.82,-0.75){4} 
\put(4.82,-0.75){5} 
\put(5.82,-0.76){6} 
\put(6.82,-0.75){7} 
\put(7.82,-0.75){8} 
\put(8.8,-0.75){9} 
\put(9.8,-0.75){10} 
\put(10.8,-0.75){11} 

\put(0,0){\line(1,1){2}} 
\put(2,2){\line(1,-1){1}} 
\put(3,1){\line(1,1){2}} 
\put(5,3){\line(1,-1){1}} 
\put(6,2){\line(1,0){2}} 
\put(8,2){\line(1,-1){1}} 
\multiput(8.97,1)(0.2,0){5}{\line(1,0){0.1}} 
\put(10,1){\line(1,-1){1}} 
\put(0.92,0.92){${\bullet}$} 
\put(1.92,1.92){${\bullet}$} 
\put(2.92,0.92){${\bullet}$} 
\put(3.92,1.92){${\bullet}$} 
\put(4.92,2.92){${\bullet}$} 
\put(5.92,1.92){${\bullet}$} 
\put(6.92,1.92){${\bullet}$} 
\put(7.92,1.92){${\bullet}$} 
\put(8.92,0.92){${\bullet}$} 
\put(9.92,0.92){${\bullet}$} 
\end{picture}
\vskip 8mm
\centerline{fig. 1}
\vskip 3mm
Un chemin de Motzkin valu\'e de longueur $n$ est un couple $(c,p)$ o\`u $c=c_1c_2\cdots c_n$
est un chemin de Motzkin de longueur $n$ et $p=p_1p_2\cdots p_n$ une suite
d'entiers $\geq 0$.

Si $p$ v\'erifie la condition \\
$0\leq p_i\leq h_{i-1}(c)$ si 
$c_i=\mt$ ou $\hc$, et $0\leq p_i\leq h_{i-1}(c)-1$ si 
$c_i=\ds$ ou $\hd$,\\
on dit que $(c,p)$ est une {\it histoire de Laguerre}.

Si $c$ est un chemin de Dyck et $p_i=0$ pour 
$c_i=\mt$, et, $0\leq p_i\leq \left\lceil \displaystyle{h_{i-1}(c)\over 2}
\right\rceil-1$ pour $c_i=\ds$ o\`u $\lceil x\rceil$ est le plus petit
entier $\geq x$,\\
on dit que $(c,p)$ est une {\it histoire de Laguerre subdivis\'ee}.
\vskip 3mm
Un chemin de Motzkin bivalu\'e de longueur $n$ est un couple $(c,\xi)$ o\`u 
$c=c_1c_2\cdots c_n$ est un chemin de Motzkin de longueur $n$ et 
$\xi=(\xi_1, \ldots,\xi_n)$ une suite de couples d'entiers $\geq 0$
telle que, si $\xi_i=(\xi_i^-,\xi_i^+)$ $(1\leq i\leq n)$, alors\\
$\xi_i^-=\xi_i^+=0$ si $c_i=\mt$;\\
$0\leq \xi_i^-\leq h_{i-1}(c)-1$,\ $0\leq \xi_i^+\leq h_{i-1}(c)-1$ si 
$c_i=\ds$;\\
$0\leq \xi_i^-\leq h_{i-1}(c)-1$,\ $\xi_i^+=0$ si $c_i=\hd$;\\
$\xi_i^-=0$,\ $0\leq \xi_i^+\leq h_{i-1}(c)$ si $c_i=\hc$.
\vskip 2mm
On note respectivement $HL(n)$, $HLS(2n)$ et $CB(n)$
l'ensemble des histoires de Laguerre de longueur $n$, des histoires de 
Laguerre subdivis\'ees de longueur $2n$
et l'ensemble des chemins de Motzkin bivalu\'es de longueur $n$.
\vskip 3.5mm

{\bf 2. -- Correspondance entre la bijection de Fran\c con - Viennot et la bijection
de Foata-Zeilberger.}
\vskip 2mm
\'Etant donn\'ee une permutation $\sigma$ de $[n]$, on dit que $\sigma(i)$ $(1\leq i\leq n)$ est:\\
-- un pic de $\sigma$ si $\sigma(i-1)<\sigma(i)>\sigma(i+1)$;\\
-- un creux de $\sigma$ si $\sigma(i-1)>\sigma(i)<\sigma(i+1)$;\\
-- une double mont\'ee de $\sigma$ si $\sigma(i-1)<\sigma(i)<\sigma(i+1)$;\\
-- une double descente de $\sigma$ si $\sigma(i-1)>\sigma(i)>\sigma(i+1)$;\\
avec la convention $\sigma(0)=\sigma(n+1)=0$.
\vskip 2mm
Si $\sigma^{-1}(i)<i>\sigma(i)$ (resp. $\sigma^{-1}(i)>i<\sigma(i)$, 
$\sigma^{-1}(i)<i<\sigma(i)$, $\sigma^{-1}(i)\geq i\geq \sigma(i)$), on dit que
$i$ est un pic (resp. un creux, une double mont\'ee, une double descente)
de cycle de $\sigma$.
\vskip 3mm
{\bf Th\'eor\`eme 1 [Fran\c con-Viennot [5]]}. -- Il existe une bijection $\Psi_{FV}:S_{n+1}
\longrightarrow \Gamma_n$, 
$\sigma\mapsto \Psi_{FV}(\sigma)=(c,p)$ telle que, pour $1\leq i\leq n$,\\
$\begin{array}{l}
i\ \hbox{ est un pic de $\sigma$ si et seulement si $c_i=\ds$};\\
i\ \hbox{est un creux de $\sigma$ si et seulement si $c_i=\mt$};\\
i\ \hbox{est une double mont\'ee de $\sigma$ si et seulement si $c_i=\hc$};\\
i\ \hbox{est une double descente de $\sigma$ si et seulement si $c_i=\hd$}.\\[0.2cm]
\end{array}$\hfill (1)

o\`u $\Gamma_n$ d\'esigne l'ensemble des chemins de Motzkin valu\'es $(c,p)$ de longueur 
$n$ v\'erifiant 
$\ 0\leq p_i\leq h_{i-1}(c)$ pour tout $i$.
\vskip 2mm
{\it Construction}. Soient $\sigma\in S_{n+1}$ et $i\in [n]$. On d\'ecompose 
$\sigma$ en une suite de mots $m_0M_0\cdots
m_kM_km_{k+1}$, appel\'ee $i$-d\'ecomposition de $\sigma$, telle que 
$M_0,\ldots, M_k$ soient des sous-mots non vides de $\sigma$ ne 
contenant que des lettres $\geq i$, et $m_0,\ldots, m_{k+1}$ des sous-mots 
non vides, sauf \'eventuellement $m_0$ et $m_{k+1}$, et ne contenant que des 
lettres $<i$. De la relation (1), on a:
$$
h_{i-1}(c)=\sum_{j=0}^{k+1}(\hbox{nb de creux dans}\ m_j-\ \hbox{nb de
pics dans}\ m_j). 
$$
Or,
 
\centerline{nb de creux dans $m_0$ (resp. $m_{k+1}$) =
nb de pics dans $m_0$ (resp. $m_{k+1}$)}
et,

\centerline{ nb de creux dans $m_j$ = 1 + nb de pics dans $m_j$\quad 
$(1\leq j\leq k)$.}

Par cons\'equent, $h_{i-1}(c)=k$ et on pose $p_i=l$ si $i\in M_l$. On a bien 
$0\leq p_i\leq h_{i-1}(c)$.\\[2mm]
Si $\sigma(n+1)=n+1$, la $i$-d\'ecomposition de $\sigma$ est 
$m_0M_0\cdots m_kM_k$. Dans ce cas, si $i$
est un pic ou une double descente de $\sigma$, n\'ecessairement $i\notin M_k$.
Ce qui implique que $k\neq 0$. Par cons\'equent, si $c_i=\setminus$ ou $\hd$,
$0\leq p_i\leq h_{i-1}(c)-1$.
\vskip 2mm
Comme toute permutation $\sigma$ de $[n+1]$ telle que $\sigma(n+1)=n+1$ peut
\^etre identifi\'ee \`a une permutation de $[n]$, alors 
on a le th\'eor\`eme suivant \'equivalent au pr\'ec\'edent.
\vskip 3mm
{\bf Th\'eor\`eme 2 [Fran\c con-Viennot]}. --  Il existe une bijection 
$\Psi'_{FV}:S_n\longrightarrow HL(n)$, $\sigma\mapsto (c,p)$ telle que, pour
$1\leq i\leq n$,\\
$\begin{array}{l}
i\ \hbox{ est un pic de $\sigma$ si et seulement si $c_i=\ds$};\\
i\ \hbox{est un creux de $\sigma$ si et seulement si $c_i=\mt$};\\
i\ \hbox{est une double mont\'ee de $\sigma$ si et seulement si $c_i=\hc$};\\
i\ \hbox{est une double descente de $\sigma$ si et seulement si $c_i=\hd$}.\\[0.2cm]
\end{array}$\hfill (2)

avec la convention $\sigma(0)=0$ et $\sigma(n+1)=n+1$. 
\vskip 3mm
{\bf Remarque}. 
Si $B_0B_1\cdots B_r$ est la d\'ecomposition de $\sigma$ en une suite de 
blocs telle que $B_j$ soit un sous-mot d\'ecroissant et maximal de 
$\sigma$ pour tout $j$ (voir [2]),
et $m_0M_0\cdots m_kM_k$ la $i$-d\'ecomposition de $\sigma$, on note
$B_{i_j}$ le bloc contenant la derni\`ere lettre de $M_j$ 
$(1\leq j\leq k-1)$.
Soit $M_l$ le sous-mot contenant $i$. \\
Si $M_l\neq i$, $B_{i_0}$, $B_{i_1}$,$\ldots$, $B_{i_{k-1}}$ sont les seuls
blocs qui embrassent $i$, c'est-\`a-dire les blocs $B_j$ tels que
$O(B_j)<i<F(B_j)$ o\`u $O(B_j)$ et 
$F(B_j)$ sont respectivement la plus petite et la plus grande lettre de $B_j$
respectivement appel\'ees ouvrant et fermant de $B_j$.\\
Si $M_l=i$, il y a exactement $k-1$ blocs qui embrassent $i$.\\
On en d\'eduit que 
\vskip 2mm
$h_{i-1}(c)=\cases{
\#\{\hbox{blocs de $\sigma$
qui embrassent $i$}\}& si $i$ n'est pas un pic;\cr 
\#\{\hbox{blocs de $\sigma$
qui embrassent $i$}\}+1& si $i$ est un pic.\cr 
}$
\vskip 2mm
et $p_i$ est \'egal au nombre de blocs embrassant $i$ et situ\'es \`a 
gauche du bloc qui le contient.\\[2mm]
{\it Exemple} 1. Soit $\sigma=8\ 2\ 3\ 1\ 10\ 9\ 4\ 6\ 7\ 5$. Sa d\'ecomposition en
blocs de descentes est $8\ 2\ - 3\ 1\ - 10\ 9\ 4\ - 6\ - 7\ 5$. Si 
$(c,p)=\Psi'_{FV}(\sigma)$, le chemin $c$ est repr\'esent\'e par la figure 2
et $p=0\ 0\ 1\ 1\ 2\ 2\ 2\ 0\ 0\ 0$.
\vskip 16mm
\hskip 2cm\begin{picture}(80,45)
\setlength{\unitlength}{8mm}
\thinlines
\put(0,0){\vector(1,0){11}}
\put(0,0){\vector(0,1){3.5}}
\multiput(1,0)(1,0){10}{\line(0,1){0.2}}
\multiput(0,1)(0,1){3}{\line(1,0){0.2}}

\put(-0.5,1){1} 
\put(-0.5,2){2} 
\put(-0.5,3){3} 

\put(-0.18,-0.75){0} 
\put(0.82,-0.75){1} 
\put(1.82,-0.75){2} 
\put(2.82,-0.75){3} 
\put(3.82,-0.75){4} 
\put(4.82,-0.75){5} 
\put(5.82,-0.76){6} 
\put(6.82,-0.75){7} 
\put(7.82,-0.75){8} 
\put(8.8,-0.75){9} 
\put(9.8,-0.75){10} 

\put(0,0){\line(1,1){2}} 
\put(2,2){\line(1,-1){1}} 
\put(3,1){\line(1,1){1}} 
\put(4,2){\line(1,1){1}} 
\put(5,3){\line(1,0){1}} 
\put(6,3){\line(1,-1){2}} 
\multiput(7.97,1)(0.2,0){5}{\line(1,0){0.1}} 
\put(9,1){\line(1,-1){1}} 
\put(0.88,0.88){${\bullet}$} 
\put(1.88,1.88){${\bullet}$} 
\put(2.88,0.88){${\bullet}$} 
\put(3.88,1.88){${\bullet}$} 
\put(4.88,2.88){${\bullet}$} 
\put(5.88,2.88){${\bullet}$} 
\put(6.88,1.88){${\bullet}$} 
\put(7.88,0.88){${\bullet}$} 
\put(8.88,0.88){${\bullet}$} 
\end{picture}
\vskip 8mm
\centerline {fig. 2}

\vskip 3mm
{\bf Th\'eor\`eme 3 [Foata-Zeilberger [4]]}. --  Il existe une bijection 
$\Psi_{FZ}:$\\ $S_n\longrightarrow HL(n)$, $\sigma\mapsto (c,p)$ telle que, pour
$1\leq i\leq n$,\\
$\begin{array}{l}
i\ \hbox{ est un pic de cycle de $\sigma$ si et seulement si $c_i=\ds$};\\
i\ \hbox{est un creux de cycle de $\sigma$ si et seulement si $c_i=\mt$};\\
i\ \hbox{est une double mont\'ee de cycle de $\sigma$ si et seulement si $c_i=\hd$};\\
i\ \hbox{est une double descente de cycle de $\sigma$ si et seulement si $c_i=\hc$}.\\[0.2cm]
\end{array}$\hfill (3)
\vskip 2mm
Soient $\sigma(i_1), \sigma(i_2),\ldots, \sigma(i_k)$ (resp.
$\sigma(j_1), \sigma(j_2),\ldots, \sigma(j_{n-k})$) les exc\'edances
(resp. les non-exc\'edances) de $\sigma$, c'est-\`a-dire $\sigma(i_l)>i_l$
(resp. $\sigma(j_l)\leq j_l$) pour tout $l$. On note:\\
$$
\sigma_{exc}=\left(\begin{tabular}{cccc}
$i_1$&$i_2$&$\cdots$&$i_k$\\ $\sigma(i_1)$&$\sigma(i_2)$&$\cdots$&
$\sigma(i_k)$\\ 
\end{tabular}\right)\quad \hbox{et}\quad
\sigma_{nex}=\left(\begin{tabular}{cccc}
$j_1$&$j_2$&$\cdots$&$j_{n-k}$\\ $\sigma(j_1)$&$\sigma(j_2)$&$\cdots$&
$\sigma(j_{n-k})$\\ 
\end{tabular}\right)
$$
Par construction,\\ 
$p_{\sigma(i_1)}p_{\sigma(i_2)}\cdots p_{\sigma(i_k)}$ est la table 
d'inversion \`a gauche de $\sigma_{exc}$;

$p_{\sigma(j_1)}p_{\sigma(j_2)}\cdots p_{\sigma(j_{n-k})}$ est la table 
d'inversion \`a droite de $\sigma_{nex}$.

Par suite, on obtient:
$$
p_i=\cases{
\#\{j<\sigma^{-1}(i);\ \sigma(j)>i\}& si\ $\sigma^{-1}(i)<i$;\cr
\#\{j>\sigma^{-1}(i);\ \sigma(j)<i\}& si\ $\sigma^{-1}(i)\geq i$.\cr
}\eqno (4)$$
D'autre part, on a:
$$
h_{i-1}(c)=\#\{j<i;\ \sigma(j)\geq i\}
=\#\{j<i;\ \sigma^{-1}(j)\geq i\}\eqno (5)
$$
En effet, la relation (3) entra\^\i ne que\\
$\begin{array}{ll}
h_i(c)&=\#\{j\leq i;\ j<\sigma^{-1}(j);\ j<\sigma(j)\}
-\#\{j\leq i;\ j>\sigma^{-1}(j);\ j>\sigma(j)\}\\
&=\#\{j\leq i;\ j<\sigma(j)\}-\#\{j\leq i;\ j\geq \sigma^{-1}(j);\ 
j<\sigma(j)\}\\
&\hskip 6cm -\#\{j\leq i;\ j>\sigma^{-1}(j);\ j>\sigma(j)\}\\
&=\#\{j\leq i;\ j<\sigma(j)\}-\#\{j\leq i;\ j>\sigma^{-1}(j)\}\\
\end{array}$\\
Or,\\
$\#\{j\leq i;\ j<\sigma(j)\}=\#\{j\leq i;\ \sigma(j)>i\}+
\#\{j\leq i;\ j<\sigma(j)\leq i\}$\\
et, $\#\{j\leq i;\ j<\sigma(j)\leq i\}=\#\{j\leq i;\ j>\sigma^{-1}(j)\}$.\\[3mm]
{\it Exemple} 2. Soient $\sigma=8\ 3\ 1\ 9\ 7\ 5\ 6\ 4\ 10\ 2$ et
$(c,p)=\psi_{FZ}(\sigma)$.
La d\'ecomposition en cycles de $\sigma$ est
$(1\ 8\ 4\ 9\ 10\ 2\ 3)(5\ 7\ 6)$. Donc $c$ est d\'etermin\'e par la figure 2.\\
D'autre part, on a:
$$
\sigma_{exc}=\left(\begin{tabular}{ccccc}
1&2&4&5&9\\ 8&3&9&7&10\\ 
\end{tabular}\right)\quad \hbox{et}\quad
\sigma_{nex}=\left(\begin{tabular}{ccccc}
3&6&7&8&10\\ 1&5&6&4&2\\ 
\end{tabular}\right)
$$
Par suite
$p=0\ 0\ 1\ 1\ 2\ 2\ 2\ 0\ 0\ 0$.
\vskip 3mm
R\'ecemment, Clarke, Steingr\'\i msson et Zeng [2] ont prouv\'e le 
th\'eor\`eme suivant.
\vskip 2mm 
{\bf Th\'eor\`eme 4}. --  Il existe une bijection $\Phi$ de $S_n$ sur $S_n$
telle que $\Psi'_{FV}=\Psi_{FZ}\circ \Phi$.\\[2mm]
{\it Construction de $\Phi$}. Soit $\pi\in S_n$, $\pi=B_0B_1\cdots B_r$ sa 
d\'ecomposition en blocs de descentes. Pour tout $i\in [n]$, on note 
$e_i$ le nombre de blocs embrassant $i$ et situ\'es \`a sa gauche.
On pose d'autre part\\
$F=\{i\in [n];\ i\ \hbox{est un creux ou une double descente de}\ \pi\}=
\{i_1,i_2,\ldots, i_k\}$;\\
$F'=\{i\in [n];\ i\ \hbox{est un pic ou une double descente de}\ \pi\}$;\\
$G=\{i\in [n];\ i\ \hbox{est un pic ou une double mont\'ee de}\ \pi\}=
\{j_1,j_2,\ldots, j_{n-k}\}$;\\
$G'=\{i\in [n];\ i\ \hbox{est un creux ou une double mont\'ee de}\ \pi\}$.\\[2mm]
On d\'efinit $\Phi(\pi)=\sigma$ de la fa\c con suivante:\\
(i)\quad $\sigma(F)=F'$ tel que 
$e_{\sigma(i_1)}e_{\sigma(i_2)}\cdots e_{\sigma(i_k)}$ soit la table d'inversion
\`a gauche de\\ $\sigma(i_1)\sigma(i_2)\cdots \sigma(i_k)$;\\
(ii)\quad $\sigma(G)=G'$ tel que 
$e_{\sigma(j_1)}e_{\sigma(j_2)}\cdots e_{\sigma(j_{n-k})}$ soit la table d'inversion
\`a droite de\\ $\sigma(j_1)\sigma(j_2)\cdots \sigma(j_{n-k})$.
\vskip 2mm
{\it Exemple} 3. Soit $\pi=8\ 2\ 3\ 1\ 10\ 9\ 4\ 6\ 7\ 5$. Sa d\'ecomposition en
blocs de descentes est $8\ 2\ - 3\ 1\ - 10\ 9\ 4\ - 6\ - 7\ 5$. On a
$e=e_1e_2\cdots e_{10}\ =0\ 0\ 1\ 1\ 2\ 2\ 2\ 0\ 0\ 0$.\\ D'autre part,\\
$F=\{1,2,4,5,9\}$, $F'=\{3,7,8,9,10\}$, $G=\{3,6,7,8,10\}$ et 
$G'=\{1,2,4,5,6\}$.\\
On a donc
$$
\sigma_{exc}=\left(\begin{tabular}{ccccc}
1&2&4&5&9\\ 8&3&9&7&10\\ 
\end{tabular}\right)\quad \hbox{et}\quad
\sigma_{nex}=\left(\begin{tabular}{ccccc}
3&6&7&8&10\\ 1&5&6&4&2\\ 
\end{tabular}\right)
$$
Par cons\'equent, $\Phi(\pi)=\sigma=8\ 3\ 1\ 9\ 7\ 5\ 6\ 4\ 10\ 2$.

D'apr\`es les exemples 1 et 2, on a bien $\Psi'_{FV}(\pi)=\Psi_{FZ}(\sigma)$
\vskip 2mm

{\bf 3. -- Correspondance entre la bijection de Foata-Zeilberger et la
bijection de Biane.}\\
Dans son article [1], Biane a d\'emontr\'e le th\'eor\`eme suivant.

{\bf Th\'eor\`eme 5}. -- Il existe une bijection $\Psi_B$ de
$S_n$ sur
$CB(n)$ telle que, si $\Psi_B(\sigma)=(c,\xi)$, alors,
pour $1\leq i\leq n$,\\
$\begin{array}{l}
i\ \hbox{ est un pic de cycle de $\sigma$ si et seulement si $c_i=\ds$};\\
i\ \hbox{est un creux de cycle de $\sigma$ si et seulement si $c_i=\mt$};\\
i\ \hbox{est une double mont\'ee de cycle de $\sigma$ si et seulement si $c_i=\hd$};\\
i\ \hbox{est une double descente de cycle de $\sigma$ si et seulement si $c_i=\hc$}.\\[0.2cm]
\end{array}$\hfill (6)
\vskip 2mm
Par construction de $\Psi_B$, on a:
$$\begin{array}{l}
\xi_i^-=\cases{
=0& si\ $\sigma^{-1}(i)\geq i$;\cr
\#\{j<\sigma^{-1}(i);\ \sigma(j)>i\}& si\ $\sigma^{-1}(i)<i$;\cr}\\
\xi_i^+=\cases{
=0& si\ $\sigma(i)>i$;\cr
\#\{j<\sigma(i);\ \sigma^{-1}(j)>i\}& si\ $\sigma(i)\leq i$.\cr}.\\
\end{array}\eqno (7)
$$
\vskip 2mm
{\it Exemple} 4. Soit $\sigma=5\ 3\ 1\ 8\ 7\ 2\ 6\ 4\ 11\ 10\ 9$. Elle est
repr\'esent\'ee par le diagramme suivant:
\vskip 8mm
\hskip 2cm\begin{picture}(80,25)
\setlength{\unitlength}{8mm}
\thinlines
\multiput(-0.1,-0.2)(1,0){11}{$\bullet$}
\multiput(-0.1,0.95)(1,0){11}{$\bullet$}
\put(-0.18,-0.75){1} 
\put(0.82,-0.75){2} 
\put(1.82,-0.75){3} 
\put(2.82,-0.75){4} 
\put(3.82,-0.75){5} 
\put(4.82,-0.75){6} 
\put(5.82,-0.75){7} 
\put(6.82,-0.75){8} 
\put(7.82,-0.75){9} 
\put(8.8,-0.75){10} 
\put(9.8,-0.75){11} 
\put(-0.18,1.25){1} 
\put(0.82,1.25){2} 
\put(1.82,1.25){3} 
\put(2.82,1.25){4} 
\put(3.82,1.25){5} 
\put(4.82,1.25){6} 
\put(5.82,1.25){7} 
\put(6.82,1.25){8} 
\put(7.82,1.25){9} 
\put(8.8,1.25){10} 
\put(9.8,1.25){11} 
\put(0,1){\vector(4,-1){4}} 
\put(1,1){\vector(1,-1){1}} 
\put(2,1){\vector(-2,-1){2}} 
\put(3,1){\vector(4,-1){4}} 
\put(4,1){\vector(2,-1){2}} 
\put(5,1){\vector(-4,-1){4}} 
\put(6,1){\vector(-1,-1){1}} 
\put(7,1){\vector(-4,-1){4}} 
\put(8,1){\vector(2,-1){2}} 
\put(9,1){\vector(0,-1){1}} 
\put(10,1){\vector(-2,-1){2}} 
\end{picture}
\vskip 10mm
Si $(c,\xi)=\psi_B(\sigma)$, alors le chemin $c$ est repr\'esent\'e par la figure
3 et\\ $\xi=(0,0)(0,0)(1,0)(0,0)(0,0)(0,0)(1,1)(0,0)(0,0)(0,1)(0,0)$
\vskip 10mm
\hskip 2cm\begin{picture}(80,40)
\setlength{\unitlength}{8mm}
\thinlines
\put(0,0){\vector(1,0){12}}
\put(0,0){\vector(0,1){3}}
\multiput(1,0)(1,0){11}{\line(0,1){0.2}}
\multiput(0,1)(0,1){2}{\line(1,0){0.2}}

\put(-0.5,1){1} 
\put(-0.5,2){2} 

\put(-0.18,-0.75){0} 
\put(0.82,-0.75){1} 
\put(1.82,-0.75){2} 
\put(2.82,-0.75){3} 
\put(3.82,-0.75){4} 
\put(4.82,-0.75){5} 
\put(5.82,-0.76){6} 
\put(6.82,-0.75){7} 
\put(7.82,-0.75){8} 
\put(8.8,-0.75){9} 
\put(9.8,-0.75){10} 
\put(10.8,-0.75){11} 

\put(0,0){\line(1,1){2}} 
\put(2,2){\line(1,-1){1}} 
\put(3,1){\line(1,1){1}} 
\multiput(3.97,2)(0.2,0){5}{\line(1,0){0.1}} 
\put(5,2){\line(1,0){1}} 
\put(6,2){\line(1,-1){2}} 
\put(8,0){\line(1,1){1}} 
\put(9,1){\line(1,0){1}} 
\put(10,1){\line(1,-1){1}} 
\put(0.92,0.92){${\bullet}$} 
\put(1.92,1.92){${\bullet}$} 
\put(2.92,0.92){${\bullet}$} 
\put(3.92,1.92){${\bullet}$} 
\put(4.92,1.92){${\bullet}$} 
\put(5.92,1.92){${\bullet}$} 
\put(6.92,0.92){${\bullet}$} 
\put(7.92,-0.08){${\bullet}$} 
\put(8.92,0.92){${\bullet}$} 
\put(9.92,0.92){${\bullet}$} 
\end{picture}
\vskip 7mm
\centerline{fig. 3}
\vskip 3mm
{\bf Th\'eor\`eme 6}. -- Il existe une bijection $\theta$ de $CB(n)$ sur
$HL(n)$ telle que $\Psi_{FZ}=\theta\circ\Psi_B$.
\vskip 2mm
{\it D\'emonstration}. Soient $\sigma\in S_n$ et $(c,\xi)=\Psi_B(\sigma)$. 
Notons\\
$A=\{j;\ c_j=\mt\ \hbox{ou}\ \hc\}=\{i_1,\ldots, i_k\}$ et
$B=\{j;\ c_j=\ds\ \hbox{ou}\ \hc\}=\{j_1,\ldots, j_k\}$.\\
On a n\'ecessairement $i_1=1, j_k=n$ et $i_l\leq j_l$ pour tout $l$.\\
Remarquons d'autre part que, pour $1\leq l\leq k$,\\
$\xi_{j_l}^+\leq h_{i-1}(c)-1\leq k-(l-1)-1=k-l$ si $c_{j_l}=\ds$;\\
$\xi_{j_l}^+\leq h_{i-1}(c)\leq (k-1)-(l-1)=k-l$ si $c_{j_l}=\hc$.\\
Soit donc $\alpha$ la bijection de A sur B telle que 
$\xi_{\alpha(i_1)}^+\xi_{\alpha(i_2)}^+\cdots\xi_{\alpha(i_k)}^+$ soit 
la table d'inversion \`a gauche de $\alpha(i_1)\alpha(i_2)\cdots\alpha(i_k)$. Soit
 $p=p_1p_2\cdots p_n$ la suite d\'efinie par:
$$
p_i=\xi_i^-\ \hbox{si}\ c_i=\ds\ \hbox{ou}\ \hd\ \hbox{et}\
p_i=\xi_{\alpha(i)}^+\ \hbox{si}\ c_i=\mt\ \hbox{ou}\ \hc.\eqno (8) 
$$
Montrons que $\theta: (c,\xi)\mapsto (c,p)$ applique bijectivement
$CB(n)$ sur $HL(n)$ et que $(c,p)=\Psi_{FZ}(\sigma)$. 
Pour cela, montrons que $\alpha(i)\geq i$ pour
tout $i\in A$.\\
Par construction, $\alpha^{-1}(j_1)$ est le $m_1$-\`eme \'el\'ement de A o\`u
$m_1=\xi_{j_1}^++1$: $\alpha^{-1}(j_1)=i_{m_1}$.\\
Si $c_{j_1}=\ds$,\\
 $m_1\leq h_{j_1-1}=\#\{j<j_1;\ c_j=\mt\}
-\#\{j<j_1;\ c_j=\ds\}=\#\{j<j_1;\ c_j=\mt\}$.\\
On a dans ce cas $i_1<j_1, i_2<j_1,\ldots, i_{m_1}<j_1$.\\
Si $c_{j_1}=\hc$, $j_1\in A$ et $m_1-1\leq h_{j_1-1}=\#\{j<j_1;\ c_j=\mt\}$.\\
Par cons\'equent, $i_1<j_1, i_2<j_1,\ldots, i_{m_1-1}<j_1$ et par suite
$i_{m_1}\leq j_1$.\\
Dans les deux cas, on a toujours $\alpha^{-1}(j_1)\leq j_1$.\\
Soit maintenant $\alpha_1$ la restriction de $\alpha$ \`a $A_1=A\setminus 
\{i_{m_1}\}$. 
$\xi_{\alpha(i_1)}^+\cdots\xi_{\alpha(i_{m_1-1})}^+
\xi_{\alpha(i_{m_1+1})}^+\cdots\xi_{\alpha(i_k)}^+$ \'etant la table 
d'inversion \`a gauche de $\alpha_1(i_1)\alpha_1(i_{m_1-1})
\alpha_1(i_{m_1+1})\cdots\alpha_1(i_k)$, on peut appliquer le r\'esultat 
pr\'ec\'edent \`a $\alpha_1$: $i_{m_2}=\alpha_1^{-1}(j_2)\leq j_2$, c'est-\`a-dire
$\alpha^{-1}(j_2)\leq j_2$.\\
Par it\'eration, on obtient $\alpha^{-1}(j_l)\leq j_l$ pour tout $l$.

Ainsi, pour tout $i\in [n]$,
$$\begin{array}{ll}
h_{i-1}(c)&=\#\{j<i;\ j\in A\}-\#\{j<i;\ j\in B\}\\
&=\#\{j<i;\ j\in A\}-\#\{j<i;\ j\in A,\ \alpha(j)<i\}\\
&=\#\{j<i;\ j\in A,\ \alpha(j)\geq i\}.\\
\end{array}\eqno (9)
$$
Il en r\'esulte que,\\
si $c_i=\ds$ ou $\hd$, $p_i=\xi_i^-\leq h_{i-1}(c)-1$;\\
si $c_i=\mt$ ou $\hc$, $p_i=\xi_{\alpha(i)}^+
=\#\{k<i;\ \alpha(k)>\alpha(i)\}
\leq \#\{k<i;\ \alpha(k)>i\}\leq h_{i-1}(c)$.

Ce qui prouve que $(c,p)\in HL(n)$. Par ailleurs, puisque
$\alpha$ est bijective, $\theta$ est clairement bijective.\\
Enfin, les relations (3) et (6) entra\^\i nent que les chemins
de Motzkin associ\'es \`a $\sigma$ respectivement par $\Psi_B$ 
et $\Psi_{FZ}$ sont identiques. De plus, on d\'eduit des
relations (5) et (9) que $\alpha$ est la restriction de 
$\sigma^{-1}$ \`a A. Compte tenu des relations (4), (7) et (8),
on a enfin $\Psi_{FZ}(\sigma)=(c,p)$.
\vskip 3mm
{\it Exemple} 5. Prenons le chemin bivalu\'e $(c,\xi)$ d\'efini dans l'exemple 4.
Si $(c,p)=\theta(c,\xi)$, on a:
$$
\alpha=\left(\begin{tabular}{cccccc}
1&2&4&6&9&10\\  3&6&8&7&11&10\\ 
\end{tabular}\right)\quad \hbox{et}\quad 
p=0\ 0\ 1\ 0\ 0\ 1\ 1\ 0\ 0\ 1\ 0
$$
Or, si $\sigma=\psi_{FZ}^{-1}(c,p)$, on a

$$
\sigma_{exc}=\left(\begin{tabular}{ccccc}
1&2&4&5&9\\  5&3&9&7&11\\ 
\end{tabular}\right)\quad \hbox{et}\quad
\sigma_{nex}=\left(\begin{tabular}{cccccc}
3&6&7&8&10&11\\ 1&2&6&4&10&9\\ 
\end{tabular}\right)
$$
Donc $\sigma=5\ 3\ 1\ 8\ 7\ 2\ 6\ 4\ 11\ 10\ 9$.\\
D'apr\`es l'exemple 4, on a alors 
$\Psi_{FZ}(\sigma)=\theta\circ\Psi_B(\sigma)$.

\vskip 3mm
{\bf 4. -- Correspondance entre la bijection de Biane et la bijection 
de M\'edicis-Viennot}.\\
de M\'edicis  et Viennot [6] ont construit en trois \'etapes une 
bijection
entre le groupe sym\'etrique et les histoires de Laguerre subdivis\'ees,
qui peut \^etre traduite par le th\'eor\`eme suivant.\\
{\bf Th\'eor\`eme 7.} -- L'application 
$\Psi_{MV}: \sigma\mapsto (\gamma,p)$ d\'efinie par\\
$\begin{array}{ll}
(i)& \left\{\begin{array}{lll}
\gamma_{2i-1}&=\ds& \hbox{si et seulement si}\ \sigma^{-1}(i)<i;\\
\gamma_{2i}&=\ds& \hbox{si et seulement si}\ \sigma(i)\leq i;\\
\end{array}\right.\\
(ii)&\left\{\begin{array}{lll}
p_i&=0& si\ \gamma_i=\mt;\\
p_{2i-1}&=\#\{j<\sigma^{-1}(i);\ \sigma(j)>i\}
& si\ \gamma_{2i-1}=\ds;\\
p_{2i}&=\#\{j<\sigma(i);\ \sigma^{-1}(j)>i\}
& si\ \gamma_{2i}=\ds.\\
\end{array}\right.\\
\end{array}\hfill (10)$\\
est une bijection de $S_n$ sur $HLS(2n)$.
\vskip 12mm
\begin{picture}(80,50)
\setlength{\unitlength}{8mm}
\thinlines
\put(0,2){\vector(2,-1){4}}
\put(2,2){\vector(1,-2){1}}
\multiput(-0.15,2)(2,0){2}{${\bullet}$} 
\multiput(2.9,-0.2)(1,0){2}{${\bullet}$} 
\put(-0.25,2.3){$j$}
\put(1.55,2.3){$\sigma^{-1}(i)$}
\put(2.85,-0.5){$i$}
\put(3.75,-0.5){$\sigma(j)$}
\put(1.5,-1.75){$(a)$}

\put(6.85,2){\vector(-1,-2){1}}
\put(6.55,2.3){$\sigma^{-1}(i)$}
\put(5.85,-0.5){$i$}
\put(5.8,-0.2){$\bullet$}
\put(6.82,2){$\bullet$}
\put(6.25,-1.75){$(b)$}

\put(9,2){\vector(1,-2){1}}
\put(8.85,2.3){$i$}
\put(9.55,-0.55){$\sigma(i)$}
\put(9.9,-0.2){$\bullet$}
\put(8.82,2){$\bullet$}
\put(9.25,-1.75){$(c)$}


\put(14,2){\vector(0,-1){2}}
\put(16,2){\vector(-3,-2){3}}
\multiput(13.8,2)(2.1,0){2}{${\bullet}$} 
\multiput(12.9,-0.2)(1,0){2}{${\bullet}$} 
\put(13.9,2.3){$i$}
\put(15.75,2.3){$\sigma^{-1}(j)$}
\put(12.85,-0.5){$j$}
\put(13.8,-0.5){$\sigma(i)$}
\put(14,-1.75){$(d)$}


\end{picture}
\vskip 20mm
$(a):
\gamma_{2i-1}=\ds,\ p_{2i-1}=\#\{j<\sigma^{-1}(i); \sigma(j)>i\}$\\
$(b): \gamma_{2i-1}=\mt,\  p_{2i-1}=0$\\
$(c): \gamma_{2i}=\mt,\ p_{2i}=0$\\
$(d): \gamma_{2i}=\ds,\
p_{2i}=\#\{j<\sigma(i);\ \sigma^{-1}(j)>i\}$
\vskip 3mm
Soit $\sigma\in S_n$, $(\gamma,p)=\Psi_{MV}(\sigma)$. On a:\\
$\begin{array}{rl}
h_{2i}(\gamma)=&\#\{j\leq 2i;\ \gamma_j=\mt\}
-\#\{j\leq 2i;\ \gamma_j=\ds\}\\
=&\#\{j\leq i;\ \sigma(j)>j\}+\#\{j\leq i;\ \sigma^{-1}(j)\geq j\}\\
&-\#\{j\leq i;\ \sigma(j)\leq j\}-\#\{j\leq i;\ \sigma^{-1}(j)< j\}\\
\end{array}$\\
$\begin{array}{ll}
\hbox{Or},\ \#\{j\leq i;\ \sigma(j)>j\}&=\#\{j\leq i;\ \sigma(j)>i\}
+\#\{j\leq i;\ j<\sigma(j)\leq i\}\\
&=\#\{j\leq i;\ \sigma(j)>i\}
+\#\{k\leq i;\ \sigma^{-1}(k)<k\}\\
\end{array}$\\
$\begin{array}{ll}
\hbox{et}\ \#\{j\leq i;\ \sigma^{-1}(j)\geq j\}&=\#\{j\leq i;\ \sigma^{-1}(j)>i\}
+\#\{j\leq i;\ j\leq \sigma^{-1}(j)\leq i\}\\
&=\#\{j\leq i;\ \sigma^{-1}(j)>i\}
+\#\{k\leq i;\ \sigma(k)\leq k\}.\\
\end{array}$\\
Donc 
$$\begin{array}{ll}
h_{2i}(\gamma)&=\#\{j\leq i;\ \sigma(j)>i\}
+\#\{j\leq i;\ \sigma^{-1}(j)>i\}\\
&=\#\{j\leq i;\ \sigma(j)>i\}+i-\#\{j\leq i;\ \sigma^{-1}(j)\leq i\}\\
&=\#\{j\leq i;\ \sigma(j)>i\}+i-\#\{k\leq i;\ \sigma(k)\leq i\}.\\
\end{array}
$$
D'o\`u
$$
h_{2i}(\gamma)=2\#\{j\leq i;\ \sigma(j)>i\}=2\#\{j\leq i;\ 
\sigma^{-1}(j)>i\}.
$$
On d\'emontre de m\^eme que
$$
h_{2i-1}(\gamma)=2\#\{j<i;\ \sigma(j)>i\}+1
=2\#\{j\leq i;\ \sigma^{-1}(j)\geq i\}-1.
$$
\vskip 3mm
{\it Exemple} 6. Soit $\sigma=5\ 3\ 1\ 8\ 7\ 2\ 6\ 4\ 11\ 10\ 9$,
$(\gamma,p)=\psi_{MV}(\sigma)$.\\
$\sigma$ est repr\'esent\'ee par le diagramme suivant:
\vskip 8mm
\hskip 2cm\begin{picture}(80,25)
\setlength{\unitlength}{8mm}
\thinlines
\multiput(-0.1,-0.2)(1,0){11}{$\bullet$}
\multiput(-0.1,0.95)(1,0){11}{$\bullet$}
\put(-0.18,-0.75){1} 
\put(0.82,-0.75){2} 
\put(1.82,-0.75){3} 
\put(2.82,-0.75){4} 
\put(3.82,-0.75){5} 
\put(4.82,-0.75){6} 
\put(5.82,-0.75){7} 
\put(6.82,-0.75){8} 
\put(7.82,-0.75){9} 
\put(8.8,-0.75){10} 
\put(9.8,-0.75){11} 
\put(-0.18,1.25){1} 
\put(0.82,1.25){2} 
\put(1.82,1.25){3} 
\put(2.82,1.25){4} 
\put(3.82,1.25){5} 
\put(4.82,1.25){6} 
\put(5.82,1.25){7} 
\put(6.82,1.25){8} 
\put(7.82,1.25){9} 
\put(8.8,1.25){10} 
\put(9.8,1.25){11} 
\put(0,1){\vector(4,-1){4}} 
\put(1,1){\vector(1,-1){1}} 
\put(2,1){\vector(-2,-1){2}} 
\put(3,1){\vector(4,-1){4}} 
\put(4,1){\vector(2,-1){2}} 
\put(5,1){\vector(-4,-1){4}} 
\put(6,1){\vector(-1,-1){1}} 
\put(7,1){\vector(-4,-1){4}} 
\put(8,1){\vector(2,-1){2}} 
\put(9,1){\vector(0,-1){1}} 
\put(10,1){\vector(-2,-1){2}} 
\end{picture}
\vskip 10mm
Alors $\gamma$ est repr\'esent\'e par la 
figure 4 suivante et\\
 $p=0\ 0\ 0\ 0\ 1\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 1\ 1\ 0\ 0\ 0\ 0\ 0
\ 1\ 0\ 0$.
\vskip 16mm
\hskip 2cm\begin{picture}(80,40)
\setlength{\unitlength}{5mm}
\thinlines
\put(0,0){\vector(1,0){24}}
\put(0,0){\vector(0,1){6}}
\multiput(1,0)(1,0){23}{\line(0,1){0.2}}
\multiput(0,1)(0,1){5}{\line(1,0){0.2}}

\put(-0.5,0.8){1} 
\put(-0.5,1.8){2} 
\put(-0.5,2.8){3} 
\put(-0.5,3.8){4} 
\put(-0.5,4.8){5} 

\put(-0.18,-0.75){0} 
\put(0.82,-0.75){1} 
\put(1.82,-0.75){2} 
\put(2.82,-0.75){3} 
\put(3.82,-0.75){4} 
\put(4.82,-0.75){5} 
\put(5.82,-0.76){6} 
\put(6.82,-0.75){7} 
\put(7.82,-0.75){8} 
\put(8.8,-0.75){9} 
\put(9.6,-0.75){10} 
\put(10.6,-0.75){11} 
\put(11.6,-0.75){12} 
\put(12.6,-0.75){13} 
\put(13.6,-0.75){14} 
\put(14.6,-0.75){15} 
\put(15.6,-0.75){16} 
\put(16.6,-0.75){17} 
\put(17.6,-0.75){18} 
\put(18.6,-0.75){19} 
\put(19.6,-0.75){20} 
\put(20.6,-0.75){21} 
\put(21.6,-0.75){22} 

\put(0,0){\line(1,1){4}} 
\put(4,4){\line(1,-1){2}} 
\put(6,2){\line(1,1){2}} 
\put(8,4){\line(1,-1){1}}
\put(9,3){\line(1,1){2}} 
\put(11,5){\line(1,-1){5}} 
\put(16,0){\line(1,1){3}} 
\put(19,3){\line(1,-1){3}} 
\multiput(0.82,0.82)(1,1){4}{${\bullet}$} 
\put(4.82,2.82){${\bullet}$} 
\put(5.82,1.82){${\bullet}$} 
\put(6.82,2.82){${\bullet}$} 
\put(7.82,3.82){${\bullet}$} 
\put(8.82,2.82){${\bullet}$} 
\put(9.82,3.82){${\bullet}$} 
\multiput(10.82,4.82)(1,-1){5}{${\bullet}$} 
\multiput(16.82,0.82)(1,1){3}{${\bullet}$} 
\multiput(19.82,1.82)(1,-1){2}{${\bullet}$} 
\end{picture}
\vskip 7mm
\centerline{fig. 4}
\vskip 3mm
{\bf Th\'eor\`eme 8}. -- Il existe une bijection $\varphi$ de $CB(n)$
sur $HLS(2n)$ telle que $\Psi_{MV}=\varphi\circ\Psi_B.$
\vskip 2mm
{\it D\'emonstration.} Soient $\sigma\in S_n$, $(c,\xi)=\Psi_B(\sigma)$
et $(\gamma,p)=\Psi_{MV}(\sigma)$. Les relations (6) et (10)(i)
montrent que $\gamma$ est le d\'econtract\'e de $c$, c'est-\`a-dire 
$\gamma$ et $c$ v\'erifient la relation suivante:
$$
\left\{\begin{array}{lrl}
\gamma_{2i-1}=\mt,\ \gamma_{2i}=\mt&\Longleftrightarrow&c_i=\mt\\
\gamma_{2i-1}=\ds,\ \gamma_{2i}=\ds
&\Longleftrightarrow&c_i=\ds\\
\gamma_{2i-1}=\mt,\ \gamma_{2i}=\ds&\Longleftrightarrow&c_i=\hc\\
\gamma_{2i-1}=\ds,\ \gamma_{2i}=\mt&\Longleftrightarrow&c_i=\hd\\
\end{array}\right. \eqno (11)
$$
Les relations (7) et (10)(ii) impliquent, d'autre part, que 
$p=p_1p_2\cdots p_{2n}$ et $\xi=\xi_1\xi_2\cdots \xi_n$ sont li\'es
par la relation:
$$
 \hbox{Pour tout}\ i\in [n], p_{2i-1}=\xi_i^- \hbox{et}\ 
p_{2i}=\xi_i^+.\eqno (12)
$$
Consid\'erons alors l'application 
$\varphi: (c,\xi)\mapsto (\gamma,p)$, o\`u $(c,\xi)\in CB_n$ et 
$(\gamma,p)$ le chemin marqu\'e
d\'efini par les relations (11) et (12).

On a:
$$h_{2j}(\gamma)=h_{2j-2}(\gamma)+2\chi(c_j=\mt)-2\chi(c_j=\ds)\
\hbox{pour tout}\ j\in [n].$$
 Ce qui entra\^\i ne que 
$$
h_{2i}(\gamma)=2h_i(c)\ \hbox{pour tout}\ i\in [n].
$$
Soit donc $k\in [2n]$.

a) {\it $k$ impair} :\ $k=2i-1$\\
-- si $\gamma_k=\mt$, $c_i=\mt$ ou $\hc$ et par suite $\xi_i^-=0$. 
Donc $p_k=0$.\\
-- si $\gamma_k=\ds$, $c_i=\ds$ ou $\hd$ 
et par suite $0\leq \xi_i^-\leq h_{i-1}(c)-1$. 
Donc $0\leq p_k\leq \displaystyle{h_{k-1}\over 2}(\gamma)-1$.\\

b) {\it $k$ pair} :\ $k=2i$\\
-- si $\gamma_k=\mt$, $c_i=\mt$ ou $\hd$ et par suite $\xi_i^+=0$. 
Donc $p_k=0$.\\
-- si $\gamma_k=\ds$, $c_i=\ds$ ou $\hc$ :\\
 Si $c_i=\ds$, $\gamma_{2i-1}=\ds$, et 
$0\leq \xi_i^+\leq h_{i-1}(c)-1
=\displaystyle{h_{2i-2}(\gamma)\over 2}-1
=\displaystyle{h_{2i-1}(\gamma)+1\over 2}-1$.\\ Par suite, 
$0\leq p_k\leq \displaystyle{h_{k-1}(\gamma)+1\over 2}-1$.

 Si $c_i=\hc$, $\gamma_{2i-1}=\mt$, 
et $0\leq \xi_i^+\leq h_{i-1}(c)=\displaystyle{h_{2i-2}(\gamma)\over 2}
=\displaystyle{h_{2i-1}(\gamma)-1\over 2}$.\\ Par suite, 
$0\leq p_k\leq \displaystyle{h_{k-1}(\gamma)-1\over 2}=
\displaystyle{h_{k-1}(\gamma)+1\over 2}-1$.

On en d\'eduit que $\varphi$ est bien une application de $CB_n$ vers
$HLS(2n)$. \\
D'autre part, d'apr\`es ce qui pr\'ec\`ede, on a les \'equivalences:\\
$$
\begin{array}{lcl}
0\leq p_{2i-1}\leq \displaystyle{h_{2i-2}\over 2}-1&
\Longleftrightarrow& 0\leq \xi_i^-\leq h_{i-1}-1;\\
0\leq p_{2i}\leq \displaystyle{h_{2i-1}+1\over 2}-1&
\Longleftrightarrow&\left\{ 
\begin{array}{l}
0\leq \xi_i^+\leq h_{i-1}-1\ \hbox{et}\ c_i=\ds;\\
\hfill\hbox{ou}\hfill\\
0\leq \xi_i^+\leq h_{i-1}\ \hbox{et}\ c_i=\hc.\\
\end{array}\right.\\
\end{array}$$
Ce qui montre que $\varphi$ est bijective et 
$\Psi_{MV}=\varphi\circ\Psi_B.$
\vskip 3mm
{\it Exemple} 7. Soit $\sigma=5\ 3\ 1\ 8\ 7\ 2\ 6\ 4\ 11\ 10\ 9$.
Le chemin de Motzkin bivalu\'e $(c,\xi)$ associ\'e par $\psi_B$ est
d\'efini dans l'exemple 5. Soit $(\gamma,p)=\varphi(c,\xi)$. Alors
$\gamma$ est repr\'esent\'e par la figure 4 et
$p=0\ 0\ 0\ 0\ 1\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 1\ 1\ 0\ 0\ 0\ 0\ 0
\ 1\ 0\ 0$.\\
Les exemples 5 et 6 montrent que 
$\Psi_{MV}(\sigma)=\varphi\circ\Psi_B(\sigma).$   
\eject

\vglue 1cm
%\sme
\centerline {BIBLIOGRAPHIE}
\vskip 5mm 
\def\pk#1#2|{{\smt#1}{\sme#2}}
\def\item#1{\par\noindent\hskip -0.45em\llap{#1\enspace}
\ignorespaces}
\def\oldstyle{}
{\parindent 1cm
\item{[1]}  \pk BIANE| (P.). --- {\it Permutations suivant le type d'exc\'edance et le nombre
d'inversions, et interpr\'etation combinatoire d'une fraction continue de
Heine}, Europ. J. Combinatorics, {\bf 14} ({\oldstyle 1993}), $277-284$.

\item{[2]}  \pk CLARKE| (R.J.), \pk STEINGR\'IMSSON| (E.) et \pk ZENG| (J.). 
--- {\it New Euler-Mahonian statistics on permutations}, Preprint 1996.

\item{[3]} \pk FLAJOLET| (P.). --- 
{\it Combinatorial aspects of continued fractions},
Disc. Math., {\bf 32} ({\oldstyle 1980}), $125-161$.
 
\item{[4]} \pk FOATA| (D.) et \pk ZEILBERGER| (D.). --- 
{\it Denert's Permutation Statistic is indeed Euler-Mahonian},
Studies in Appl. Math., {\bf 83} ({\oldstyle 1990}), $31-59$.
 
\item{[5]} \pk FRAN\c CON| (J.) et \pk VIENNOT| (X.G.). --- {\it 
Permutations selon les pics, creux, doubles mont\'ees, doubles descentes, 
nombres d'Euler, nombres de genocchi}, Disc. Math., {\bf 28} 
({\oldstyle 1979}), $21-35$.

\item{[6]} de \pk M\'EDICIS| (A.) et \pk VIENNOT| (X.G.). --- {\it Moments des $q-$polyn\^omes de
Laguerre et la bijection de Foata-Zeilberger}, Adv. Applied Math., {\bf 15} 
({\oldstyle 1994}), $262-304$.
\par}


\end{document}