%%% A TeX plain file for the paper by
%%% Dominique Foata and Arthur Randrianarivony
%%% Two Oiseau Decompositions of Permutations
%%% and their Application to Eulerian Calculus
%%% An output of 25 pages

\magnification=1200
\hsize=11.25cm
\voffset=.5cm

\frenchspacing
\def\P{{\cal P}}
\def\Tilde{\char126\relax}
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
 0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
 height0.15cm width 0.01cm}}
\def\tir{\raise 2pt\hbox{{\thinspace\vrule height.5pt 
depth0pt width 3pt\thinspace}}}

\def\tot{\mathop{\rm tot}}
\def\des{\mathop{\rm des}}
\def\rise{\mathop{\rm rise}}
\def\maj{\mathop{\rm maj}}
\def\mak{\mathop{\rm mak}}
\def\stat{\mathop{\rm stat}}
\def\dbv{\mathop{\rm Dbv}}
\def\Last{\mathop{\raise .2pt\hbox{\rm L}}}
\def\First{\mathop{\raise .2pt\hbox{\rm F}}}
\def\inv{\mathop{\rm inv}}
\def\card{\mathop{\rm card}}
\def\bfr{{\bf r}}
\def\bfd{{\bf d}}
\def\bfD{{\bf D}}
\def\bfc{{\bf c}}
\def\bfs{{\bf s}}


\def\val{\mathop{\rm val}}
\font\eightrm=cmr8 \font\sixrm=cmr6 
\font\eighttt=cmtt8
\font\bigbf=cmbx10 at 11pt

\def\pic#1{#1\hskip-8pt\raise 10pt\hbox{$\wedge$}\thinspace}
\def\petitpic#1{#1\hskip-5pt\raise
10pt\hbox{$\wedge$}\kern-2pt}
\def\petittrou#1{#1\hskip-6pt\lower
8pt\hbox{$\vee$}\kern-1pt}

%%%%%% 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

\newif\ifpagetitre
\newtoks\auteurcourant \auteurcourant={DOMINIQUE FOATA AND
ARTHUR RANDRIANARIVONY}
\newtoks\titrecourant \titrecourant={OISEAU DECOMPOSITIONS OF
PERMUTATIONS}

\pretolerance=500 \tolerance=1000 \brokenpenalty=5000
\newdimen\hmargehaute \hmargehaute=0cm
\newdimen\lpage \lpage=13.3cm
\newdimen\hpage \hpage=20cm
\newdimen\lmargeext \lmargeext=1cm
\def\margehaute{\vbox to \hmargehaute{\vss}}%
\def\margebasse{\vss}

\output{\shipout\vbox to \hpage{\margehaute\nointerlineskip
  \corpsdepage\margebasse}
  \advancepageno \global\pagetitrefalse
  \ifnum\outputpenalty>-20000 \else\dosupereject\fi}

\def\corpsdepage{\hbox to \lpage{\hss\pagetexte\hskip\lmargeext}}
\def\pagetexte{\vbox{\makeheadline\pagebody\makefootline}}
\headline={\ifpagetitre\titleheadline \else
  \ifodd\pageno\rightheadline \else\leftheadline\fi\fi}
\def\leftheadline{\eightrm\hfil\the\auteurcourant\hfil}
\def\rightheadline{\eightrm\hfil\the\titrecourant\hfil}
\def\titleheadline{\hfill}
\pagetitretrue

\def\qed{\quad\raise -2pt\hbox{\vrule\vbox to 10pt{\hrule width 4pt
\vfill\hrule}\vrule}}

\def\smashtop#1{\setbox0=\hbox{#1}\ht0=0pt\box0}
\def\smashbot#1{\setbox0=\hbox{#1}\dp0=0pt\box0}

%
%end macros
 
\vglue2cm

\centerline{\bigbf Two Oiseau Decompositions of Permutations}
\smallskip
\centerline{\bigbf and their Application to Eulerian Calculus}

\bigskip
\centerline{\sl Dominique Foata and Arthur Randrianarivony}
\bigskip\bigskip
{\narrower
\noindent
{\bf Abstract:} Two transformations are constructed that map the
permutation group onto a well-defined subset of a
partially commutative monoid generated by the so-called
oiseaux. Those trans\-formations are then used to show
that some bivariable statistics introduced by Babson and
Steingr\'\i msson are Euler-Mahonian.

}

\bigskip\bigskip 
\centerline{\bf 1. Introduction}
 
\bigskip
Everybody knows that each permutation of a finite set can be
uniquely expressed as a product of disjoint cycles, except for changes in
the order of the factors, so that the rule of commutation is the
property of being disjoint. In what follows the cycles will be
replaced by the so-called {\it oiseaux}, and those oiseaux,
although they may also be regarded as disjoint, are restricted to
commute according to another rule.

By {\it oiseau} it is meant a word, whose letters are {\it
distinct nonnegative} integers, of the form $pdth$, where~$p$ and~$t$
are single letters, $d$ is a (strictly) decreasing (possibly empty) word and
$h$ a (strictly) increasing (possibly empty) word; it is further assumed
that~$p$ (resp.~$t$) is the greatest (resp. the smallest) letter in~$pdth$.
By convention, the letter~$p$ could also be equal to~$\infty$.
The letter~``$p$" stands for {\it peak}, the letter~``$d$" for {\it
double-descent}, the letter~``$t$" for {\it trough} and~``$h$" for
{\it double-rise}, or {\it hill}.

\midinsert

\newbox\boxredblue

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

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


\setbox\boxredblue=\vbox{
\offinterlineskip 
\segment(0,0)\dir(1,-5)\long{7}
\centerput(3,0){\sevenrm 16}
\centerput(0,-1){$\bullet$}
\centerput(7.5,-29){\sevenrm 4}
\centerput(5.5,-29){$\bullet$}
\centerput(7,-39){\sevenrm 2}
\centerput(7,-36){$\bullet$}
\segment(7,-35)\dir(1,1)\long{25}
\centerput(16,-24){\sevenrm 6}
\centerput(17,-26){$\bullet$}
\centerput(23.5,-16){\sevenrm 10}
\centerput(24,-19){$\bullet$}
\centerput(31,-8.5){\sevenrm 14}
\centerput(32,-11){$\bullet$}
}

\vglue1cm
\centerline{\box\boxredblue\hskip 3cm}
\vglue4.2cm
\centerline{Fig. 1}
\endinsert

\medskip
\noindent
{\it Remark}.\quad
As shown in Fig.~1 an {\it oiseau} looks like a bird seen from
some distance, whose left wing is higher than the right
one. The terminology was suggested by G\'erard Duchamp [Du04],
who has used those oiseaux as particular classes of descents
occurring in the Dynkin Lie projector. In this example $p=16$ is
the peak of the oiseau, $d=4$ is the double-descent factor,
$t=2$ is the trough, $h=6,10,14$ is the double-rise factor. 

\medskip
Take the set of all the {\it oiseaux} as an alphabet~$A$,
supposed to be totally ordered by the lexicographic order, denoted by
``$\le$," induced by the usual order on the integers. As an element
of alphabet~$A$, each oiseau will be written $(pdth)$ with
parentheses.  Let $(pdth)$, $(p'd't'h')$ be two {\it distinct}
oiseaux; we say that $(pdth)$ is {\it below} $(p'd't'h')$ and write
$(pdth)\ll (p'd't'h')$, if and only if every letter in the word
$pdth$ is less than every letter in $p'd't'h'$. We also say that
$(p'd't'h')$ is {\it above} $(pdth)$ and write $(p'd't'h')\gg (pdth)$.
Two oiseaux are said to {\it commute} if and only if one is below
the other. One of the goals of this paper is to show that each
permutation can be written as a juxtaposition product of oiseaux
submitted to the previous commutation rule. As a matter of fact,
two transformations $\bfd$ and~$\bfD$ will be given that map
permutations onto such juxtaposition products.

For instance, consider the
following permutation
$$
{\sigma}=\pic{18},{\it 3},
\petittrou 1, \pic {16}, 
{\it 4}, \petittrou 2, 
{\bf 6},
\petitpic{9}, 
\petittrou 5, {\bf 7, 10},
\pic{11},\petittrou 8,
\pic{13},\petittrou{12},{\bf 14},
\pic{17},\petittrou{15},{\bf 19},
$$
where the {\it peaks} (resp. the {\it troughs\/}) are materialized
by ``$\wedge$" (resp. ``$\vee$") and the {\it double-rises} (resp.
the {\it double-descents}) are written in boldface (resp. in italic).
Under the {\it first} transformation~$\bfd$ the  permutation is
mapped onto an {\it oiseau-word}~$v$, i.e., a word whose letters
are oiseaux of the form $(p_0d_0t_0h_0)\ldots(p_rd_rt_rh_r)$:
$$
v=(\infty,0,{\bf 19})(\pic{18},  {\it 3}, \petittrou 1)( \pic {16},
{\it 4}, \petittrou 2, {\bf 6, 10,14})(\petitpic{9},  \petittrou 5,
{\bf 7})( \pic{11},\petittrou 8) (\pic{13},\petittrou{12})
(\pic{17},\petittrou{15}).
$$
Using the commutation rule on oiseaux, this juxtaposition product
can be rewritten as
$$
v'=(\infty,0,{\bf 19})(\pic{18},  {\it 3}, \petittrou 1)( \pic {16},
{\it 4}, \petittrou 2, {\bf 6,
10,14})(\pic{17},\petittrou{15})(\pic{13},\petittrou{12})(\petitpic{9},  \petittrou 5,
{\bf 7})( \pic{11},\petittrou 8).
$$
Finally, the permutation~$\sigma'$ that is sent over~$v'$ under
the {\it second} transformation~$\bfD$ reads:
$$
\sigma'=\pic{19},\petittrou 1,\pic{18},{\it 3},\petittrou2,{\bf
6,10,14},\pic{16},\petittrou{15},\pic{17},\petittrou{12},
\pic{13},\petittrou5,{\bf7},\pic9,\petittrou8,\pic{11},{\it 4}.
$$
Notice that the {\it nonzero troughs} in the
permutations~$\sigma$, $\sigma'$ and the words $v$, $v'$ are
the same: 1, 2, 5, 8, 12, 15; as well as the {\it double-descents}
(written in italic): {\it 3, 4}. As seen in the following theorem, the
transformations~$\bfd$, $\bfD$ and also the commutation rule on
oiseaux {\it preserve} the {\it set} of all the nonzero troughs and
double-descents.

Let $\sigma=x_1x_2\ldots x_n$ be a permutation of
$1,2,\ldots,n$. Following Babson-Steingr\'\i msson [BaSt01], 
$(b\tir ca)\sigma$ designates the number of
triples $(i,j,k)$ such that $1\le i<j<k=j+1\le n$ and
$x_j>x_i>x_k$. When the parentheses are
removed from an oiseau-word, we get another
word, say~$\overline v$, whose letters are nonnegative integers.
It then makes sense to define
$(b\tir ca)v:=(b\tir ca)\overline v$.
The main result of the paper can be stated as follows.

\proclaim Theorem 1.1.
For each positive integer~$n$ there exist two sets
$B_n^{\min}$ and $B_n^{\max}$ of oiseau-words having the
following properties:\hfil\break
\hbox{\quad} {\rm (i)} the transformation~\bfd\ is a bijection of
the permutation group
${\cal S}_n$ onto $B_n^{\min}$ with the
property
$$
(b\tir ca)\sigma=(b\tir ca)\bfd\,\sigma;
$$
\quad\ {\rm (ii)} there is a bijection $\theta$ of $B_n^{\min}$
onto
$B_n^{\max}$ such that
$$
(b\tir ca)v=(b\tir ca)\theta(v);
$$
\quad\ {\rm (iii)} the transformation \bfD\ is a bijection of
${\cal S}_n$ onto $B_n^{\max}$ with the property
$$
(b\tir ca)\sigma=(b\tir
ca)\bfD\,\sigma+n-\Last\sigma-\des\sigma,
$$
where $\Last\sigma$ is the rightmost letter of~$\sigma$ and
$\des\sigma$  the usual number of descents of the 
permutation;\hfil\break
\hbox{\quad} {\rm (iv)} the bijections $\bfd$, $\theta$, $\bfD$
preserve the set of the nonzero troughs and double-descents.

Going back to the previous numerical example we can verify that
in~$\sigma$\hfil\break
the letter 3 is to the left of $16,4,2$;\qquad 
6 is to the left of $9,5$;\hfil\break
the letters 9, 10 are on the left of $11,8$;\quad
16 is on the left of $17,15$;\hfil\break
so that 
$
(b\tir ca)\sigma=5$. Also $(b\tir ca)v=(b\tir ca)v'=5$. However
$(b\tir ca)\sigma'=12$, $\Last\sigma'=4$, $\des\sigma'=8$ and
$n=19$. As $v'=\bfD\,\sigma'$, we verify that
$$
12=(b\tir ca)\sigma'=
(b\tir ca)\bfD\,\sigma'+n-\Last\sigma'-\des\sigma'
=5+19-4-8,
$$
so that (iii) holds.

\medskip
The composition product $\Phi:={\bfD}^{-1}\theta\bfd$ is then a
bijection of ${\cal S}_n$ onto itself with the property
$$
(b\tir ca)\Phi(\sigma)
=(b\tir ca)\sigma+n-\Last\Phi(\sigma)-\des\Phi(\sigma)
\leqno(1.1)$$
and this latter result will be the basic ingredient for proving that
two bivariable statistics are Euler-Mahonian.

\goodbreak


$$
\vbox{\offinterlineskip
\halign{\strut\vrule\hfil$\,#\,$\hfil
&\vrule\hfil$\,#\,$\hfil
&\vrule\hfil$\,#\,$\hfil
&\vrule\hfil$\,#\,$\hfil
&\vrule\hfil$\,#\,$\hfil
&\vrule\hfil$\,#\,$\hfil
&\vrule\hfil$\,#\,$\hfil\vrule\cr
\noalign{\hrule}
(1)&(2)&(3)&(4)&(5)&(6)&(7)\cr
\noalign{\hrule}
\sigma&\bfd\,\sigma&\theta\bfd\,\sigma{=}\bfD\,\sigma'
&\bfD^{-1}\theta\bfd\,\sigma
&(b\tir ca)\sigma'&(b\tir ca)\sigma
&f(\sigma')\cr
{\cal
S}_4&B_4^{\min}&B_4^{\max}&{=}\Phi(\sigma){=:}\sigma'&&&\cr
\noalign{\hrule}
1234&(\infty01234)&{\rm id}&1234&0&0&0\cr
\noalign{\hrule}
124{\bf 3}&(\infty012)(4{\bf 3})&{\rm id}&124{\bf 3}&0&0&0\cr
\noalign{\hrule}
13{\bf 2}4&(\infty014)(3{\bf 2})&{\rm id}&14{\bf 2}3&0&0&0\cr
\noalign{\hrule}
134{\bf 2}&(\infty013)(4{\bf 2})&{\rm id}&13{\bf 2}4&0&1&-1\cr
\noalign{\hrule}
14{\bf 2}3&(\infty01)(4{\bf 2}3)&{\rm id}&134{\bf 2}&1&0&1\cr
\noalign{\hrule}
14{\bf 32}&(\infty01)(4{\bf 32})&{\rm id}&14{\bf 32}&0&0&0\cr
\noalign{\hrule}
2{\bf 1}34&(\infty034)(2{\bf 1})&{\rm id}&34{\bf 1}2&1&0&1\cr
\noalign{\hrule}
2{\bf 1}4{\bf 3}&(\infty0)(2{\bf 1})(4{\bf 3})&(\infty0)(4{\bf 3})(2{\bf 1})&4{\bf 3}{\bf 1}2&0&0&0\cr
\noalign{\hrule}
23{\bf 1}4&(\infty024)(3{\bf 1})&{\rm id}&24{\bf 1}3&1&1&0\cr
\noalign{\hrule}
234{\bf 1}&(\infty023)(4{\bf 1})&{\rm id}&23{\bf 1}4&1&2&-1\cr
\noalign{\hrule}
24{\bf 1}3&(\infty02)(4{\bf 1}3)&{\rm id}&2{\bf 1}34&0&1&-1\cr
\noalign{\hrule}
24{\bf 3}{\bf 1}&(\infty02)(4{\bf 3}{\bf 1})&{\rm id}&2{\bf 1}4{\bf 3}&0&1&-1\cr
\noalign{\hrule}
3{\bf 1}24&(\infty04)(3{\bf 1}2)&{\rm id}&4{\bf 1}23&0&0&0\cr
\noalign{\hrule}
3{\bf 1}4{\bf 2}&(\infty0)(3{\bf 1})(4{\bf 2})&{\rm id}&3{\bf 2}4{\bf 1}&2&1&1\cr
\noalign{\hrule}
3{\bf 2}{\bf 1}4&(\infty04)(3{\bf 2}{\bf 1})&{\rm id}&4{\bf 1}3{\bf 2}&0&0&0\cr
\noalign{\hrule}
3{\bf 2}4{\bf 1}&(\infty0)(3{\bf 2})(4{\bf 1})&{\rm id}&3{\bf 2}{\bf 1}4&0&2&-2\cr
\noalign{\hrule}
34{\bf 1}2&(\infty03)(4{\bf 1}2)&{\rm id}&3{\bf1}24&0&1&-1\cr
\noalign{\hrule}
34{\bf 2}{\bf 1}&(\infty03)(4{\bf 2}{\bf 1})&{\rm id}&3{\bf 1}4{\bf 2}&1&1&0\cr
\noalign{\hrule}
4{\bf 1}23&(\infty0)(4{\bf 1}23)&{\rm id}&234{\bf 1}&2&0&2\cr
\noalign{\hrule}
4{\bf 1}3{\bf 2}&(\infty0)(4{\bf 1})(3{\bf 2})&{\rm id}&4{\bf
2}3{\bf 1}&1&0&1\cr
\noalign{\hrule}
4{\bf 2}{\bf 1}3&(\infty0)(4{\bf 2}{\bf 1}3)&{\rm id}&34{\bf 2}{\bf 1}&1&0&1\cr
\noalign{\hrule}
4{\bf 2}3{\bf 1}&(\infty0)(4{\bf 2})(3{\bf 1})&{\rm id}&4{\bf 2}{\bf 1}3&0&1&-1\cr
\noalign{\hrule}
4{\bf 3}{\bf 1}2&(\infty0)(4{\bf 3}{\bf 1}2)&{\rm id}&24{\bf 3}{\bf 1}&1&0&1\cr
\noalign{\hrule}
4{\bf 3}{\bf 2}{\bf 1}&(\infty0)(4{\bf 3}{\bf 2}{\bf 1})&{\rm id}&4{\bf 3}{\bf 2}{\bf 1}&0&0&0\cr
\noalign{\hrule}
}
\medskip
\line{\hfil Fig. 2\hfil}}
$$

In Fig. 2 the permutations in ${\cal S}_4$ are listed in
column~(1). The second column contains the images of each
permutation~$\sigma$ under the bijection~$\bfd$. We can then
read all the oiseau-words belonging to~$B_4^{\min}$. In
column~(3) the elements $\theta\bfd\,\sigma$ that are listed are
the oiseau-words belonging to~$B_4^{\max}$. The entry ``id"
means that $\bfd\, \sigma=\theta\bfd\,\sigma$. This is the case
for all the oiseau-words, except for $\sigma=2{\bf1}4{\bf3}$.
Notice that the oiseaux $(2{\bf1})$ and $(4{\bf3})$ commute.
The images $\sigma':=\Phi(\sigma)$ are listed in column~(4). In
columns~(5) and~(6) the statistics
$(b\tir ca)$ are calculated for~$\sigma'$ and for~$\sigma$,
respectively. The function~$f$ in column~(7) is defined to be
$f(\sigma'):=n-\Last\sigma'-\des\sigma'$, so that (1.1) reads
$(b\tir ca)\sigma'=(b\tir ca)\sigma+f(\sigma')$. To verify that
(1.1) holds for~$n=4$ we just have to notice that
${\rm column}\;(5)={\rm column}\;(6)+{\rm column}\;(7)$. The
nonzero troughs and the double-descents are reproduced in
boldface, so that statement~(iv) of Theorem~1.1 is illustrated by
the fact that in each row the {\it set} of letters in boldface is the
same in columns (1), (2), (3) and~(4). For instance, {\bf 2} is a
{\it trough}  in $\sigma=3{\bf 2}4{\bf 1}$ and
$\bfd\,\sigma=(\infty0)(3{\bf 2})(4{\bf 1})$, but a {\it
double-descent} in $\Phi(\sigma)=3{\bf 2}{\bf 1}4$.

\medskip
For constructing the transformations \bfd, \bfD\ and $\theta$,
and accordingly defining the two sets 
$B_n^{\min}$ and $B_n^{\max}$, we have recourse to the theory
of {\it partially commutative monoids}, as was developed by
Cartier and Foata [CaFo69]. The salient features are recalled in
Section~2. The partially commutative monoid generated by the set
of the {\it oiseaux} is then described in Section~3. The next two
sections are devoted to the constructions of the
transformations~$\bfd$ and~$\bfD$. Surprisingly, part~(iii) of
Theorem~1.1 requires a delicate analysis that is made in
Section~6. The final sections deal with Eulerian Calculus. In
particular, we prove that four conjectures made by Babson and
Steingr\'\i msson [BaSt01] are correct.

The following notations will be used throughout. Let $A$ be a 
non-empty set; we let $A^*$ denote the free monoid generated
by~$A$, that is, the set of all the finite words $w=a_1a_2\ldots
a_m$, whose letters~$a_i$ belong to~$A$. The number~$m$ of
the letters in the word~$w$ is the {\it length} of~$w$, denoted
by~$|w|$. If~$E$ is a subset of~$A$, then $|w|_{ E}$ is
the number of letters of~$w$ that belong to~$E$. When the
underlying alphabet~$A$ is the set of the integers, then
$\tot w$ designates the {\it sum} of its letters: $\tot
w=a_1+a_2+\cdots +a_m$ (``tot" stands for ``total").
As noted before, $\Last w$ designates the rightmost letter~$a_m$
of~$w$. Furthermore, $\First w$ refers to its leftmost
letter~$a_1$ (the first~one).

When the alphabet~$A$ is totally ordered, the number of
{\it descents} of~$w$ is defined to be the
number of integers~$j$ such that $1\le j\le m-1$ and
$a_j>a_{j+1}$. It is expressed as $(ba)w$ or $\des w$. 
Further statistics, that are introduced in the final sections, refer
to Eulerian Calculus proper.

\bigskip
\centerline{\bf 2. Partially commutative monoids}

\medskip
Let $A^*$ be the free monoid generated by a nonempty set~$A$
and let~$C$ be a subset of $A\times A$ containing no element of
the form~$(a,a)$ and such that $(a',a)$ belongs to~$C$ if $(a,a')$
does. Two words~$w$ and~$w'$ are said to be $C$-{\it
adjacent}, if there exist two words~$u$ and~$v$ and an ordered
pair $(a,a')$ in~$C$ such that $w=uaa'v$ and $w'=ua'av$. Two
words~$w$ and~$w'$ are said to be~$C$-{\it equivalent}, if
they are equal, or if there exists a sequence of words $w_0$,
$w_1$, \dots~, $w_p$, such that
$w_0=w$, $w_p=w'$ and $w_{i-1}$ and~$w_i$ are $C$-adjacent
for $1\le i\le p$. This defines an equivalence relation~$R_C$
on~$A^*$, compatible with the multiplication in~$A^*$. The
quotient monoid $A^*/R_C$ is denoted by $L(A;C)$ and is called
the $C$-{\it partially commutative monoid generated by}~$A$.
The $C$-equivalence class of a letter~$a\in A$ is denoted by
$[a]$. Two letters $a$, $a'$ are said to {\it commute}, if
$[a][a']=[a'][a]$ in $L(A;C)$.

A subset~$F$ of~$A$ is said to be {\it commutative}, if it is finite,
non-empty and if any two of its elements commute. For such a subset
let $[F]:=\prod_{a\in A} [a]$. A letter~$a$ is said to be {\it
linked to} a subset~$F$ of~$A$, if $a\in F$ or if there exists a letter
in~$F$ that does not commute with~$a$. Let $F$, $F'$ be two subsets
of~$A$; then, $F$ is said to be {\it contiguous} to~$F'$ if every letter
of~$F'$ is linked to~$F$. Each sequence $(F_1,\ldots, F_r)$ of
commutative subsets of~$A$ is called a $V$-{\it sequence}, if for each
$i=1,\ldots, r-1$ the subset~$F_i$ is contiguous to~$F_{i+1}$.

\proclaim Theorem 2.1. For every element~$u$ in $L(A;C)$ there is a
unique $V$-sequence $(F_1,\ldots,F_r)$ such that 
$u=[F_1]\cdots [F_r]$.

[See [CaFo69, p.~11] for a proof.]

\goodbreak
\medskip
We mention a further property that is needed in the present context.
Suppose that the alphabet~$A$ is totally ordered and let ``$\le$" denote
the total ordering. A word $w=a_1a_2\ldots a_m$ is said to be $C$-{\it
minimal} (resp. $C$-{\it maximal\/}), if for each $i=1,2,\ldots, m-1$ the
following property holds

\medskip\noindent
(2.1) if $a_i$ and $a_{i+1}$ commute, then $a_i<a_{i+1}$
(resp. $a_i>a_{i+1}$).

\smallskip
\proclaim Proposition 2.2. Each $C$-equivalence class in $L(A;C)$
contains one and only one $C$-minimal (resp. $C$-maximal) word.

{\it Proof.}\quad
Let $u=[b_1][b_2]\ldots [b_m]$ be a $C$-equivalence class and let
$(F_1,F_2,\ldots,F_r)$ be its $V$-sequence. Denote the minimum
of~$F_1$ (with respect to the total ordering on~$A$) by~$a_1$.
The product $[F_1\setminus\{a_1\}][F_2]\cdots [F_r]$ in $L(A;C)$
admits a $V$-sequence $(G_1,G_2,\ldots, G_s)$. More essentially, the
inclusion $F_1\setminus\{a_1\}\subset G_1$ holds, as can be verified
directly, or by using Corollary~1.4 on page~15 in [CaFo69]. Extract
$a_2:=\min G_1$ from~$B_1$. If~$a_2$
belongs to~$F_1$, both $a_1$ and $a_2$ commute and $a_1<a_2$; if
$a_2\not\in F_1$, then~$a_2$ necessarily belongs to~$F_2$ and commutes
with all the letters in $F_1\setminus\{a_1\}$. Consequently, $a_1$ and
$a_2$ do not commute. Again form the new class
$[G_1\setminus\{a_2\}][G_2]\cdots [G_s]$, and so on. At the end we get a
word $a_1a_2\ldots a_m$ such that either $a_i<a_{i+1}$, or $a_i$ and
$a_{i+1}$ do not commute. 

To prove the uniqueness take two
{\it distinct} $C$-minimal words $v$ and~$v'$ supposed to be
$C$-equivalent. There suffices to consider the case where
$v=a_1a_2\ldots a_m$,
$v'=a_{i_1}a_{i_2}\ldots a_{i_m}$ with
$a_1\not=a_{i_1}$. Those words may also be expressed as
$v\!=\!a_1a_2\ldots a_ja_{i_1}a_{j+2}\ldots a_m$ and
$v'\!=\!a_{i_1}a_{i_2}\!\ldots\! a_{i_k}a_1a_{i_{k+2}}\ldots
a_{i_m}$, with $a_{i_1}\not= a_1,a_2,\ldots ,a_j$ and
$a_1\not=a_{i_1},a_{i_2},\ldots,a_{i_k}$. As $v$ and~$v'$ are
supposed to be~$C$-equivalent, the letter~$a_{i_1}$
(resp.~~$a_1$) commutes with $a_1, a_1,\ldots,a_j$ (resp. with
$a_{i_1},a_{i_2},\ldots,a_{i_k})$. But as~$v$ and~$v'$ are both
$C$-minimal, the two relations $a_1<a_{i_1}$, $a_{i_1}<a_1$
hold, a contradiction. To prove the ``resp." part, simply replace
``min" vy ``max" and ``$<$" by ``$>$" in the above
derivation.\qed

\medskip
In the sequel the map that sends each $C$-minimal word in~$A^*$
onto the $C$-maximal word that belongs to the same $C$-equivalence
class will be denoted by~$\theta$. If $v=a_1a_2\ldots a_m$ is
$C$-minimal, we form the $C$-class $u=[a_1][a_2]\cdots [a_m]$, then
its $V$-sequence $(F_1,F_2,\ldots, F_r)$. Following the proof of the
previous proposition, define $b_1:=\max F_1$ and form the $V$-sequence
$(G_1,G_2,\ldots, F_s)$ of $[F_1\setminus\{b_1\}][F_2]\ldots
[F_r]$. Further, define $b_2:=\max G_1$, and so on. Finally,
$\theta(v)=b_1b_2\ldots b_m$.

\bigskip
\centerline{\bf 3. The oiseau partially commutative monoid}

\medskip
Now $A$ will designate the set of all the oiseaux $(pdth)$, as defined
in the introduction and~$C$ will be the set of all pairs
$\bigl((pdth),(p'd't'h')\bigr)$ of oiseaux such that either
$(pdth)\ll (p'd't'h')$, or $(pdth)\gg (p'd't'h')$. We form the
free monoid~$A^*$ generated by~$A$. Its elements are the
{\it oiseau-words} 
$v=(p_0d_0t_0h_0)(p_1d_1t_1h_1)\ldots (p_rd_rt_rh_r)$. We
also consider the $C$-partially commutative monoid
$L(A;C)$. The
$C$-equivalence class of each oiseau
$(pdth)$ will be denoted by $[pdth]$.

For each $n\ge 1$ the two classes of oiseau-words $B^{\min}_n$
and $B^{\max}_n$, mentioned in the statement of Theorem~1.1,
are defined as follows. An oiseau-word
$v=(p_0d_0t_0h_0)(p_1d_1t_1h_1)\ldots (p_rd_rt_rh_r)$
belongs to $B^{\min}_n$ (resp. to $B^{\max}_n$) if and only if
the following three conditions hold:

(i) the oiseau-word $v$ is $C$-minimal (resp. $C$-maximal);

(ii) $p_0=\infty$, $d_0=e$ (the empty word) and $t_0=0$;

(iii) the factor 
$h_0p_1d_1t_1h_1\ldots p_rd_rt_rh_r$
is a permutation of $1,2,\ldots n$.

\medskip
Let $[v]=[p_0d_0t_0h_0]\ldots [p_rd_rt_rh_r]$ be the
$C$-equivalence class of an
element $v=(p_0d_0t_0h_0)\ldots
(p_rd_rt_rh_r)$ of
$B^{\min}_n$ (resp. of $B^{\max}_n$). As $p_0d_0t_0=\infty0$, 
no oiseau $(p_id_it_ih_i)$ $(i=1,\ldots,r)$
can commute with $(p_0d_0t_0h_0)=(\infty 0h_0)$. Hence,
all the words in the
$C$-equivalence class~$[v]$ start with 
$(\infty 0h_0)$
and the first factor in the $V$-sequence of~$[v]$ is
reduced to the single term $[(\infty 0h_0)]$. 
The set of all the
$C$-equivalence classes that contain one element of
$B^{\min}_n$ (and only one by Proposition~2.2) will be
designated by~$B_n$. The three sets $B_n$,
$B^{\min}_n$, $B^{\max}_n$ can be put
into a one-to-one correspondence. In particular,
$B^{\max}_n=\theta(B^{\min}_n)$, where~$\theta$ is the
bijection introduced at the end of Section~2.


\medskip
{\it Example}.\quad 
The following word
$$
v=(\infty,0,19)(18,  3, 1)( {16}, 4, 2, {6, 10,14})({9},  5, { 7})(
{11},8) ({13},{12})( {17},{15})
$$
is an element of $B^{\min}_{19}$. To derive $\theta(v)$, calculate
the $V$-sequence of $[v]$ that reads $(F_1,F_2,F_3,F_4,F_5)$
with
$$\displaylines{
F_1=\{(\infty,0,19)\},\quad F_2=\{(18,  3, 1)\},\quad F_3=\{( {16}, 4,
2, 6, 10,14)\},\cr
F_4=\{({9},5, 7) ,   ( {13},{12}),( {17},{15})\},\quad
F_5=\{( {11}, 8)\}\bigr).\cr}
$$
Then $a_1=\max F_1=(\infty,0,19)$. The $V$-sequence of
$[F_2][F_3][F_4][F_5]$ is simply $(F_2,F_3,F_4,F_5)$, so that
$a_2=(18,3,1)$. The $V$-sequence of $[F_3][F_4][F_5]$
is $(F_3,F_4,F_5)$ and $a_3=( {16}, 4,2, 6, 10,14)$. The
$V$-sequence of $[F_4][F_5]$ is $(F_4,F_5)$ and
$a_4=\max F_4=(17,15)$. The $V$-sequence of
$[F_4\setminus \{a_4\}][F_5]$ is $(\{(9,5,7),(13,12)\},\{(11,8)\})$ and
$a_5=(13,12)$. Finally, $a_6=(9,5,7)$, $a_7=(11,8)$, so that
$$
\theta(v)=(\infty,0,19)(18,  3, 1)( {16}, 4, 2, { 6, 10,14})(
{17},{15})({13},{12})({9},  5, { 7})( {11},8) .
$$

The next two sections will be devoted to constructing two bijections
$\bfd$ and $\bfD$ of the permutation group ${\cal S}_n$ onto
$B^{\min}_n$ and $B^{\max}_n$, respectively.

\goodbreak
\bigskip
\centerline{\bf 4. The first transformation}

\medskip
To construct the first bijection~$\bfd$ of ${\cal S}_n$
onto~$B^{\min}_n$ we proceed as follows.
Let $\sigma=x_1x_2\cdots x_n$ be a permutation
of the word $12\ldots n$, written as a linear word. Let $x_0:=0$,
$x_{-1}=x_{n+1}:=+\infty$ and
consider the word $0\sigma=x_0x_1\ldots x_n$. 
By {\it peak} of 
$0\sigma$ it is meant a letter $x_j$ such that $1\le j\le n$ and
$x_{j-1}<x_j$, $x_j>x_{j+1}$.  By {\it trough} we mean a
letter
$x_j$ such that $0\le j\le n$ and
$x_{j-1}>x_j$, $x_j<x_{j+1}$. Accordingly, each permutation
$0\sigma$ has
$(r+1)$~troughs and $r$ peaks for some $r\ge 0$. By 
{\it double-descent} we mean a letter $x_j$ such that $1\le j\le
n-1$ and $x_{j-1}>x_j>x_{j+1}$. By {\it double-rise} we mean a
letter
$x_j$ such that $1\le j\le n$ and $x_{j-1}<x_j<x_{j+1}$.
As above, $p$ and $t$ will designate 
{\it letters} which are peaks and troughs, respectively, while $d$,
$h$, will designate {\it words} all letters of which are
double-descents, double-rises, respectively. There is a unique
factorization
$$t_0h_0\mid p_1d_1t_1h_1\mid p_2d_2t_2h_2\mid\;\ldots \;
\mid p_rd_rt_rh_r\leqno(4.1)$$ 
of $0\sigma$, called its 
{\it peak factorization}, having the following properties:

(1) $r\ge 0$; $t_0=0$;

(2) the $p_i$'s are the {\it peaks} and the $t_i$'s the {\it troughs} of the
permutation;

(3) for each $i$ the symbols $h_i$, $d_i$ are {\it words}, possibly
empty, all letters of which are {\it double-rises}, {\it double-descents},
respectively. It will be convenient to let $p_0=p_{r+1}:=+\infty$. 

\medskip
In each component $p_jd_jt_jh_j$ the peak~$p_j$ is not
necessarily the greatest letter of the factor, so that
$(p_jd_jt_jh_j)$ may not be an oiseau. The transformation~$\bfd$
will consist of moving {\it to the left} the different {\it double-rises} in such a way that the new factors, say,
$(p_jd_jt_jh'_j)$ will be oiseaux; in particular, $p_j\gg h'_j$.

\medskip
Let $y$ be a {\it double-rise} of~$0\sigma$, so that~$y$ is a letter of
the factor~$h_j$ for some~$j$ $(0\le j\le r)$. Define $\varphi(y)$
to be the {\it greatest integer}~$i$ such that $0\le i\le j$ and
$p_i>y>t_i$. Thus, the following inequalities hold:
$$
p_i>y>t_i,\ y>p_{i+1},\ \ldots\ ,\ 
y>p_j,\ t_j<y<p_{j+1}.\leqno(4.2)
$$

Next, define $h'_i$ to be the {\it increasing word} of all
double-rises~$y$ in~${\sigma}$ such that $\varphi(y)=i$. If
$\varphi(y)\not=i$ for every double-descent~$y$ of~${0\sigma}$, let
$h'_i$ be the empty word. Clearly, $(\infty 0h'_0)$ is an oiseau, as well as
each letter $(p_id_it_ih'_i)$ for $i=1,2,\ldots, r$.
Define ${\bf d}\,{\sigma}$ to be the following
element in $A^*$ [remember that $t_0=0$]
$$
{\bf d}\,{\sigma}:=(\infty t_0h'_0)(p_1d_1t_1h'_1)(p_2d_2t_2h'_2)\ldots 
(p_rd_rt_rh'_r)\leqno(4.3)
$$

For example, start with the peak-factorized permutation
$$
{0\sigma}=\vtop{\hbox{0}\smallskip\hbox{0}}\mid \pic{18}, 
\vtop{\hbox{3}\smallskip\hbox{1}},
\petittrou 1\mid
\pic {16}, 4\vtop{\hbox{,}\smallskip\hbox{2}} \petittrou 2, 
{\bf 6}\mid
\petitpic{9}, 
\petittrou 5\vtop{\hbox{,}\smallskip\hbox{3}} {\bf 7, 10}\mid
\pic{11}\vtop{\hbox{,}\smallskip\hbox{4}}\petittrou 8\mid
\pic{13},\vtop{\hbox{\petittrou{12}}\hbox{5}},{\bf 14}\mid
\pic{17},\vtop{\hbox{\petittrou{15}}\hbox{6}},{\bf 19},
$$
that has seven factors, numbered from~0 to~6. The
peaks (resp. the troughs) are materialized by
``$\wedge$" (resp. ``$\vee$") and the double-rises are written in
boldface. We have $p_0=\infty$, $p_1=18$, $p_2=16$, $p_3=9$,
$p_4=11$, $p_5=13$, $p_6=17$. Also, $t_0=0$, $t_1=1$,
$t_2=2$, $t_3=5$,
$t_4=8$, $t_5=12$, $t_6=15$. Next, the double-descent factors read
$d_1=3$;
$d_2=4$, $d_3=d_4=d_5=d_6=e$ (the empty word)
and the double-rise factors
$h_0=h_1=e$;
$h_2={\bf 6}$; $h_3={\bf 7, 10}$; $h_4=e$;
$h_5={\bf 14}$; $h_6={\bf 19}$. 

Thus
$\varphi({\bf 6})=2$,
$\varphi({\bf 7})=3$,
$\varphi({\bf 10})=2$,
$\varphi({\bf 14})=2$,
$\varphi({\bf 19})=0$ (remember that $p_0=\infty$)
and $h'_0={\bf 19}$; $h'_2={\bf 6,10,14}$; $h'_3={\bf 7}$;
$h'_4=h'_5=h'_6=e$. Hence
$$
{\bf d}\,{\sigma}\!=\!(\infty,0,{\bf19})(18,  3, 1)( {16}, 4, 2, {\bf 6,
10,14})( {9}, 
 5, {\bf 7})( {11}, 8)( {13},{12})( {17},{15}).
$$

Go back to the general case. For each
$i=0,1,\ldots, r-1$ the trough
$t_i$ is less than both $p_i$ and $p_{i+1}$. Hence, if $p_i>p_{i+1}$,
the two oiseaux $(p_id_it_ih'_i)$ and
$(p_{i+1}d_{i+1}t_{i+1}h'_{i+1})$ cannot commute. In an equivalent
manner, if $(p_id_it_ih'_i)$ and
$(p_{i+1}d_{i+1}t_{i+1}h'_{i+1})$ commute, then $p_i<p_{i+1}$ and
also
$(p_id_it_ih'_i)<(p_{i+1}d_{i+1}t_{i+1}h'_{i+1})$ (for the lexicographic
order). But as the oiseaux commute, the $<$-sign can be replaced by the
$\ll $-sign, so that $\bfd\,\sigma$ is {\it minimal}.


\medskip
{\it The map {\bf d} is bijective}.\quad
The construction of~{\bf d} given above is perfectly reversible. 
Let
$v=(\infty t_0h'_0)(p_1d_1t_1h'_1)(p_2d_2t_2h'_2)\ldots 
(p_rd_rt_rh'_r)$ be an element of $B_n^{\min}$ and let~$y$ be a {\it
double-rise} in the word $p_id_it_ih'_i$ $(0\le i\le r)$ (with
$p_0=\infty$, $d_0=e$ and $t_0=0$).

If $p_i<p_{i+1}$ (remember that $p_{r+1}=\infty$ by convention), let
$\varphi^-(y):=i$. If $p_i>p_{i+1}$, define $\varphi^-(y)$ to be the
smallest integer~$j$ such that $i+1\le j\le r$ and $y<p_{j+1}$. 
Then, define~$h_j$ to be the {\it increasing word} of all double-rises~$y$
from each of the words $p_0d_0t_0h'_0$, \dots~, $p_rd_rt_rh'_r$ such
that $\varphi^-(y)=j$ and form the permutation
$\sigma^-:=t_0h_0 p_1d_1t_1h_1p_rd_rt_rh_r$.

As the inequalities in (4.2) hold, we have the equivalence
$$
[y\hbox{ is a letter of }h_j\hbox{ and } \varphi(y)=i]
\Leftrightarrow
[y\hbox{ is a letter of }h'_i\hbox{ and } \varphi^-(y)=j].
$$
To show that {\bf d} is reversible we only have to verify that the
factorization
$$
t_0h_0\mid p_1d_1t_1h_1\mid\;\ldots \;\mid p_rd_rt_rh_r,
$$
is the peak factorization of~$\sigma^-$, essentially verify that
the~$p_j$'s are the peaks of~$\sigma^-$. When $p_j>p_{j+1}$, we don't
have $p_jd_jt_jh'_j\gg  p_{j+1}d_{j+1}t_{j+1}h'_{j+1}$, because~$v$ is
supposed to be minimal; hence $t_j<p_{j+1}$. The double-rises in~$h'_j$
less than $p_{j+1}$ occur in~$h_j$, while the double-rises greater
than~$p_{j+1}$ occur in a factor $h_i$ with
$i\ge j+1$. It follows that $p_{j+1}$ is greater than all the letters
of~$h_j$. It is then is a peak of~$\sigma^-$, so that
$\sigma^-=\sigma$. Thus {\bf d} is a bijection.

\medskip
{\it Example.}\quad Start with the $C$-minimal word
$$
v=(\infty,\vtop{\hbox{0}\hbox{0}},{\bf19})
(18, \vtop{\hbox{3}\hbox{1}}, 1)( {16}, 4, 2, 
\vtop{\hbox{\bf 6}\hbox{2}},
{\bf 10,14})( {9}, \vtop{\hbox{5}\hbox{3}}, {\bf 7})(
{11}\vtop{\hbox{,}\hbox{4}} 8)( {13}\vtop{\hbox{,}\hbox{5}}{12})(
{17}\vtop{\hbox{,}\hbox{6}}{15})
$$
We have $\varphi^-({\bf 19})=6$; 
$\varphi^-({\bf 6})=2$;
$\varphi^-({\bf 10})=3$;
$\varphi^-({\bf 14})=5$;
$\varphi^-({\bf 7})=3$; so that
$h_0=h_1=e$; $h_2={\bf 6}$; $h_3={\bf 7,10}$; $h_4=e$; 
$h_5={\bf 14}$;
$h_6={\bf 19}$ and
$$\bfd^{-1}v\!=\!
{\sigma}\!=\mid {18},  3,  1\mid
 {16}, 4,  2, {\bf 6}\mid {9}, 
 5, {\bf 7, 10}\mid
{11}, 8\mid {13},{12},{\bf 14}\mid
{17},{15},{\bf 19}.
$$

\bigskip
\centerline{\bf 5. The second transformation}

\medskip
In the second transformation the key role will be played by the
double-descents instead of the double-rises.  The peak
factorization is replaced by the {\it trough factorization} that
consists of cutting the permutation just before each trough. More
formally, each permutation $\sigma=x_1x_2\ldots x_n$ has a
unique factorization
$$
h_0p_0d_0\mid t_1h_1p_1d_1\mid t_2h_2p_2d_2\mid\;\ldots \;
\mid t_rh_rp_rd_r,
$$ 
where all the previous notations about the
letters~$h$, $p$, $d$, $t$ have been kept. By convention this time,
$t_0=t_{r+1}=-\infty$.


\medskip
{\it Construction of the transformation ${\bf D}$.}\quad
There are four steps in the construction:

(1) The first step consists of transposing the factors $t_ih_i$
and $p_id_i$ in each compartment, for $i=1,2,\ldots,r$, the first
compartment remaining alike, to obtain:
$$
h_0p_0d_0\mid p_1d_1t_1h_1\mid p_2d_2t_2h_2\mid\;\ldots \;
\mid p_rd_rt_rh_r.
$$

(2) Let $x$ be a letter of the factor $d_i$ $(1\le i\le r)$. Either there
exists an integer~$j$ such that $1\le j\le i$ and $p_j>x>t_j$ and 
$\psi^-(x)$ will denote the {\it greatest} integer with those properties,
or such an integer does not exist and we define $\psi^-(x):=0$. Also let
$\psi^-(x):=0$ for each letter~$x$ in the factor~$d_0$.


(3) For each $i=0,1,\ldots,r$ form the {\it decreasing} factor $\overline
d_i$ with all the letters~$x$ such that $\psi^-(x)=i$.

$(4')$ If the word $\overline d_0$ is empty, define $\bfD\,\sigma$
to be the word in~$A^*$ [later it will be shown that each letter
$(\,\dots\,)$ is an oiseau]
$$
{\bf D}\,\sigma:=(\infty 0h_0p_0)(p_1\overline d_1t_1h_1)
(p_2\overline d_2t_2h_2)\;\ldots\;(p_r\overline d_rt_rh_r).
$$

\def\debut{\overline d_0\kern0.01pt'\kern1pt }

$(4'')$ If $\overline d_0$ is nonempty, denote 
its rightmost letter by $t_0$, so that $\overline d_0$ may be
written as $\overline d_0=\debut t_0$ for some (decreasing) factor
$\debut$. If $h_0=e$, let $h'_0=h''_0:=e$; if $t_0\ll h_0$, let
$h'_0:=e,\ h''_0:=h_0$; if $h_0\ll t_0$, let $h'_0:=h_0$,
$h''_0:=e$. Otherwise, the word~$h_0$ may be expressed (in a
unique manner) as
$h_0=h'_0h''_0$, in such a way that
$h'_0\ll t_0\ll h''_0$. Then define
$$
{\bf D}\,\sigma:=(\infty 0h'_0)(p_0\debut t_0h_0'')(p_1\overline
d_1t_1h_1) (p_2\overline d_2t_2h_2)\;\ldots\;(p_r\overline d_rt_rh_r).
$$

{\it Example} 1.\quad Consider the following permutation already
trough-factorized:
$$\displaylines{\noalign{\vskip-8pt}
\sigma=18\vtop{\hbox{,}\smallskip\hbox{0}}\pic {20}\mid\petittrou
3,7\vtop{\hbox{,}\smallskip\hbox{1}}\pic{17}\mid
\petittrou{16},\pic{19}\vtop{\hbox{,}\smallskip\hbox{2}}15,6\mid
\petittrou2,12\vtop{\hbox{,}\smallskip\hbox{3}}\pic{14},10\mid
\petittrou9,\pic{13}\vtop{\hbox{,}\smallskip\hbox{4}}11,8\mid
\petittrou1,\pic{5\;}\kern-3pt\vtop{\hbox{,}\smallskip\hbox{5}}4.\cr
\noalign{\hbox{Step (1) yields}}
18\vtop{\hbox{,}\smallskip\hbox{0}}\pic {20}\mid\pic{17}
\vtop{\hbox{,}\smallskip\hbox{1}}\petittrou
3,7\mid \pic{19},15\vtop{\hbox{,}\smallskip\hbox{2}}6,
\petittrou{16}\mid\pic{14},10\vtop{\hbox{,}\smallskip\hbox{3}}\petittrou2,12\mid
\pic{13},11\vtop{\hbox{,}\smallskip\hbox{4}}8,
\petittrou9\mid\pic{5\;}\kern-3pt
,4\vtop{\hbox{,}\smallskip\hbox{5}}\petittrou1.\cr}
$$
In step (2) we have to define:
$\psi^-(15)=1$, $\psi^-(6)=1$, $\psi^-(10)=3$,
$\psi^-(11)=4$, $\psi^-(8)=3$; $\psi^-(4)=5$, so that we may
form, as prescribed in step~(3),\quad
$\overline d_0=e$;\quad $\overline d_1=15,6$;\quad $\overline
d_2=e$;\quad $\overline d_3=10,8$;\quad $\overline
d_4=11$;\quad $\overline d_5=4$.

As $\overline d_0=e$, step $(4')$ applies, so that
$${\bf D}\,\sigma\!:=\!(\infty, 0,18,20)(17,15,6,3,7)
(19,16)(14,10,8,2,12)(13,11,9)(5,4,1).
$$

{\it Example} 2.\quad With the permutation
$$\displaylines{\noalign{\vskip-6pt}
\sigma=1,6,11\vtop{\hbox{,}\smallskip\hbox{0}}\pic{18},17\mid
\petittrou{16},\pic{20}\vtop{\hbox{,}\smallskip\hbox{1}}15
\mid\petittrou8,12\vtop{\hbox{,}\smallskip\hbox{2}}
\pic{14}\mid\petittrou{10},\pic{13}\vtop{\hbox{,}\smallskip\hbox{3}}9,7\mid
\petittrou 2,4,\pic{19}\vtop{\hbox{,}\smallskip\hbox{4}}5,3,\cr
\noalign{\hbox{already trough-factorized, step (1) yields:}}
1,6,11\vtop{\hbox{,}\smallskip\hbox{0}}\pic{18},17\mid
\pic{20},15\vtop{\hbox{,}\smallskip\hbox{1}}\petittrou{16}\mid
\pic{14},\petittrou8\vtop{\hbox{,}\smallskip\hbox{2}}12\mid
\pic{13},9\vtop{\hbox{,}\smallskip\hbox{3}}7,\petittrou{10}\mid
\pic{19},5\vtop{\hbox{,}\smallskip\hbox{4}}3,\petittrou 2,4.\cr}
$$
In step (2) we define: $\psi^-(17)=0$, $\psi^-(15)=0$,
$\psi^-(9)=2$, $\psi^-(7)=0$, $\psi^-(5)=4$,
$\psi^-(3)=4$. In step~(3) we get:\quad
$\overline d_0=17,15,7$;\quad
$\overline d_1=e$;\quad
$\overline d_2=9$;\quad
$\overline d_3=e$;\quad
$\overline d_4=5,3$.
As $\overline d_0=17,15,7$ is nonempty, we apply $(4'')$
with $h_0=1,6,11$ and $\debut =7$. We
get 
$h'_0=1,6<7<11=h_0''$. Hence
$${\bf D}\,\sigma
\!=\!(\infty,0,1,6)(18,17,15,7,11)(20,16)(14,9,8,12)(13,10)(19,5,3,2,4).
$$

\medskip
Several properties are to be verified.

(a) {\it Each letter in $\bfD\,\sigma$ is an oiseau}.\quad
First, $0\ll h_0\ll p_0$, so that $(\infty0h_0p_0)$ is an oiseau. Next,
for each $i=1,2,\ldots, r$ we have $p_i\gg \overline d_i\gg t_i$
by (2)--(3). Also $t_i\ll h_i\ll p_i$, since $t_i$ is a trough
and~$p_i$ a peak in the permutation~$\sigma$. Consequently,
for each
$i=1,2,\ldots, r$, each letter $(p_i\overline d_it_ih_i)$ is an oiseau.

Now, if $x$ is a letter in~$d_0$, it is also a letter in~$\overline
d_0$ by (2), so that $p_0\gg x\gg t_1$. Furthermore, if~$x$ is a letter
of some~$d_i$ with $1\le i\le r$ and $\psi^-(x)=0$, then $x<t_1$,
$x<t_2$, \dots~, $x<t_i$. As $p_0\gg t_1$, we conclude that
$p_0\gg x$. Hence, $p_0\gg \overline d_0$ and $(p_0\overline
d_0h_0'')=(p_0\debut t_0h''_0)$ is also an oiseau.

\medskip
(b) {\it The word $\bfD\,\sigma$ is $C$-maximal}.\quad
First $(\infty0h_0p_0)$ (resp. $(\infty0h'_0)$) does not commute
with any one of the other letters in~$\bfD\,\sigma$. As $t_{i+1}$ is
the closest trough to the right of the peak~$p_i$ in~$\sigma$, we
have $p_i>t_{i+1}$ $(i\ge 1)$. Hence
$p_i\overline d_it_ih_i\ll p_{i+1}\overline d_{i+1}t_{i+1}h_{i+1}$
cannot hold. It then follows that if 
$(p_i\overline d_it_ih_i)$ and 
$(p_{i+1}\overline d_{i+1}t_{i+1}h_{i+1})$ commute, we necessarily
have $p_i\overline d_it_ih_i\gg p_{i+1}\overline
d_{i+1}t_{i+1}h_{i+1}$. Finally, as $p_0>t_1$, we show, using the
same argument, that if $(p_0\debut t_0h''_0)$ and $(p_1\overline
d_1t_1h_1)$ commute, we have
$(p_0\debut t_0h''_0)\gg (p_1\overline d_1t_1h_1)$. Thus
$\bfD\,\sigma$ is $C$-maximal.

\medskip
(c) {\it Construction of the inverse $\bfD^{-1}$}.\quad
Compare steps $(4')$ and $(4'')$. In $(4')$ the rightmost letter
$p_0$ in the first oiseau is greater than the
trough $t_1$ in the second oiseau. In $(4'')$ the rightmost letter of
$0h'_0$ in the first oiseau is less than the trough~$t_0$ in the
second oiseau. This makes up the first step in the definition of
the reverse of~$\bfD$.
Let $v=\omega_0\omega_1\ldots\omega_s$ belong
to~$B_n^{\max}$ with
$\omega_0=(\infty0k_0)$. If~$s=0$, then
$\bfD^{-1}\,v=k_0=1,2,\ldots,n$. Assume now that
$s\ge 1$.

$(i)$ If the rightmost letter of~$0k_0$ is {\it not} less than the
trough in the oiseau~$\omega_1$, it cannot be~0; denote it
by~$p_0$. We may express~$v$ as
$$
v=(\infty 0h_0p_0)(p_1\overline d_1t_1h_1)
(p_2\overline d_2t_2h_2)\;\ldots\;(p_r\overline d_rt_rh_r),
\leqno(5.1)
$$
with $r=s$, $0h_0p_0=0k_0$ and $(p_i\overline
d_it_ih_i)=\omega_i$ for $i=1,2,\ldots,r$.

$(ii)$
If the rightmost letter of~$0k_0$ is less than the trough is the
oiseau~$\omega_1$, we may express~$v$ as
$$
v=(\infty 0h'_0)(p_0\debut t_0h_0'')(p_1\overline
d_1t_1h_1) (p_2\overline d_2t_2h_2)\;
\ldots\;(p_r\overline d_rt_rh_r),
\leqno(5.2)
$$
with $r=s-1$, $\omega_0=(\infty0k_0)=(\infty0h'_0)$,
$\omega_1=(p_0\debut t_0h''_0)$ and 
$\omega_{i+1}=(p_i\overline d_i t_ih_i)$ for
$i=0,1,\ldots,r$ and $0h'_0\ll t_0$. Then define
$h_0:=h'_0h''_0$,
$\overline d_0:=\debut t_0$.

In both cases the words $\overline d_i$, $h_i$ and the letter
$p_i$ have been defined for each $i=0,1,\ldots,r$ and the
letter~$t_i$ for $i=1,2\ldots,r$. We form the factorization
$$
h_0p_0\overline d_0\mid
t_1h_1p_1\overline d_1\mid
t_2h_2p_2\overline d_2\mid\;\cdots\;\mid
t_rh_rp_r\overline d_r.\leqno(5.3)
$$
With the convention $t_{r+1}=-\infty$ and for $i=0,1,\ldots,
r$ we move each letter~$x$ of~$\overline d_i$ {\it
to the right} until it falls between a peak~$p_j$ and the next
trough~$t_{j+1}$. More formally, we define $\psi(x)$ to be the
least integer~$j$ such that $i\le j\le r$ and
$p_j>x>t_{j+1}$ and let $d_j$ be the {\it decreasing} word with
all the letters~$x$ such that $\psi(x)=j$. As $t_i\ll h_i\ll p_i$,
because the letters of~$v$ are oiseaux, the factorization
$$
h_0p_0 d_0\mid
t_1h_1p_1 d_1\mid
t_2h_2p_2 d_2\mid\;\cdots\;\mid
t_rh_rp_r d_r\leqno(5.4)
$$
is a trough factorization of a permutation. This defines
$\bfD^{-1}\,v$. We also convince ourselves that
$\bfD^{-1}\bfD$ and $\bfD\bfD^{-1}$ are identity maps.

\medskip
{\it Example} 1.\quad Let
$$v=(\infty, 0,18,20)(17,{\bf15,6},3,7)
(19,16)(14,{\bf10,8},2,12)(13,\bf{11},9)(5,{\bf4},1)
$$
belong to $B_{20}^{\max}$. As the rightmost letter~20 of the
factor $0,18,20$ is not less than the trough~3 of the second
oiseau, step~$(i)$ applies. We define $h_0=18,20$, $p_0=20$,
$\overline d_1={\bf15,6}$, $\overline d_2=e$, $\overline
d_3={\bf10,8}$,
$\overline d_4=\bf{11}$, $\overline d_5={\bf4}$. Next, form the
factorization introduced in (5.3)
$$
18,20\mid 3,7,17,{\bf15,6}\mid
16,19\mid
2,12,14,{\bf10,8}\mid
9,13,{\bf11}\mid
1,5,{\bf4}
$$
and move the letters of the $\overline d_i$'s (the letters in
boldface) to the right until they are inserted correctly between a
peak and the next trough. We get
$$
18,20\mid 3,7,17\mid
16,19,{\bf15,6}\mid
2,12,14,{\bf10}\mid
9,13,{\bf11,8}\mid
1,5,{\bf4}.
$$
This is the trough factorization of the permutation $\bfD^{-1}v$.

\medskip
{\it Example} 2.\quad
The following word
$$
v=(\infty,0,1,6)(18,17,15,7,11)(20,16)(14,9,8,12)(13,10)(19,5,3,2,4)
$$
belongs to $B_{20}^{\max}$. The rightmost letter~6 of the factor
$0,1,6$ is less than the trough~7 of the second oiseau, so that
step~$(ii)$ applies. We have $h'_0=1,6$, $p_0=18$,
$\debut=17,15$, $t_0=7$, $h''_0=11$, then
$h_0=h'_0h''_0=1,6,11$, $\overline d_0=\debut t_0={\bf 17,15,7}$,
$\overline d_1=e$, $\overline d_2={\bf 9}$, $\overline d_3=e$,
$\overline d_4={\bf 5,3}$. Thus, the (5.1)-factorization reads
$$
1,6,11,18,{\bf 17,15,7}\mid
16,20\mid 8,12,14,{\bf9}\mid
10,13\mid 2,4,19,{\bf 5,3}.
$$
Next, we move the letters in bold-face to the right, following the
rule described before. We get:
$$
1,6,11,18,{\bf 17}\mid
16,20,{\bf 15}\mid
8,12,14\mid
10,13,{\bf 9,7}\mid
2,4,19,{\bf 5,3},
$$
which is the trough factorization of a permutation
$\sigma=\bfD^{-1}v$.

\bigskip
\centerline{\bf 6.  Order statistics}

\nobreak
\medskip
Let $0\sigma=0x_1x_2\ldots x_n$ be a permutation, starting
with~0, whose peak factorization reads
$$t_0h_0\mid p_1d_1t_1h_1\mid p_2d_2t_2h_2\mid\;\ldots \;
\mid p_rd_rt_rh_r.$$  
Let $p_0:=\infty$, $d_0:=e$,
$t_0=0$ and for
$0\le i<j\le r$ let $|p_id_it_ih_i|_{]t_j,p_j[}$ denote the
number of letters in the word $p_id_it_ih_i$ that
belong to the open interval $]t_j,p_j[$. 
As only the factors $p_id_it_i$ contain subfactors of the
form~$ca$, we can express
$(b\tir ca)\sigma$ as
$$
(b\tir ca)\sigma=\sum_{1\le j\le
r}\sum_{i<j}|p_id_it_ih_i|_{]t_j,p_j[}.\leqno(6.1)
$$

Now, let
$v=(\infty0h_0)(p_1d_1t_1h'_1)\ldots (p_rd_rt_rh'_r)$
belong to the $C$-equiv\-alence class $B_n$ and define
$$
(b\tir ca)v:=\sum_{1\le j\le
r}\sum_{i<j}|p_id_it_ih'_i|_{]t_j,p_j[},\leqno(6.2)
$$
keeping the convention $p_0:=\infty$, $d_0:=e$,
$t_0=0$. When two oiseaux
$(p_id_it_ih'_i)$, $(p_jd_jt_jh'_j)$ commute,~then
$|p_id_it_ih'_i|_{]t_j,p_j[}=0$.
It then follows that if two elements $v$, $v'$ in~$A^*$, of
valuation~$1^n$, are $C$-equivalent, then
$$
(b\tir ca)v=(b\tir ca)v'.\leqno(6.3)
$$

When we go from $\sigma$ to ${\bf d}\,\sigma$,
only the {\it positions} of some double-rises~$y$ change, and if
they do, those double-rises move {\it to the left}, but not to
the left of factors
$p_id_it_ih_i$ such that 
$p_i>y$, as shown in (4.2). Hence, we also have
$$|p_id_it_ih'_i|_{]t_j,p_j[}
=|p_id_it_ih_i|_{]t_j,p_j[}
$$
for $0\le i<j\le r$. Hence,
$$
(b\tir ca)\sigma =(b\tir ca)\bfd\,\sigma.\leqno(6.4)
$$
But as the statistic $(b\tir ca)$ depends only on the
$C$-equivalence class and not on its representative by (6.3), we
also have
$$
(b\tir ca)\theta(\bfd\,\sigma)=(b\tir ca)\bfd\,\sigma.\leqno(6.5)
$$
The next proposition is the analog for~$\bfD$ of
property~(6.4). It requires a longer proof.

\proclaim Proposition 6.1. Let $\sigma$ be a permutation of
order~$n$. Then
$$
(b\tir ca)\sigma -(b\tir ca)\bfD\,\sigma
=n-\Last \sigma -\des\sigma. \leqno(6.6)
$$

{\it Proof}.\quad
Let $v:=\bfD\,\sigma$. As seen in Section~5 (c), the element~$v$
is in $B_n^{\max}$ and appears in the form (5.1) or in the form
(5.2). When $r=0$, we have $v=(\infty 0h_0p_0)$ or
$v=(\infty0h'_0)(p_0\debut t_0h''_0)$.  In the first case,
$\sigma=h_0p_0$ is the increasing word
$12\ldots n$ and identity (6.6) holds. In the second case, 
$\sigma=h'_0h''_0p_0\debut t_0$ and $\des\sigma=|p_0\debut|$,
$(b\tir ca)\sigma=|h'_0h''_0|_{\textstyle ]t_0,p_0[}
=|h''_0|_{\textstyle ]t_0,p_0[}=|h''_0|$. On the other hand,
$(b\tir ca)\,\bfD\,\sigma=|h'_0|_{\textstyle ]t_0,p_0[}=0$, since
$h'_0\ll t_0$, whenever $h'_0$ is nonempty. Thus, the left-hand
side of (6.6) is equal to $|h''_0|$. 

To evaluate the right-hand side of (6.6) consider the two cases:
\hfil\break
(i) $h'_0=h''_0= e$; (ii) $h'_0$, $h''_0$ not both empty.
In case~(i)
$n-\Last\sigma-\des\sigma=p_0-1-(p_0-1)=0=|h''_0|$, since
$p_0\debut t_0=n(n-1)\ldots 1$. In case~(ii) we have
$n-\Last\sigma-\des\sigma=p_0-1-|p_0\debut|
=p_0-|p_0\debut t_0|$, which is equal to the number of letters
in~$\sigma$ less than~$t_0$. This number is precisely
$|h''_0|$. Thus (6.6) holds for $r=0$

We then proceed by induction on~$r$ and assume that $r\ge 1$.
The construction of~$\bfD$, given in Section~5, depends only on
the total ordering on the set $\{1,2,\ldots, n\}$. The latter set can
then be replaced by any set~$E$ of integers of the same
cardinality. Let ${\cal S}_E$ be the set of the permutations
of~$E$. Then the set $\bfD({\cal S}_E)$ will again be denoted by
$B_n^{\max}$, the context indicating the underlying set~$E$
that is on use.

Having this convention in mind we can write~$v$,
using the notations (5.1) and (5.2), as $v=v_1(p_r\overline
d_rt_rh_r)$, where~$v_1$ is an element of
$B_{n_1}^{\max}$ for some
$n_1\le n-2$. Let $\sigma_1:=\bfD^{-1}v_1$. Again notice
that~$\sigma_1$ is a permutation of a set of cardinality~$n_1$.
We shall evaluate the left-hand side of (6.6) as the sum
$U_1+U_2-U_3$, where
$$\displaylines{
U_1:=(b\tir ca)\sigma-(b\tir ca)\sigma_1;\quad
U_2:=(b\tir ca)\sigma_1-(b\tir ca)v_1;\cr
U_3:=(b\tir ca)v-(b\tir ca)v_1.\cr}
$$

{\it A first evaluation of $U_3$}.\quad
Using (5.1) and (5.2) let
$$\displaylines{
w:=h_0p_0p_1\overline d_1t_1h_1
\ldots p_{r-1}\overline
d_{r-1}t_{r-1}h_{r-1}\cr
\noalign{\hbox{(resp.
$h'_0p_0\debut t_0h_0''p_1\overline
d_1t_1h_1
\ldots p_{r-1}\overline d_{r-1}t_{r-1}h_{r-1}$). Then}}
\rlap{(6.7)}\hfill
(b\tir ca)v-(b\tir ca)v_1
=|w|_{\textstyle ]t_r,p_r[}.\hfill\cr}
$$

\smallskip
{\it Evaluation of $U_1$}.\quad
By (5.4) $\sigma=h_0p_0 d_0
t_1h_1p_1 d_1
\ldots
t_rh_rp_r d_r$.
In the construction of $\bfD^{-1}\sigma$ the
decreasing factor~$d_r$ is made of the double-descents~$x$
in~$w$ such that
$\psi(x)=r$ [let $d'_{r-1}$ be the decreasing word made of those
letters~$x$], plus all the double-descents in the factor~$\overline
d_r$.  Also, by construction, 
$$\leqalignno{d'_{r-1}&\ll t_r&(6.8)\cr
\noalign{\hbox{and also,}}
t_r &\ll \overline d_r,&(6.9)\cr
\noalign{\hbox{since $(p_rd_rt_r\overline h_r)$ is an oiseau.
Hence}}
d_r&=\overline d_rd'_{r-1}.&(6.10)\cr}
$$
Accordingly, 
$$\leqalignno{\noalign{\vskip-7pt}
\sigma&=h_0p_0 d_0
t_1h_1p_1 d_1
\ldots t_{r-1}h_{r-1}p_{r-1}d_{r-1}
t_rh_rp_r \overline d_rd'_{r-1};\cr
\sigma_1&=h_0p_0 d_0
t_1h_1p_1 d_1
\ldots t_{r-1}h_{r-1}p_{r-1}d_{r-1}
d'_{r-1}.\cr}
$$
We can evaluate $U_1$, the open intervals to be considered
being $]t_r,p_{r-1}[$ and $]\Last\sigma,p_r[$ for~$\sigma$ and
$]\Last\sigma_1,p_{r-1}[$ for~$\sigma_1$. We get
$$
\leqalignno{
U_1&=|\sigma_1|_{\textstyle ]t_r,p_{r-1}[}
-|p_{r-1}d_{r-1}d'_{r-1}|_{\textstyle ]t_r,p_{r-1}[}&(6.11)\cr
&\qquad{}+|\sigma_1|_{\textstyle ]\Last\sigma,p_r[}
-|d'_{r-1}|_{\textstyle ]\Last\sigma,p_r[}
+|t_rh_r|_{\textstyle ]\Last\sigma,p_r[}\cr
&\qquad{}-|\sigma_1|_{\textstyle ]\Last\sigma_1,p_{r-1}[}
+|p_{r-1}d_{r-1}d'_{r-1}|_{\textstyle ]\Last\sigma_1,p_{r-1}[}.
\cr
}
$$

\smallskip
{\it Evaluation of $U_2$}.\quad
As the bottoms of the descents are the $t_i$'s and the
double-descents, we have:
$\des\sigma-\des\sigma_1= |d_{r-1}t_r|+|\overline
d_rd'_{r-1}|-|d_{r-1}d'_{r-1}| =|t_r\overline d_r|$. On the other
hand,
$n-\Last\sigma=|\sigma|_{\textstyle]\Last\sigma,+\infty[}$, so
that by induction
$$\leqalignno{
U_2
&=|\sigma_1|_{\textstyle]\Last\sigma_1,+\infty[}-\des\sigma_1
&(6.12)\cr
&=|\sigma_1|_{\textstyle]\Last\sigma_1,+\infty[}-\des\sigma
+|t_r\overline d_r|.\cr}
$$

\smallskip
{\it Evaluation of $U_3$}.\quad
Again take the expression derived in (6.7). The word~$w$ is a
rearrangement of $h_0p_0\overline d_0t_1h_1p_1\overline d_1
\ldots t_{r-1}h_{r-1}p_{r-1}\overline d_{r-1}$ [see (5.3)] and
also of $h_0p_0d_0t_1h_1p_1
\ldots t_{r-1}h_{r-1}p_{r-1} d_{r-1}d'_{r-1}=\sigma_1$ [see
(5.4)] by definition of~$d'_{r-1}$. Hence
$$
U_3=|\sigma_1|_{\textstyle]t_r,p_r[}.\leqno(6.13)
$$
To calculate $U_1+U_2-U_3$ two cases are to be considered:
(i) $\Last\sigma=\Last\sigma_1$;
(ii) $\Last\sigma\not=\Last\sigma_1$.

\medskip
Case (i): The factor $d'_{r-1}$  is nonempty. By (6.8) we have
$\Last\sigma=\Last d'_{r-1}<\ t_r$ and
$$-|p_{r-1}d_{r-1}d'_{r-1}|_{\textstyle ]t_r,p_{r-1}[}
-|d'_{r-1}|_{\textstyle
]\Last\sigma,p_r[}+|p_{r-1}d_{r-1}d'_{r-1}|_{\textstyle
]\Last\sigma,p_{r-1}[}=0.
$$
There are three terms of the form
$|\sigma|_{]\ldots[}$ in (6.11) and one in (6.13) and their
contribution to
$U_1-U_3$ is
$$
|\sigma_1|_{\textstyle ]t_r,p_{r-1}[}
+|\sigma_1|_{\textstyle ]\Last\sigma,p_r[}
-|\sigma_1|_{\textstyle ]\Last\sigma_1,p_{r-1}[}
-|\sigma_1|_{\textstyle]t_r,p_r[}=0,
$$
since $\Last\sigma\!=\!\Last\sigma_1$. Hence
$$\eqalignno{
U_1+U_2-U_3
&=|t_rh_r|_{\textstyle ]\Last\sigma,p_r[}
+|\sigma_1|_{\textstyle]\Last\sigma,+\infty[}-\des\sigma
+|t_r\overline d_r|\cr
&=|\sigma_1|_{\textstyle]\Last\sigma,+\infty[}
+ |p_r\overline d_rt_rh_r|-\des\sigma\cr
&=|\sigma|_{\textstyle]\Last\sigma,+\infty[}
-\des\sigma.\cr}
$$

\smallskip
Case (ii): The factor $d'_{r-1}$ is then empty and
$\Last\sigma_1=\Last p_{r-1}d_{r-1}>t_r$, $\Last\sigma>t_r$,
$\overline d_r=d_r$.
Then
$$
\displaylines{\noalign{\vskip-5pt}
|\sigma_1|_{\textstyle]\Last\sigma_1,+\infty[}
+|\sigma_1|_{\textstyle ]t_r,p_{r-1}[}
+|\sigma_1|_{\textstyle ]\Last\sigma,p_r[}
-|\sigma_1|_{\textstyle ]\Last\sigma_1,p_{r-1}[}
-|\sigma_1|_{\textstyle]t_r,p_r[}\hfill\cr
\kern3.1cm{}
=|\sigma_1|_{\textstyle]\Last\sigma_1,+\infty[}
+|\sigma_1|_{\textstyle
]t_r,\Last\sigma_1]} -|\sigma_1|_{\textstyle ]t_r,\Last\sigma]}
\hfill\cr
\kern3.1cm{}
=\cases{|\sigma_1|_{\textstyle]\Last\sigma_1,+\infty[}+|\sigma_1|_{\textstyle
]\Last\sigma,\Last\sigma_1]}, &if
$\Last\sigma<\Last\sigma_1$;\cr 
|\sigma_1|_{\textstyle]\Last\sigma_1,+\infty[}-|\sigma_1|_{\textstyle
]\Last\sigma_1,\Last\sigma]}, &if
$\Last\sigma_1<\Last\sigma$.\cr}\hfill\cr 
\kern3.1cm{}
=|\sigma_1|_{\textstyle]\Last\sigma,+\infty[}.\hfill\cr
\noalign{\hbox{Also}}
\!-|p_{r-1}d_{r-1}d'_{r-1}|_{\textstyle ]t_r,p_{r-1}[}
-|d'_{r-1}|_{\textstyle ]\!\Last\sigma,p_r[}
+|p_{r-1}d_{r-1}d'_{r-1}|_{\textstyle
]\!\Last\sigma_1,p_{r-1}[}\!\!=\!\!-1.\cr
\noalign{\hbox{Hence}}
\eqalign{
U_1+U_2-U_3
&=|\sigma_1|_{\textstyle]\Last\sigma,+\infty[}
-\des\sigma+|t_rh_r|_{\textstyle ]\Last\sigma,p_r[}
+|t_r\overline d_r|-1\cr
&=|\sigma_1|_{\textstyle]\Last\sigma,+\infty[}
-\des\sigma+|p_rd_rt_rh_r|_{\textstyle]\Last\sigma,+\infty[}\cr
&=|\sigma|_{\textstyle]\Last\sigma,+\infty[}
-\des\sigma.\qed\cr}\cr
}
$$

With the completion of Proposition 6.1 all the statements of
Theorem~1.1 have been proved, except statement~(iv). In fact,
only the steps $(4')$ and $(4'')$ in the definition of~$\bfD$
(see Section~5) modify the nature of some peaks, troughs,
double-descents or double-rises. In $(4')$ the peak~$p_0$
becomes a double-rise, but troughs and double-descents remain
alike. In $(4'')$ the rightmost letter of $\overline d_0$, a
descent, becomes a trough. In both cases, the {\it set} of troughs
and double-descents is not modified. This proves statement~(iv).

\bigskip
\centerline{\bf 7. Euler-Mahonian Statistics}

\nobreak
\medskip
Let us go back to the notation introduced by
Babson and  Steingr\'\i msson [BaSt00] for ``atomic" permutation
statistics. For each permutation
$\alpha,\beta,\gamma$ of
${a,b,c}$ the expression $(\alpha\tir \beta\gamma)(w)$ is meant to
be the number of pairs
$(i,j)$, $1 \leq i <j<n$, such that the orderings of
the two triples $(x_i,x_j,x_{j+1})$ and $(\alpha,\beta,\gamma)$
are identical. Of course,
$(ba)\sigma$ denotes the number of {\it descents}, $\des \sigma $
(i.e. the number of places $1 \leq i <n$ such that $x_i>x_{i+1}$).
Finally, $[b\tir a)\sigma$ is the number of of $x_j$ such that
$x_1>x_j$, that is,
$x_1-1$.

Using these atomic objects, Babson and Steingr\'\i msson noticed
that the two classical {\it Mahonian} 
statistics, the inversion number ``$\inv$"
and the major index ``$\maj$" could be written in terms of those
patterns. For instance,
$\inv=(bc\tir a)+(ca\tir b)+(cb\tir a)+(ba)$ and
$\maj=(a\tir cb)+(b\tir ca)+(c\tir ba)+(ba)$. It is worth
mentioning that an analogous notation has been introduced by
Han ([Ha94], theorem~2.1) that enabled him to make a link between
the major index and the Denert statistic. The former authors were
then motivated to perform a computer search for all statistics that
could be thus written and be ``conjecturally Mahonian." Several of
the statistics they have introduced have been shown to be
Mahonian since. However their {\it Conjecture}~11 has remained
open (it will be stated later on). Our purpose will be to prove its
correctness by using the previous algebraic set-up. Before doing
so let us recall some basic notations and facts about
Euler-Mahonian statistics.

As usual,
$$\leqalignno{
(a;q)_n&:=\cases{1,&if $n=0$;\cr
(1-a)(1-a q)\,\ldots\,(1-a q^{n-1}),&if
$n\geq 1$;\cr} &(7.1)\cr
(a;q)_{\infty }&:=\lim\nolimits_n(a;q)_n=
{\textstyle \prod\limits _{n\geq 0}(1-a
q^n)}.&(7.2)\cr 
\noalign{\hbox{Also,}}
[n]_q&:={1-q^n\over 1-q}=(1+q+\cdots +q^{n-1});&(7.3)\cr
[n]_q!&:={(q;q)_n\over (1-q)^n}
=[n]_q\,[n-1]_q\,\cdots\,[1]_q&(7.4)\cr &=(1+q+\cdots
+q^{n-1})(1+q+\cdots+q^{n-2})\cdots(1).\cr }
$$

The sequence of polynomials $([n]_q!)$
$(n\ge 0)$ is said to be {\it Mahonian}. On the other hand, a
statistic ``stat" (actually, we should say a sequence
$(\stat_n)$ $(n\ge 0$) of statistics, where $\stat_n$ is defined on
the symmetric group~${\cal S}_n$) is  said to be {\it Mahonian},
if for every $n\ge0$ we have
$$
\sum_{w\in {\cal S}_n} q^{\stat w}=[n]_q!
$$

A sequence $(A_n(t,q))$ $(n\ge 0)$ of polynomials in two
variables~$t$ and~$q$, is said to be {\it Euler-Mahonian}, if one
of the following {\it equivalent} conditions holds:

(1) For every $n\ge 0$,
$$
{1\over (t;q)_{n+1}}\,A_n(t,q)
=\sum_{s\ge 0}t^s\,
\bigl([s+1]_q\bigr)^n.\leqno(7.5)
$$

(2) The exponential generating function for the fractions
$\displaystyle\smash{{A_n(t,q)\over (t;q)_{n+1}}}$ is given by:
$$
\sum_{n\ge 0}{u^n\over n!}\,
{A_n(t,q)\over (t;q)_{n+1}}
=\sum_{s\ge 0} t^s\, \exp(u\,[s+1]_q).\leqno(7.6)
$$

(3) The sequence $(A_n(t,q))$ satisfies the recurrence relation:
$$
(1-q) \,A_n(t,q)
= (1-tq^{n}) \,A_{n-1}(t,q) -q
(1-t) \,A_{n-1}(tq,q).\leqno(7.7)
$$

(4) Let \smash{$A_n(t,q)=\sum \limits_{s\ge
0} t^s\,A_{n,s}(q)$}. Then the coefficients $A_{n,s}(q)$
satisfy the recurrence:
$$
A_{n,s}(q)
= [s+1]_q\,A_{n-1,s}(q)
+q^{s}[n-s]_q\,A_{n-1,s-1}(q).\leqno(7.8)
$$

\medskip
It is routine to prove that those four conditions are equivalent
(see, e.g. [ClFo95, \S\S\kern2pt 6,7] for a proof in a more general
setting). Now a pair of statistics $(\stat_1,\stat_2)$ defined on
each symmetric group ${\cal S}_n$ $(n\ge 0)$ is said to be {\it
Euler-Mahonian}, if for every $n\ge 0$ we have
$$
\sum_{w\in {\cal S}_n} t^{\stat_1 w}q^{\stat_2 w}
=A_n(t,q).
$$

The first values of the Euler-Mahonian polynomials are the
following:
$A_0(t,q)=A_1(t,q)=1$; $A_2(t,q)=1+tq$;
$A_3(t,q)=1+t(2q+2q^2)+t^2q^3$;

\noindent
$A_4(t,q)=1+t(3q+5q^2+3q^3)+t^2(3q^3+5q^4+3q^5)
+t^3q^6$;

\noindent
$A_5(t,q)=1+t(4q+9q^2+9q^3+4q^4)
+t^2(6q^3+16q^4+22q^5+16q^6+6q^7)$

$\qquad{}+t^3(4q^6+9q^7+9q^8+4q^9)+t^4q^{10}$.

\medskip
The bistatistic that is  Euler-Mahonian, {\it par excellence}, is
the pair $(\des,\maj)$. The proof of this statement goes back to
Carlitz [Ca54], [Ca59], although some $q$-calculations for
the major index already appeared in [Ma15]. Further bistatistics
have since been introduced and proved to be Euler-Mahonian, in
particular the pair $(\des,\mak)$ (see [FoZe90]), where
$$
\mak:=(a\tir cb)+(b\tir ca)+(cb\tir a)+ (ba).\leqno(7.9)
$$
Actually, the original ``mak", as introduced by Foata and
Zeilberger [FoZe90], reads
$$
(a\tir cb)+(ca\tir b)+(cb\tir a)+ (ba),
$$
but Babson and Steingr\'\i msson changed the
notation. However, we shall stick with Definition (7.9) in the
sequel. Notice that to prove that $(\des,\mak)$ is Euler-Mahonian
requires only a slight modification in the argument used
in [FoZe90], \S\kern2pt 8. Babson-Steingr\'\i msson's
Conjecture~11 is the following.    

\proclaim Conjecture 11. Let 
$$
\eqalignno{\noalign{\vskip-7pt}
S_1&:=(a\tir cb)+(b\tir ac)+(cb\tir a)+[b\tir a),\cr 
S_2&:=(a\tir cb)+(b\tir ac)+(c\tir ba)+[b\tir a),\cr
S_3&:=(a\tir cb)+(b\tir ca)+(cb\tir a)+[b\tir a),\cr
S_4&:=(a\tir cb)+(b\tir ca)+(c\tir ba)+[b\tir a).\cr
}
$$
Then the bistatistics $(\des,S_i)$ for $i=1,2,3,4$ are
Euler-Mahonian.

In the next section we prove that $(\des,S_1)$ and $(\des,S_3)$
are equidistributed with $(\des,\mak)$ (this requires the
machinery developed in the previous sections). The last section is
devoted to proving that $(\des,S_2)$ and $(\des,S_4)$
are equidistrubuted with $(\des,\maj)$. This is far easier.

\goodbreak
\bigskip
\centerline{\bf 8. The transformation $\Phi$}

\nobreak
\medskip
The transformation
$$
\Phi:={\bfD}^{-1}\theta\,{\bfd},\leqno(8.1)
$$ 
already introduced in the introduction,
maps the permutation group ${\cal S}_n$ onto itself. Let
$\Phi^{-1}$ be the inverse bijection. As is often the case, such
combinatorial bijections are now combined with the classical
dihedral transformations, namely the {\it reverse image}~$\bfr$
and the {\it complement}~$\bfc$ that map each permutation
$\sigma=x_1x_2\ldots x_n$ onto
$\bfr\,\sigma=x_n\ldots x_2x_1$ and
$\bfc\,\sigma=(n+1-x_1)(n+1-x_2)\ldots (n+1-x_n)$,
respectively.

Denote by $\dbv\sigma$ the sum of the {\it descent bottom values}
of the permutation~$\sigma$, that is, the sum of the troughs and
double-descents of~$\sigma$. The following formula can be
obtained by means of a simple counting:
$$
\dbv=(a\tir cb)+(cb\tir a)+(ba).\leqno(8.1)
$$
It follows from (7.9) that ``mak" can also be expressed as
$$
\mak=\dbv+(b\tir ca).\leqno(8.2)
$$
Another statistic~$S$ will be used for technical reasons. It is
defined by
$$
S:=\dbv+(b\tir ca)+(ba)+L-n=\mak+(ba)+L-n.\leqno(8.3)
$$
Statement (iv) of Theorem~1.1, that was proved at the end of
Section~6, has two consequences, essential for the subsequent
derivation:
$$\displaylines{\rlap{(8.4)}\hfill
\des\Phi(\sigma)=\des\sigma
\quad ({\rm or}\ (ba)\Phi(\sigma)=(ba)\sigma);\hfill\cr
\rlap{(8.5)}\hfill
\dbv\Phi(\sigma)=\dbv\sigma.\hfill\cr}
$$

\proclaim Theorem 8.1. The transformation
$\bfr\,\Phi^{-1}\,\bfr\,\Phi$ is a bijection of 
${\cal S}_n$ onto itself having the property that
$$
(\des,S_1)(\bfr\,\Phi^{-1}\,\bfr\,\Phi)(\sigma)
=(\des,\mak)\,\sigma \leqno(8.6)
$$
holds for each permutation~$\sigma$.

\proclaim Theorem 8.2. The transformation
$\bfr\,\bfc\,\Phi\,\bfr\,\bfc$ is a bijection of 
${\cal S}_n$ onto itself having the property that
$$
(\des,S_3)(\bfr\,\bfc\,\Phi\,\bfr\,\bfc)(\sigma)
=(\des,\mak)\,\sigma \leqno(8.7)
$$
holds for each permutation~$\sigma$.

The first step in the proof of Theorem 8.1 is to establish the
following identity
$$
\mak \bfr\,\Phi(\sigma)-\mak
\bfr\,\sigma=\Last\sigma+\First\sigma -\First\Phi(\sigma)+\des
\Phi(\sigma)-n,\leqno(8.8)
$$
for each $\sigma\in {\cal S}_n$. 

\goodbreak
\medskip
By definition of ``mak" we get
$$
\mak\bfr=(bc\tir a)+(ac\tir b)+(a\tir bc)+(ab).
$$
Let $T_1:=(a\tir bc)+(bc\tir a)+(ab)$
and $T_2:=(b\tir ac)+(ac\tir b)$, so that
$\mak\bfr=T_1+T_2-(b\tir ac)$. Let us evaluate
$T_1\,\sigma$, $T_2\,\sigma$ in terms of the factors of the {\it
peak factorization} 
$$0h_0\mid p_1d_1t_1h_1\mid p_2d_2t_2h_2\mid\;\ldots \;
\mid p_rd_rt_rh_r
$$
of~$0\sigma$ introduced in (4.1). When
$\sigma''=\Phi(\sigma)$, let us also calculate 
$T_1\,\sigma''$, $T_2\,\sigma''$, in terms of the {\it trough
factorization} 
$$
h_0''p_0''d_0''\mid t_1''h_1''p_1''d_1''\mid
t_2''h_2''p_2''d_2''\mid\;\ldots
\;\mid t_s''h_s''p_s''d_s'',
$$ 
of $\sigma''$ introduced in \S\kern2pt 5. We have added a double
prime to all the factors to avoid any confusion with the
factorization of~$\sigma$. As $\theta(\sigma)$ is a
rearrangement of the oiseau-word $\bfd\,\sigma$
and $\sigma''=\bfD^{-1}\theta\,\bfd\,\sigma$, we have
$$
\theta({\bfd}\,\sigma)={\bfD}\,\sigma''
=(\infty0h'_0)(p_{i_1}d_{i_1}t_{i_1}h'_{i_1})
\ldots(p_{i_r}d_{i_r}t_{i_r}h'_{i_r}),\leqno(8.9)
$$
where, as seen in (4.3), the word $h'_0h'_1h'_2\ldots h'_r$ (and
also $h'_0h'_{i_1}h'_{i_2}\ldots h'_{i_r}$) is a rearrangement of
$h_0h_1h_2\ldots h_r$.

If $x_i<x_{i+1}$ holds in the permutation
$\sigma=x_1x_2\ldots x_n$, then $x_i$ is either a trough or a
double-rise. The contribution of~$x_i$ to~$T_1\,\sigma$
is equal to~$x_i$ if $i\le n-1$ and~0 if $i=n$. As, by
convention, $x_n$ is either a trough or a double-rise, we get:
$$
T_1\,\sigma=\sum_{i=0}^r \tot h_i
+\sum_{i=1}^r t_i-\Last\sigma.
$$
The same investigation of the contribution of each factor
$h_ip_{i+1}$ to
$T_2\,\sigma$ leads to the evaluation
$$\eqalign{
{T}_2\,\sigma&=
(p_1-\First\sigma-|h_0|)
+\sum_{i=2}^{r}(p_i-t_{i-1}-|h_{i-1}|-1)
+(\Last\sigma-t_r-|h_r|)\cr
&=
\sum_{i=1}^rp_i-\sum_{i=1}^rt_i-\sum_{i=0}^r|h_i|
+\Last\sigma-\First\sigma-(r-1),\cr}
$$
so that
$$
({T}_1+{T}_2)\sigma
=\sum_{i=1}^rp_i+\sum_{i=0}^r\tot
h_i-\sum_{i=0}^r|h_i|-\First\sigma-r+1.\leqno (8.10)
$$
In the same manner,
$$\leqalignno{
{T}_1\,\sigma''&=\sum_{i=0}^s\tot h_i''+
\sum_{i=1}^{s}t_i''\,;\cr
T_2\,\sigma''&=
(p_0''-\First\sigma''-|h''_0|)
+\sum_{i=1}^{s}(p''_i-t''_{i}-|h''_{i}|-1)\cr
&=\sum_{i=0}^sp_i''-\sum_{i=1}^{s}t_i''
-\sum_{i=0}^s|h_i''|-\First\sigma''-s.\cr
\noalign{\hbox{Hence}}
({T}_1+{T}_2)\sigma''
&=\sum_{i=0}^sp_i''
+\sum_{i=0}^s\tot h_i''
-\sum_{i=0}^s|h_i''|-\First\sigma''-s.&(8.11)\cr}
$$
To pursue the calculation of $(T_1+T_2)\sigma''$ we have to take
the steps $(4')$ and $(4'')$ in the construction of~$\bfD$,
described in Section~5, into account. In case $(4')$
$$\leqalignno{
{\bfD}\,\sigma'&=(\infty0h''_0p_0'')
(p''_{1}\overline{d''_{1}}t_1''h''_{1})
\ldots (p''_{s}\overline{d''_{s}}t''_{s}h''_{s}),\cr
\noalign{\hbox{so that, by comparison with (8.9),}}
({T}_1+{T}_2)\sigma''&=\sum_{i=1}^rp_i
+\sum_{i=0}^r\tot h'_i
-(\sum_{i=0}^r|h'_i|-1)-\First\sigma''-r\cr
&=\sum_{i=1}^rp_i
+\sum_{i=0}^r\tot h_i
-\sum_{i=0}^r|h_i|-\First\sigma''-r+1.&(8.12)\cr}
$$
In case $(4'')$
$$\bfD\,\sigma''=(\infty0(h'_0)'')(p''_{0}
((\overline{d'_{0}})''t_0''(h''_{0})'')
(p''_{1}\overline{d''_{1}}t_1''h''_{1})\cdots
(p''_{s}\overline{d''_{s}}t''_{s}h''_{s}).
$$
By comparison with (8.9)
$$\leqalignno{
({T}_1+{T}_2)\sigma''&=
\sum_{i=1}^rp_i
+\sum_{i=0}^r\tot h'_i
-\sum_{i=0}^r|h'_i|-\First\sigma'-(r-1)\cr
&=\sum_{i=1}^rp_i
+\sum_{i=0}^r\tot h_i
-\sum_{i=0}^r|h_i|-\First\sigma'-r+1.&(8.13)\cr
}
$$
Thus, the two expressions for $({T}_1+{T}_2)\sigma''$ in (8.12)
and (8.13) coincide and
$$
(T_1+T_2)\sigma''-(T_1+T_2)\sigma
=\First \sigma-\First\sigma''.\leqno(8.14)
$$
As $\mak\bfr=T_1+T_2-(b\tir ac)$, identity (8.3) will be proved
if we show that
$$
{}-(b\tir ac)\sigma''+(b\tir ac)\sigma
=\Last\sigma+\des\sigma''-n.
$$
To do so we make use of the identity
$$
(b\tir ac)=(b\tir ca)+(ba)+\Last{}-n,\leqno(8.15)
$$
that is straightforward to prove by induction, and of (1.1) that
rewrites
$$
(b\tir ca)\sigma''=(b\tir ca)\sigma+n-\Last \sigma''-\des\sigma''.
$$
Because $(ba)\sigma''=(ba)\sigma$ by (8.4), we get:
$$\leqalignno{
{}-(b\tir ac)\sigma''+(b\tir ac)\sigma
&=-(b\tir ca)\sigma''
+(b\tir ca)\sigma-\Last\sigma''+\Last\sigma\cr
&=-(b\tir ca)\sigma-n+\Last \sigma''+\des\sigma''\cr
&\kern3cm{}+(b\tir ca)\sigma-\Last\sigma''+\Last\sigma\cr
&=\Last\sigma+\des\sigma''-n.\qed\cr}
$$

\proclaim Lemma 8.3. The two identities hold:
$S\,\Phi=\mak$ and $S_1\,\bfr=S\,\bfr\,\Phi$.

{\it Proof}.\quad
We have:
$$
\eqalignno{
S\,\Phi&=\dbv\Phi+(b\tir ca)\Phi+(ba)\Phi-n
+\Last\Phi&\hbox{[by (8.3)]}\cr
&=\dbv+(b\tir ca)\Phi+(ba)\Phi-n
+\Last\Phi&\hbox{[by (8.5)]}\cr
&=\dbv+\bigl((b\tir ca)+n-\Last\Phi-(ba)\Phi\bigr)+(ba)\Phi-n
+\Last\Phi\qquad\quad&\hbox{[by (1.1)]}\cr
&=\dbv+(b\tir ca)=\mak.&\hbox{[by (8.2)]}\cr}
$$
On the other hand, the statistic $S_1$ can be rewritten as:
$$
S_1=\mak+\First+\Last-n-1.\leqno(8.16)
$$
Hence, as $\des\bfr=n-1-\des$ and $\Last\bfr=\First$,
we have:
$$
\eqalignno{
S\,\bfr\,\Phi&=\mak\bfr\,\Phi+\des\bfr\,\Phi+\Last\bfr\,\Phi-n
&\hbox{[by (8.3)]}\cr
&=\bigl(\mak\bfr+\Last{}+\First{}-\First\Phi+\des\Phi-n\bigr)\cr
&\kern2cm{}+(n-1-\des\Phi)+\First\Phi-n&\hbox{[by (8.8)]}\cr
&=\mak\bfr+\First\bfr+\Last\bfr-n-1
=S_1\,\bfr.\qed\cr}
$$

It follows from Lemma 8.3 that
$S_1\,\bfr\,\Phi^{-1}\,\bfr=S$, so that
$S_1\,\bfr\,\Phi^{-1}\,\bfr\,\Phi=S\,\Phi=\mak$.
Also $\des\bfr\,\Phi^{-1}\,\bfr\,\Phi=\des$, by (8.4) and
the fact that~$\bfr$ occurs twice in the expression of the
transformation
$\bfr\,\Phi^{-1}\,\bfr\,\Phi$. This achieves the proof of
Theorem~8.1.

\medskip
The proof of Theorem 8.2 is much simpler. It is based upon the
straightforward identities:
$$
\des\bfr\,\bfc=\des\quad
{\rm and}\quad
\mak\bfr\,\bfc=n\,\des-\mak.\leqno(8.17)
$$
First, 
$$\eqalignno{
\des \bfr\,\bfc\,\Phi\,\bfr\,\bfc&=\des \bfr\,\bfc\,\Phi
\qquad\qquad &\hbox{[by (8.17)]}\cr
&=\des \bfr\,\bfc&\hbox{[by (8.4)]}\cr
&=\des.&\hbox{[by (8.17)]}\cr}
$$
Then, notice that
the statistic $S_3$ is also equal to
$$
S_3=\mak-\des+\First{}-1.\leqno(8.18)
$$
Hence
$$\eqalignno{
S_3\,\bfr\,\bfc\,\Phi
&=\mak\bfr\,\bfc\,\Phi-\des\bfr\,\bfc\,\Phi
+\First\bfr\,\bfc\,\Phi-1&\hbox{[by (8.18)]}\cr
&=\bigl(n\,\des\Phi-\mak\Phi\bigr)-\des\Phi+\bigl(n+1-\Last\Phi\bigr)-1
\qquad\quad&\hbox{[by (8.17)]}\cr
&=n\,\des-\bigl(\mak\Phi+\des\Phi+\Last\Phi-n\bigr)\cr
&=n\,\des-S\,\Phi&\hbox{[by (8.3)]}\cr
&=n\,\des-\mak&\hbox{[by Lemma 8.3]}\cr
&=\mak\bfr\,\bfc.&\hbox{[by (8.17)]}\cr}
$$
Thus $S_3\,\bfr\,\bfc\,\Phi\,\bfr\,\bfc=\mak$. This achieves the
proof of Theorem 8.2.

\bigskip
\centerline{\bf 9. The other statistics
$S_2$ and $S_4$}

\medskip
Those statistics will be compared with the major index ``maj" that
reads $\maj=(a\tir cb)+(b\tir ca)+(c\tir ba)+(ba)$.
First,
$$S_2-\maj=(b\tir ac)-(b\tir ca)+[b\tir a)-(ba).$$
As
$(b\tir ac)+(b\tir a]=(b\tir ca)+(ba)$,
we have
$
S_2-\maj
=[b\tir a)-(b\tir a]
$.
Also
$
S_4-\maj=(b\tir a)-(ba)$.

With each permutation $\sigma=x_1x_2\ldots x_n$
associate $\sigma'=x_1'x_2'\ldots x_n'$, \qquad where
$x_i'-x_i\equiv n+1-x_n-x_1\pmod{n}.$
Then, $\sigma\mapsto \sigma'$ is an {\it involution}, for
$(x_i')'\equiv x'_i+ n+1-x'_n-x'_1
\equiv (x_i+n+1-x_n-x_1)+n+1-(x_n+n+1-x_n-x_1)
-(x_n+n+1-x_n-x_1)
\equiv x_i$.
Moreover, $\des \sigma'=\des \sigma$ and
$$\leqalignno{
\maj \sigma'&=\maj \sigma+x_1+x_n-n-1\cr
&=\maj\sigma+[b\tir a)\sigma-(b\tir a]\sigma
=S_2\,\sigma.\cr}
$$
This shows that $(\des,S_2)$ is equidistributed with
$(\des,\maj)$.

What about $S_4$? We have
$S_4\,\sigma=\maj\sigma+(b\tir a)\sigma-(ba)\sigma=\maj
\sigma+x_1-1-\des\sigma$. Consider the transformation that
maps the permutation $\sigma=x_1x_2\ldots x_n$ onto
$\overline \sigma=\overline x_1\overline x_2\ldots
\overline x_n$, where $\overline x_n:=n+1-x_1$ and
$$\overline x_i\equiv x_{i+1}-x_1\pmod{(n+1)}\quad
(i=1,2,\ldots,n-1).$$
The map $\sigma\mapsto \sigma'$ not involutive,
but is a bijection of ${\cal S}_n$ onto itself
and
$$\leqalignno{
\des \overline \sigma&=\des \sigma;\cr
\maj \overline \sigma&=\maj \sigma+x_1-1-\des \sigma
=S_4\,\sigma.\cr}
$$
Again $(\des,S_4)$ is another bistatistic equidistributed with
$(\des,\maj)$. Thus, Conjecture~11 is correct.

\goodbreak
{\it Acknowledgements}.\ 
The authors thank Einar Steingr\'\i msson
for his careful and knowledgeable reading of the paper.


\vglue2cm


\centerline{\bf References}
 
\bigskip
[BaSt00] Eric Babson and Einar Steingr\'\i msson,
Generalized permutation patterns and a classification
of the Mahonian statistics, {\sl S\'em. Loth. Comb. }
[{\tt http://mat.univie.ac.at/$\sim$slc/}]
{\bf 44 }, {\oldstyle 2000}, B44b, 18~pp.

[Ca54] Leo Carlitz, $q$-Bernoulli and
Eulerian numbers,{\sl Trans. Amer. Math. Soc.},
{\bf 76}, {\oldstyle 1954}, 332--350.

[Ca59] Leo Carlitz, Eulerian numbers and polynomials, {\sl Math.
Magazine}, {\bf 33}, {\oldstyle 1959}, 247--260.

[CaFo69] Pierre Cartier and
Dominique Foata, {\sl Probl\`emes combinatoires de permutations
et r\'earrangements}. Berlin, Springer-Verlag, {\oldstyle 1969} ({\sl
Lecture Notes in Math., {\bf 85}}).

[ClFo95] Robert J. Clarke and Dominique Foata,
Eulerian Calculus, II: An Extension
of Han's Fundamental Transformation,
{\sl Europ. J. Combinatorics}, {\bf 16}, {\oldstyle 1995},
221--252. 

[Du04] G\'erard Duchamp, Oral communication, {\oldstyle 2004}.

[FoZe90] Dominique Foata and Doron Zeilberger,
Denert's Permutation Statistic Is Indeed Euler-Mahonian,
{\sl Studies in Appl. Math.}, {\bf 83}, {\oldstyle 1990}, 31--59.

[Ha94] Guo-Niu Han, Une transformation fondamentale sur les
r\'earrangements de mots, {\sl Advances in Math.}, {\bf 105},
{\oldstyle 1994}, 26--41.

[Ma15] Percy Alexander MacMahon, {\sl Combinatory
Analysis,} {\rm vol.~1 and~2}. Cambridge, Cambridge Univ. Press,
{\oldstyle 1915} (Reprinted by Chelsea, New York,
{\oldstyle 1955}).


\bigskip\bigskip
\hbox{\vtop{\halign{#\hfil\cr
Dominique Foata \cr
Institut Lothaire\cr
1, rue Murner\cr
F-67000 Strasbourg, France\cr
\noalign{\smallskip}
{\tt foata@math.u-strasbg.fr}\cr}}
\qquad
\vtop{\halign{#\hfil\cr
Arthur Randrianarivony\cr
Facult\'e des Sciences\cr
Universit\'e d'Antananarivo\cr
Antananarivo, Madagascar\cr
\noalign{\smallskip}
{\tt arthur@univ-antananarivo.mg}\cr}}
}

\bye



\bye
 
 
 