

%%%%%%%%%%%%%%%%%%%%%
%% TeX plain file for the paper entitled
%% Une nouvelle transformation pour les 
%% statistiques Euler-mahoniennes ensemblistes
%% by Dominique Foata and Guo-Niu Han
%% An output of 24  pages
%%%%%%%%%%%%%%%%%%%%%

\catcode'32=9
\magnification=1200

\voffset=1cm
\hoffset=0cm
\font\tenpc=cmcsc10

% Charge des fontes de 8 et 6 points :
\font\eightrm=cmr8
\font\eighti=cmmi8
\font\eightsy=cmsy8
\font\eightbf=cmbx8
\font\eighttt=cmtt8
\font\eightit=cmti8
\font\eightsl=cmsl8
\font\sixrm=cmr6
\font\sixi=cmmi6
\font\sixsy=cmsy6
\font\sixbf=cmbx6

\skewchar\eighti='177 \skewchar\sixi='177
\skewchar\eightsy='60 \skewchar\sixsy='60

% Chargement des fontes AMS

\font\tengoth=eufm10
\font\tenbboard=msbm10
\font\eightgoth=eufm10 at 8pt
\font\eightbboard=msbm7 at 8pt
\font\sevengoth=eufm7
\font\sevenbboard=msbm7
\font\sixgoth=eufm7 at 6pt
\font\fivegoth=eufm7 at 5pt

\newfam\gothfam
\newfam\bboardfam

\catcode`\@=11

\def\raggedbottom{\topskip 10pt plus 36pt
\r@ggedbottomtrue}
\def\pc#1#2|{{\bigf@ntpc #1\penalty
\@MM\hskip\z@skip\smallf@ntpc #2}}

\def\tenpoint{%
  \textfont0=\tenrm \scriptfont0=\sevenrm \scriptscriptfont0=\fiverm
  \def\rm{\fam\z@\tenrm}%
  \textfont1=\teni \scriptfont1=\seveni \scriptscriptfont1=\fivei
  \def\oldstyle{\fam\@ne\teni}%
  \textfont2=\tensy \scriptfont2=\sevensy \scriptscriptfont2=\fivesy
  \textfont\gothfam=\tengoth \scriptfont\gothfam=\sevengoth
  \scriptscriptfont\gothfam=\fivegoth
  \def\goth{\fam\gothfam\tengoth}%
  \textfont\bboardfam=\tenbboard \scriptfont\bboardfam=\sevenbboard
  \scriptscriptfont\bboardfam=\sevenbboard
  \def\bboard{\fam\bboardfam}%
  \textfont\itfam=\tenit
  \def\it{\fam\itfam\tenit}%
  \textfont\slfam=\tensl
  \def\sl{\fam\slfam\tensl}%
  \textfont\bffam=\tenbf \scriptfont\bffam=\sevenbf
  \scriptscriptfont\bffam=\fivebf
  \def\bf{\fam\bffam\tenbf}%
  \textfont\ttfam=\tentt
  \def\tt{\fam\ttfam\tentt}%
  \abovedisplayskip=12pt plus 3pt minus 9pt
  \abovedisplayshortskip=0pt plus 3pt
  \belowdisplayskip=12pt plus 3pt minus 9pt
  \belowdisplayshortskip=7pt plus 3pt minus 4pt
  \smallskipamount=3pt plus 1pt minus 1pt
  \medskipamount=6pt plus 2pt minus 2pt
  \bigskipamount=12pt plus 4pt minus 4pt
  \normalbaselineskip=12pt
  \setbox\strutbox=\hbox{\vrule height8.5pt depth3.5pt width0pt}%
  \let\bigf@ntpc=\tenrm \let\smallf@ntpc=\sevenrm
  \let\petcap=\tenpc
  \normalbaselines\rm}
\def\eightpoint{%
  \textfont0=\eightrm \scriptfont0=\sixrm \scriptscriptfont0=\fiverm
  \def\rm{\fam\z@\eightrm}%
  \textfont1=\eighti \scriptfont1=\sixi \scriptscriptfont1=\fivei
  \def\oldstyle{\fam\@ne\eighti}%
  \textfont2=\eightsy \scriptfont2=\sixsy \scriptscriptfont2=\fivesy
  \textfont\gothfam=\eightgoth \scriptfont\gothfam=\sixgoth
  \scriptscriptfont\gothfam=\fivegoth
  \def\goth{\fam\gothfam\eightgoth}%
  \textfont\bboardfam=\eightbboard \scriptfont\bboardfam=\sevenbboard
  \scriptscriptfont\bboardfam=\sevenbboard
  \def\bboard{\fam\bboardfam}%
  \textfont\itfam=\eightit
  \def\it{\fam\itfam\eightit}%
  \textfont\slfam=\eightsl
  \def\sl{\fam\slfam\eightsl}%
  \textfont\bffam=\eightbf \scriptfont\bffam=\sixbf
  \scriptscriptfont\bffam=\fivebf
  \def\bf{\fam\bffam\eightbf}%
  \textfont\ttfam=\eighttt
  \def\tt{\fam\ttfam\eighttt}%
  \abovedisplayskip=9pt plus 2pt minus 6pt
  \abovedisplayshortskip=0pt plus 2pt
  \belowdisplayskip=9pt plus 2pt minus 6pt
  \belowdisplayshortskip=5pt plus 2pt minus 3pt
  \smallskipamount=2pt plus 1pt minus 1pt
  \medskipamount=4pt plus 2pt minus 1pt
  \bigskipamount=9pt plus 3pt minus 3pt
  \normalbaselineskip=9pt
  \setbox\strutbox=\hbox{\vrule height7pt depth2pt width0pt}%
  \let\bigf@ntpc=\eightrm \let\smallf@ntpc=\sixrm
  \normalbaselines\rm}

\let\bb=\bboard

\tenpoint

% dactylographie fran�aise

\catcode`\;=\active
\def;{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern\fontdimen2 \font\kern -1.2 \fontdimen3 \font\fi\string;}

\catcode`\:=\active
\def:{\relax\ifhmode\ifdim\lastskip>\z@\unskip\fi\penalty\@M\ \fi\string:}

\catcode`\!=\active
\def!{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern\fontdimen2 \font \kern -1.1 \fontdimen3 \font\fi\string!}

\catcode`\?=\active
\def?{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern\fontdimen2 \font \kern -1.1 \fontdimen3 \font\fi\string?}

\def\^#1{\if#1i{\accent"5E\i}\else{\accent"5E #1}\fi}
\def\"#1{\if#1i{\accent"7F\i}\else{\accent"7F #1}\fi}

\frenchspacing

% format de sortie


\newif\ifpagetitre
\newtoks\auteurcourant \auteurcourant={\hfil}
\newtoks\titrecourant \titrecourant={\hfil}

\def\appeln@te{}
\def\vfootnote#1{\def\@parameter{#1}\insert\footins\bgroup\eightpoint
  \interlinepenalty\interfootnotelinepenalty
  \splittopskip\ht\strutbox % top baseline for broken footnotes
  \splitmaxdepth\dp\strutbox \floatingpenalty\@MM
  \leftskip\z@skip \rightskip\z@skip
  \ifx\appeln@te\@parameter\indent \else{\noindent #1\ }\fi
  \footstrut\futurelet\next\fo@t}

\pretolerance=500 \tolerance=1000 \brokenpenalty=5000
\newdimen\hmargehaute \hmargehaute=0cm
\newdimen\lpage \lpage=13.3cm
\newdimen\hpage \hpage=20cm
\newdimen\lmargeext \lmargeext=1cm
\hsize=11.25cm
\vsize=18cm
\parskip 0pt
\parindent=12pt

\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{\eightpoint\hfil\the\auteurcourant\hfil}
\def\rightheadline{\eightpoint\hfil\the\titrecourant\hfil}
\def\titleheadline{\hfill}
\pagetitretrue

\def\footnoterule{\kern-6\p@
  \hrule width 2truein \kern 5.6\p@} % the \hrule is .4pt high



\let\rmpc=\sevenrm
\def\pd#1#2 {\pc#1#2| }

\def\pointir{\discretionary{.}{}{.\kern.35em---\kern.7em}\nobreak
\hskip 0em plus .3em minus .4em }

\def\resume#1{\vbox{\eightpoint \pc R\'ESUM\'E|\pointir #1}}
\def\abstract#1{\vbox{\eightpoint \pc ABSTRACT|\pointir #1}}

\def\titre#1|{\message{#1}
              \par\vskip 30pt plus 24pt minus 3pt\penalty -1000
              \vskip 0pt plus -24pt minus 3pt\penalty -1000
              \centerline{\bf #1}
              \vskip 5pt
              \penalty 10000 }

\def\section#1|{\par\vskip .3cm
                {\bf #1}\pointir}

\def\ssection#1|{\par\vskip .2cm
                {\it #1}\pointir}

\long\def\th#1|#2\finth{\par\medskip
              {\petcap #1\pointir}{\it #2}\par\smallskip}

\long\def\tha#1|#2\fintha{\par\medskip
                    {\petcap #1.}\par\nobreak{\it #2}\par\smallskip}
\def\cf{{\it cf}}

\def\rem#1|{\par\medskip
            {{\it #1}\pointir}}

\def\rema#1|{\par\medskip
             {{\it #1.}\par\nobreak }}

%
\def\ieme{\raise 1ex\hbox{\pc{}i\`eme|}}
\def\omini{\raise 1ex\hbox{\pc{}o|}}
\def\emini{\raise 1ex\hbox{\pc{}e|}}
\def\ermini{\raise 1ex\hbox{\pc{}er|}}
\def\remini{\raise 1ex\hbox{\pc{}re|}}

%reference pour un article :

\def\article#1|#2|#3|#4|#5|#6|#7|
    {{\leftskip=7mm\noindent
     \hangindent=2mm\hangafter=1
     \llap{[#1]\hskip.35em}{#2}\pointir
     #3, {\sl #4}, vol.\nobreak\ {\bf #5}, {\oldstyle #6},
     p.\nobreak\ #7.\par}}
%reference pour un livre :
\def\livre#1|#2|#3|#4|
    {{\leftskip=7mm\noindent
    \hangindent=2mm\hangafter=1
    \llap{[#1]\hskip.35em}{#2}\pointir
    {\sl #3}\pointir #4.\par}}
%reference complementaire :
\def\divers#1|#2|#3|
    {{\leftskip=7mm\noindent
    \hangindent=2mm\hangafter=1
     \llap{[#1]\hskip.35em}{#2}\pointir
     #3.\par}}
%
\mathchardef\conj="0365
\def\dem{\par{\it D\'emonstration}\pointir}
\def\qed{\quad\raise -2pt\hbox{\vrule\vbox to 10pt{\hrule width 4pt
\vfill\hrule}\vrule}}

\def\virg{\raise 2pt\hbox{,}}   % virgule apr\`es une fraction

\def\cqfd{\penalty 500 \hbox{\qed}\par\smallskip}

\long\def\entourer#1{\hbox{\vrule\vbox{\hrule\hbox{\kern15pt\vbox{\kern5pt
{#1}\kern5pt}\kern15pt}\hrule}\vrule}}
\def\\S {\vskip 5pt\hskip .5cm plus .1cm minus .1cm\relax}

%les differents retraits, voir aussi \item
\def\enonce#1|#2\finenonce{{\par\leftskip=36pt
\noindent\hbox to 0pt{\kern-\leftskip#1\hfill}{#2}\par}}

\def\senonce#1|#2\finsenonce{{\par\leftskip=36pt
\noindent\hbox to 0pt{\kern-24pt #1\hfill}{#2}\par}}

\def\ssenonce#1|#2\finssenonce{{\par\leftskip=48pt
\noindent\hbox to 0pt{\kern-24pt #1\hfill}{#2}\par}}

\def\decale#1|{\par\noindent\hskip 28pt\llap{#1}\kern 5pt}
\def\decaledecale#1|{\par\noindent\hskip 34pt\llap{#1}\kern 5pt}
% pour les titres en deux lignes et les sections sans point-tiret :
\def\titrea#1|#2|{\message{#1 #2}
  \par\vskip.5cm plus .1cm minus .1cm\penalty -1000
  \centerline{\bf #1}
  \centerline{\bf #2}
  \vskip 5pt
  \penalty 10000 }
\def\sectiona#1|{\par\vskip .3cm
  {\bf #1.}
  \par\nobreak\vskip 3pt }
\def\ssectiona#1|{\par\vskip .2cm
  {\it #1.}
  \par\nobreak\vskip 2pt }

\def\rest#1{\ifinner\setbox1=\hbox{$\textstyle{#1}$}
            \else\setbox1=\hbox{$\displaystyle{#1}$}\fi
            \dimen1=\ht1
            \advance\dimen1 by\dp1
            \divide\dimen1 by 2
            \box1\lower 2pt\hbox{$\left|\vbox to\dimen1{}\right.$}}


\def\matrice#1{\null \,\vcenter {\normalbaselines \m@th
\ialign {\hfil $##$\hfil &&\  \hfil $##$\hfil\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip } #1\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip }}}\,}

\def\petitematrice#1{\null \,\vcenter {\normalbaselines \m@th
\ialign {\hfil $##$\hfil &&\thinspace  \hfil $##$\hfil\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip } #1\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip }}}\,}


\catcode`\@=12

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

\def\inv{\mathop{\rm inv}}
\def\maj{\mathop{\rm maj}}
\def\des{\mathop{\rm des}}
\def\imaj{\mathop{\rm imaj}}
\def\ides{\mathop{\rm ides}}
\def\inverse{\mathop{\bf i}}
\def\red{\mathop{\hbox{\rm r\'ed}}\nolimits}

\def\Rise{\mathop{\rm Rise}}
\def\Majcode{\mathop{\rm Majcode}\nolimits}
\def\Invcode{\mathop{\rm Invcode}\nolimits}
\def\Ligne{\mathop{\rm Ligne}}
\def\Iligne{\mathop{\rm Iligne}}
\def\Sub{\mathop{\rm Sub}\nolimits}
\def\st{\mathop{\rm st}}
\def\Stat{\mathop{\rm Stat}}
\def\tot{\mathop{\rm tot}}
\def\SE{\mathop{\rm SE}}
\def\eul {\mathop{\rm eul}}
\def\Eul {\mathop{\rm Eul}}
\def\Last{\mathop{\rm Last}}
\def\haut{\mathop{\rm haut}}
\def\bfi{{\bf i}}
\def\bfj{{\bf j}}
\def\bfl{{\bf l}}
\def\bfL{{\bf L}}
\def\bfE{{\bf E}}
\def\bfF{{\bf F}}
\def\bfk{{\bf k}}
\frenchspacing

\auteurcourant={DOMINIQUE FOATA ET GUO-NIU HAN}
\titrecourant={TRANSFORMATION POUR STATISTIQUES ENSEMBLISTES}
\vglue 1cm
\centerline{\bf UNE NOUVELLE TRANSFORMATION POUR LES}
\smallskip
\centerline{\bf STATISTIQUES EULER-MAHONIENNES ENSEMBLISTES}
\bigskip
\centerline{\sl Dominique Foata et Guo-Niu Han \footnote{$(^*)$}{Ce travail de recherche a pu
\^etre effectu\'e gr\^ace au soutien financier
du contrat europ\'een ``Algebraic Combinatorics", no. RTN2-2001-00059.}}

\bigskip\medskip

{\eightpoint

\leftline{\indent\indent EN HOMMAGE \`A PIERRE CARTIER,}
\rightline{POLYMATH,
LOTHARINGIEN D'HONNEUR\hskip24pt}

}
\bigskip\
{\eightpoint
\narrower\narrower

\noindent
{\bf Abstract}.\quad 
The construction of a bijection of the symmetric group onto itself is
given that has the property of mapping a pair of set-statistics onto
another pair. As a consequence, it is shown that a pair of
Euler-mahonian statistics has a symmetric distribution.

\bigskip

\noindent
{\bf R\'esum\'e}.\quad
On donne la construction d'une bijection du groupe sym\'e\-trique sur
lui-m\^eme, qui a la propri\'et\'e d'envoyer un couple de statistiques
ensemblistes sur un autre couple. Comme cons\'equence, on montre qu'un
couple de statistiques Euler-mahoniennes a une distribution
sym\'etrique.

}

\bigskip\bigskip
\centerline{\bf Avant-propos}

\medskip\noindent
Nous sommes heureux de d\'edier le pr\'esent article de Combinatoire \`a
Pierre Cartier, qui, d\`es les ann\'ees soixante, a attir\'e l'attention de la
com\-mu\-naut\'e math\'ematique sur la renaissance de cette discipline ;
t\'emoin~son expos\'e de 1962 au S\'eminaire Bourbaki (\cf. [Ca62]) sur
l'identit\'e exponentielle de Spitzer [Sp56] et ses applications aux
fluctuations de sommes de varia\-bles al\'eatoires. Tout au long de sa
carri\`ere, il est rest\'e attentif \`a tous les d\'eveloppements importants
(\cf. [Ca80, Ca82, Ca91]), en particulier au renouveau de l'\'etude des
fonctions sym\'etriques initialis\'e par Sch\"utzenberger [Sc77] et \`a la
r\'evolution philosophique que constitue la d\'emonstration ``automatique"
des identit\'es hyperg\'eom\'etriques due \`a  Zeilberger [Ze90]. Il a
lui-m\^eme contribu\'e \`a cette discipline dans plusieurs travaux (\cf.
[CaFo69, Ca72, Ca90, Ca00]). Notons enfin que le m\'emoire sur les
commutations [CaFo69] a donn\'e un cadre math\'ematique utile aux
probl\`emes de paral\-l\'elisme (\cf. Diekert [Di90]) et a fourni une version
non-commutative \`a l'identit\'e fondamentale du polyn\^ome chromatique
[St73] (\cf. Lass [La01]).

\medskip
La construction donn\'ee ci-dessous d'une nouvelle transformation sur le
groupe sym\'etrique s'inscrit dans ce cadre de recherche, o\`u les propri\'et\'es
des statistiques d\'efinies sur ce groupe (comme le nombre de des\-centes,
la longueur, l'indice majeur, \dots\thinspace) sont
syst\'ematiquement explor\'ees et \'etendues \`a certains groupes de Coxeter (\cf.
[AR01, ABR01, Br94, FH97, Re93a, Re93b, Re93c, Re95a, Re95b, StE93, St76,
StJ92]). Il s'agit, en particulier, de trouver les expressions analytiques des
s\'eries g\'en\'eratrices de ces statistiques ; si on ne peut le faire directement,
il s'agit alors  de construire des bijections sur ces groupes qui permettent
de ramener le calcul \`a des cas classiques connus. Chemin faisant, la
construction de ces bijections fait appara\^\i tre des propri\'et\'es nouvelles
sur ces groupes.

\bigskip
\centerline{\bf 1. Introduction}

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

\medskip
Appelons {\it ligne de route}
d'une permutation $\sigma=\sigma(1)\sigma(2)\ldots
\sigma(n)$ (\'ecrite comme un mot en les lettres $1,2,\ldots,n$),  l'{\it
ensem\-ble}, not\'e $\Ligne \sigma$, de tous les entiers~$i$ tels que $1\le
i\le n-1$ et $\sigma(i)>\sigma(i+1)$. [Certains auteurs parlent d'{\it
ensemble de descentes} (``descent set") et adoptent la notation $D(\sigma)$ ou
$\hbox{\eightrm DES}\,\sigma)$ (\cf. [AR01, Br94, Re95a, Re95b]).] La
{\it somme des \'el\'ements} de $\Ligne\sigma$ est not\'ee $\maj\sigma$
(l'{\it indice majeur} de~$\sigma$).

Par ailleurs, la {\it ligne inverse de route},
$\Iligne\sigma$,  de~$\sigma$, est d\'efinie comme l'{\it ensemble} de
toutes les lettres $\sigma(i)$, telles que la lettre \'egale \`a $1+\sigma(i)$
soit {\it \`a la gauche}  de $\sigma(i)$ dans le mot~$\sigma$. Il est
imm\'ediat que la ligne inverse de route de~$\sigma$ n'est autre que la
ligne de route de la permutation inverse $\sigma^{-1}$. 

Rappelons que le {\it codage par inversions} (ou codage de Lehmer)
(\cf. [Le60]),
$\Invcode\sigma$, d'une permutation~$\sigma$ est d\'efini
comme le {\it mot}
$w=x_1x_2\ldots x_n$, de longueur~$n$, tel que pour tout $i=1,2,\ldots,
n$, la lettre~$x_i$ est donn\'ee par
$$\leqalignno{\noalign{\vskip-5pt}
x_i&:=\#\{j:1\le j\le i-1,\,\sigma(j)>\sigma(i)\}.&(1.1)\cr
\noalign{\hbox{Par construction-m\^eme, on a :}}
0&\le x_i\le i-1\qquad(1\le i\le n).&(1.2)\cr}
$$
Un mot $w=x_1x_2\ldots x_n$, dont les lettres sont des entiers satisfaisant
les in\'egalit\'es (1.2) est dit {\it sous-exc\'edent}. On note $\SE_n$
l'ensemble des mots sous-exc\'edents de longueur~$n$. On d\'efinit la {\it
ligne des mont\'ees}, $\Rise w$, d'un mot quelconque (en
particulier d'un mot sous-exc\'edent)
$w=x_1x_2\ldots x_n$, comme l'ensemble des indices~$i$ tels que $1\le i\le
n-1$ et
$x_i<x_{i+1}$.

Il est \'evident que ``$\Invcode$" est une bijection de ${\cal S}_n$ sur
$\SE_n$. Une autre telle bijection est le {\it maj-codage} ``Majcode", que
l'on peut d\'efinir, par r\'ecurrence, de la fa\c con suivante : le
maj-codage de la permutation~1 est~0. Soient $\sigma$ une permutation
d'ordre~$n\ge 2$ et~$\sigma^-$ la permutation d\'eduite de~$\sigma$
par suppression de la lettre~$n$ dans~$\sigma$. Si $x_1x_2\ldots
x_{n-1}$ est le maj-codage de~$\sigma^-$, alors on d\'efinit 
$\Majcode\sigma:=x_1x_2\ldots x_{n-1}x_n$, avec
$x_n:=\maj\sigma-\maj\sigma^-$. Une autre d\'efinition de ``Majcode" par
\'etiquetage est propos\'ee au paragraphe~5. 

Le but de cet article est de d\'emontrer qu'il existe une 
bijection $\phi:\sigma\mapsto \tau$ du groupe
sym\'etrique~${\cal S}_n$ sur lui-m\^eme et surtout de construire une
telle bijection, telle que le diagramme suivant soit commutatif : 
$$\vbox{\offinterlineskip
\centerput(0,0){$w'$}
\fleche(3,0)\dir(1,0)\long{20}
\centerput(26,0){$B$}
\centerput(13,1){$\Rise$}
\fleche(0,-12)\dir(0,1)\long{10}
\centerput(-8,-8){$\Majcode$}
\centerput(32,-8){$\Iligne$}
\fleche(26,-12)\dir(0,1)\long{10}
\centerput(0,-15){$\tau$}
\centerput(26,-15){$\sigma$}
\centerput(13,-12){$\phi$}
\centerput(-22,-12){(1.3)}
\fleche(23,-14)\dir(-1,0)\long{20}
\fleche(0,-16)\dir(0,-1)\long{10}
\fleche(26,-16)\dir(0,-1)\long{10}
\centerput(0,-29){$w$}
\centerput(26,-29){$A$}
\fleche(3,-28)\dir(1,0)\long{20}
\centerput(13,-32){$\Rise$}
\centerput(-7,-22){$\Invcode$}
\centerput(32,-22){$\Ligne$}
\leftput(45,-10){$w,w'\in \SE_n;$}
\leftput(45,-15){$\sigma, \tau \in {\cal S}_n;$}
\leftput(45,-20){$A,B\subset \{1,2,\ldots,n-1\}.$}}\hskip6cm
$$

\vskip3cm
\noindent
On en d\'eduit le r\'esultat suivant.

\proclaim Th\'eor\`eme 1.1. Il existe une bijection $\phi$ qui satisfait :
$$
(\Ligne,\Iligne)\,\sigma=(\Rise\circ\Invcode,\Rise\circ\Majcode)\,
\phi(\sigma).\leqno(1.4)
$$

Le lecteur souhaitant lire tout de suite la construction de la
bijection~$\phi$ est invit\'e \`a se reporter au paragraphe~4, o\`u deux
descriptions en sont donn\'ees. Il doit seulement se rappeler la d\'efinition
de Majcode et, pour chaque entier~$i$ tel que $1\le i\le n$, utiliser la
bijection croissante de $\{1,\ldots,i-1,i+1,\ldots,n\}$ sur
$\{1,2,\ldots, n-1\}$ not\'ee $\red_i$ (``r\'ed" pour
``r\'eduite") et la bijection inverse $\red_i^{-1}$.

En plus des statistiques ``Ligne", ``Iligne" et ``Rise" d\'ej\`a d\'efinies,
intro\-dui\-sons une quatri\`eme statistique {\it ensembliste} ``Eul", dite
{\it valeur Eul\'e\-rienne}, qui associe \`a tout mot sous-exc\'edent
$w=x_1x_2\ldots x_n$ un sous-ensemble, $\Eul w$, de $\{1,2,\ldots,n-1\}$.
Si $n=1$, on pose $\Eul 0:=\emptyset$ ; si $n\ge 2$ et si l'on
pose $w':=x_1x_2\ldots x_{n-1}$, 
de sorte que $w'\in \SE_{n-1}$ et
$w=w'x_n$, on peut poser, par r\'ecurrence,
$\Eul w':=\{y_k<y_{k-1}<\cdots <y_1\}\subset \{1,2,\ldots, n-2\}$.
Notons alors
$\{z_{k+1}<z_{k+2}<\cdots <z_{n-1}=n-1\}$ l'ensemble compl\'ementaire
$\{1,2,\ldots, n-1\}\setminus \Eul w'$. Si $k\ge x_n\ge 0$, on d\'efinit :
$$
\Eul w' x_n:=\{y_k,y_{k-1},\ldots, y_{x_n+1}, y_{x_n}+1,\ldots, 
y_2+1,y_1+1\}.\leqno(1.5)
$$
En particulier $\Eul w'0=\Eul w'$.

Posons, par commodit\'e, $y_{k+1}:=0$ et $y_0:=n$. Si $n-1\ge x_n\ge
k+1$, il existe un entier unique~$p$ tel que $y_{p+1}<z_{x_n}<y_p$. En
particulier, $x_n\ge k+1\ge p+1$. On d\'efinit alors :
$$
\Eul w' x_n:=\{y_k,\ldots, y_{p+1},x_n-p,y_p+1,\ldots, y_1+1\}.
\leqno(1.6)
$$

{\it Exemple}.\quad On a successivement : $\Eul(0,0)=\emptyset$ ;
$\Eul(0,0,1)=\{1\}$ ; $\Eul(0,0,1,0)=\{1\}$ ;
$\Eul(0,0,1,0,3)=\{1,3\}$ ; $\Eul(0,0,1,0,3,1)=\{1,4\}$. 
Avec $w'=0,0,1,0,3,1$, on obtient 
$\Eul w'0=\{1,4\}$ ; $\Eul w'1=\{1,5\}$ ; $\Eul w'2=\{2,5\}$ ;
$\Eul w'3=\{1,2,5\}$ ; $\Eul w'4=\{1,3,5\}$ ;
$\Eul w'5=\{1,4,5\}$ et $\Eul w'6=\{1,4,6\}$.

\medskip

Par d\'efinition-m\^eme du
codage par inversions (\cf., par exemple, [Lo02], Proposition~11.4.2), on a,
pour toute permutation~$\sigma$,
$$\leqalignno{
\Ligne\sigma&=\Rise\circ\Invcode\sigma.&(1.7)\cr
\noalign{\hbox{On peut v\'erifier \'egalement (voir \S\kern 2pt5) que l'on
a :}}
\Ligne\sigma&=\Eul\circ\Majcode\sigma.&(1.8)\cr}
$$

D\'esignons par $\bfi$ la bijection d\'efinie sur~${\cal
S}_n$, qui envoie toute permutation sur son inverse
$\bfi\,\sigma:=\sigma^{-1}$ et formons la cha\^\i ne
$$
\matrix{&\eightpoint\inverse&&\eightpoint\phi&&\eightpoint\Majcode&
&\eightpoint\Invcode^{-1}&\cr
\sigma'&\mapsto&\sigma&\mapsto&\tau&\mapsto&w'&\mapsto&\tau'\cr
{\cal S}_n&&{\cal S}_n&&{\cal S}_n&&\SE_n&&{\cal S}_n\cr}\leqno(1.9)
$$
De (1.4), (1.7) et (1.8), r\'esultent, d'une part, les identit\'es
$$(1.10)\ \matrice{
\Ligne \sigma'&\!=\!
&\Iligne\sigma&\!=\!
&\Rise\circ \Majcode \tau&\!=\!
&
\Rise w'&\!=\!
&\Ligne \tau';\cr
\Iligne\sigma'&\!=\!
&\Ligne \sigma&\!=\!
&\Ligne \tau&\!=\!
&\Eul 
w'&\!=\!
&\Eul\circ\Invcode 
\tau',\cr }
$$
d'autre part, le th\'eor\`eme suivant.

\proclaim Th\'eor\`eme 1.2. 
Les couples de statistiques ensemblistes $(\Ligne,\Iligne)$,
$(\Rise\circ\!\Majcode,\Ligne)$,
$(\Ligne,\Eul\!\circ\!\Invcode)$
 sur ${\cal S}_n$, ainsi que
$(\Rise,\Eul)$ sur $\SE_n$ ont m\^eme distribution. 

\medskip
Le plan de l'article est le suivant. Dans le prochain paragraphe, nous
donnons les applications du Th\'eor\`eme~1.1 \`a l'\'etude des statistiques
{\it num\'eriques Euler-Mahoniennes}. Dans le paragraphe~3, nous expliquons
la d\'emarche naturelle qui m\`ene \`a la construction de la bijection du
Th\'eor\`eme~1.1, qui est, elle, d\'ecrite dans le paragraphe~4. Les
propri\'et\'es de cette bijection reposent sur une analyse fine du majcodage,
qui est explicit\'ee dans le paragraphe~5. Le paragraphe suivant contient
un lemme fondamental sur les lignes de mont\'ee. Dans le paragraphe~8,
nous calculons le polyn\^ome g\'en\'erateur des permutations, de ligne de
route fix\'ee, par un couple Euler-Mahonien de statistiques. Pour terminer,
nous donnons un exemple num\'erique, qui illustre, d'une part, la
construction de la bijection~$\phi$, d'autre part, le calcul de toutes les
statistiques utilis\'ees.

\bigskip
\centerline{\bf 2. Statistiques Euler-Mahoniennes}

\medskip
Si ``$\Stat$" est une statistique {\it ensembliste}, comme les quatre
statistiques pr\'ec\'edemment introduites, on forme les deux
statistiques {\it num\'eriques} $\#\Stat$ et $\Sigma\Stat$, telles que 
$\#\Stat w$ (resp. $\Sigma\Stat w$) est d\'efinie comme le {\it cardinal
de} (resp. la {\it somme des \'el\'ements dans}) $\Stat w$. 

\goodbreak
Avec ``Ligne", on retrouve 
$\des:=\#\Ligne$ ({\it le nombre de descentes}) et 
$\maj:=\Sigma\Ligne$ ({\it l'indice majeur}). Avec ``Iligne", on pose
traditionnellement
$\ides:=\#\Iligne$,
$\imaj:=\Sigma\Iligne$. On introduit, en plus, les quatre statistiques
d\'efinies sur 
$\SE_n$ :
$\#\Eul$, $\Sigma\Eul$, $\#\Rise$, $\Sigma\Rise$. D'apr\`es la
d\'efinition de la valeur Eul\'erienne donn\'ee en (1.5) et (1.6), on observe
que si $w=x_1x_2\ldots x_n\in \SE_n$, alors
$$
\Sigma\Eul w=x_1+x_2+\cdots+x_n,\leqno(2.1)
$$
une statistique que l'on note plus volontiers $\tot w$ (``tot" pour ``total").
Quant \`a la statistique $\#\Eul$, que l'on note simplement ``$\eul$", elle a
d\'ej\`a \'et\'e introduite dans [Ha90] : soit $w=x_1x_2\ldots
x_n$ un mot sous-exc\'edent. Si
$n=1$, on pose $\eul w=0$ ; si $n\ge 2$ et si l'on pose
$w':=x_1x_2\ldots x_{n-1}\in
\SE_{n-1}$, de sorte que $w=w'x_n$, alors
$$
\eul (w'x_n):=\cases{\eul w',&si $x_n\le \eul w'$ ;\cr
1+\eul w',& si $x_n\ge 1+\eul w'$.\cr}\leqno(2.2)
$$
On peut encore voir que $\eul w$ est la longueur du plus long sous-mot
$x_{i_1}x_{i_2}\ldots x_{i_k}$ $(1\le i_1<i_2<\cdots <i_k)$ tel que $1\le
x_{i_1}$, $2\le x_{i_2}$, \dots~, $k\le x_{i_k}$.

Soit $\inv\sigma$ le {\it nombre d'inversions} de la permutation~$\sigma$.
Par d\'efinition-m\^eme de Invcode, on a imm\'ediatement :
$$
\Sigma\Eul\circ\Invcode=\inv.\leqno(2.3)
$$

\medskip
On dit qu'une statistique bivari\'ee $(f,g)$ est {\it
Euler-mahonienne}, si
$f$ et $g$ sont d\'efinies sur un ensemble fini~$E_n$, de cardinal~$n!$
et si sa fonction g\'en\'eratrice $\sum t^{f(w)}q^{g(w)}$ $(w\in E_n)$, 
\'ecrite sous la forme $A_n(t,q)=\sum\limits_{k\ge 0} A_{n,k}(q)t^k$, satisfait
la relation de r\'ecurrence 
$$
A_{n,k}(q)=[k+1]_q\,A_{n-1,k}(q)+q^k\,[n-k]_q\,A_{n-1,k-1}(q)
\leqno(2.4)
$$
pour $1\le k\le n-1$, avec les conditions initiales :
$A_{n,0}(q)=1$ et $A_{n,k}(q)=0$ pour $k\ge n$. Dans (2.4), on a pos\'e
$[k]_q:=0$ pour $k=0$ et $[k]_q:=1+q+\cdots+q^{k-1}$ pour $k\ge 1$.
Posons
$$
(t;q)_n:=\cases{1,&si $n=0$;\cr
(1-t)(1-tq)\cdots (1-tq^{n-1}),&si $n\ge 1$.\cr}
$$
De fa\c con \'equivalente (l'\'equivalence est facile \`a voir), on peut dire
que
$(f,g)$ est Euler-mahonienne si le polyn\^ome
$A_n(t,q)$ satisfait l'identit\'e
$$
{A_n(t,q)\over (t;q)_{n+1}}=\sum_{r\ge 0} t^r\,(\,[r+1]_q\,)^n.\leqno(2.5)
$$
On sait depuis Carlitz [Ca54] que la statistique $(\des,\maj)$, \'egale
encore \`a $(\#\Ligne,\Sigma\Ligne)$, est
Euler-mahonienne sur~${\cal S}_n$. La proposition suivante r\'esulte alors
de (1.9) et de (1.10).

\proclaim Proposition 2.1. Les couples $(\ides,\imaj)$,
$(\eul\circ\Invcode,\inv)$ sur ${\cal S}_n$ et
$(\eul,\tot)$, $(\#\!\Rise,\Sigma\!\Rise)$ sur
$\SE_n$ sont des statistiques Euler-Mahoniennes.

Se reportant toujours \`a la cha\^\i ne (1.9) et \`a (1.10), on obtient, en
plus, les propri\'et\'es suivantes

\proclaim Propri\'et\'e 2.2. La bijection $\sigma'\mapsto \tau'$ 
de ${\cal S}_n$ sur ${\cal S}_n$
satisfait
$$\leqalignno{
(\Ligne,\ides,\imaj)\,\sigma'&=(\Ligne,
\eul\circ\Invcode,\inv)\,\tau';&(2.6)\cr
(\des,\maj,\ides,\imaj)\,\sigma'&=(\des,\maj,
\eul\circ\Invcode,\inv)\,\tau'.&(2.7)\cr}
$$

La statistique ``$\eul\circ\Invcode$" a \'et\'e introduite par Skandera
[Sk01] sous le nom de ``st". Il avait aussi conjectur\'e qu'il existait une
bijection $\sigma'\mapsto\tau'$ satisfaisant (2.7). On peut donc r\'epondre
positivement \`a sa conjecture.

\proclaim Propri\'et\'e 2.3. La bijection $\sigma'\mapsto w'$ de ${\cal
S}_n$ sur $\SE_n$ satisfait
$$\leqalignno{
(\Ligne,\ides,\imaj)\,\sigma'&=(\Rise, \eul,\tot)\,w';&(2.8)\cr
(\des,\maj,\ides,\imaj)\,\sigma'&=(\#\,\Rise,\Sigma\,\Rise,
\eul,\tot)\,w'.&(2.9)\cr }
$$


Posons
$$
(u;q_1,q_2)_{r+1,s+1}:=\prod_{0\le i\le r,0\le j\le s}
(1-uq_1^iq_2^j).
$$
Comme d\'emontr\'e dans [GG78] (voir aussi [Ra80], [DF86]), l'identit\'e
$$
\sum_{r,s\ge 0}
{t_1^r\,t_2^s\over (u;q_1,q_2)_{r+1,s+1}}
=\sum_{n\ge 0}u^n\,
{A_n(t_1,t_2,q_1,q_2)\over (t_1;q_1)_{n+1}\,(t_2;q_2)_{n+1}},\leqno(2.10)
$$
d\'efinit une suite de polyn\^omes $(A_n(t_1,t_2,q_1,q_2))$ 
$(n\ge 0)$ qui sont les fonctions g\'en\'eratrices de~${\cal S}_n$ par le
quadruplet $(\des,\maj,\ides,\imaj)$. En d'autres termes, on a :
$A_n(t_1,t_2,q_1,q_2)=\sum_{\sigma\in {\cal S}_n}
t_1^{\des\sigma}t_2^{\ides\sigma}q_1^{\maj\sigma}q_2^{\imaj\sigma}$.
L'existence de la bijection $\sigma'\mapsto w'$ permet donc d'obtenir le
r\'esultat suivant, apparemment difficile \`a obtenir directement.

\proclaim Th\'eor\`eme 2.4. La fonction g\'en\'eratrice factorielle des
polyn\^omes g\'en\'e\-ra\-teurs des ensembles $\SE_n$ de mots sous-exc\'edants 
$(n\ge 0)$ par le quadruplet 
$(\#\,\Rise,\Sigma\,\Rise,\eul,\tot)$ est donn\'ee
par l'expression $(2.10)$.

Pour tout couple d'entiers $r,n\ge 0$, notons $n\brack r$ le
$q$-coefficient binomial d\'efini par :
$${n\brack r}:=\cases{
\displaystyle{(q;q)_n\over (q;q)_{n-r}\,(q;q)_r},&si $0\le r\le n$;\cr
\noalign{\smallskip}
0,&autrement.\cr}
$$
Soit $L=\{\ell_1<\cdots<\ell_k\}$ un sous-ensemble de
l'intervalle~$\{1,2,\ldots,n-1\}$. On pose $\ell_0:=0$ et
$\ell_{k+1}:=n$ et on d\'esigne par $N_r(L,n)$ la matrice
$(k+1)\times (k+1)$ :
$$
N_r(L,n)=\pmatrix{{\ell_1-\ell_0+r\brack r}&{\ell_2-\ell_0+r\brack
r}&\ldots&{\ell_{k}-\ell_0+r\brack r}
&{\ell_{k+1}-\ell_0+r\brack r}\cr
1&{\ell_2-\ell_1+r\brack r}&\ldots&{\ell_{k}-\ell_1+r\brack r}
&{\ell_{k+1}-\ell_1+r\brack r}\cr
0&1&\ldots&{\ell_k-\ell_2+r\brack r}
&{\ell_{k+1}-\ell_2+r\brack r}\cr
\vdots&\vdots&\ddots&\vdots&\vdots\cr
0&0&\ldots&1&{\ell_{k+1}-\ell_k+r\brack r}\cr}.
$$
En particulier, $N_r(\emptyset,n)={n+r\brack r}$.

\goodbreak
Il r\'esulte des Propri\'et\'es 2.2 et 2.3 que pour tout sous-ensemble~$L$
de
$\{1,2,\ldots, n-1\}$ on a les \'egalit\'es :
$$
\sum_{\sigma\in {\cal S}_n,\Ligne\sigma=L}
\kern-.5cm t^{\ides\sigma}q^{\imaj\sigma}
=\kern-.5cm\sum_{\sigma\in {\cal S}_n,\Ligne\sigma=L}
\kern-.5cm  t^{\eul\circ\Invcode\sigma}q^{\inv\sigma}
=\kern-.5cm\sum_{w\in \SE_n,\Rise w=L} 
\kern-.5cm t^{\eul w}q^{\tot w}.
$$
D\'esignons par $A_L(t,q)$ ce polyn\^ome. Dans le dernier paragraphe, on
\'etablit le r\'esultat suivant, qui entra\^\i ne d'ailleurs l'identit\'e (2.5).

\proclaim Th\'eor\`eme 2.5. On a :
$$
{A_L(t,q)\over (t;q)_{n+1}}=\sum_{r\ge 0} t^r\,\det N_r(L,n).
\leqno(2.11)
$$

\bigskip
\centerline{\bf 3. Comment construire la bijection $\phi$ ?}

\medskip
La construction de $\phi$ n\'ecessite une analyse fine des propri\'et\'es du
maj-codage. On la d\'efinit par r\'ecurrence sur~$n$. Si $n\ge 2$ et si
$\sigma=\sigma(1)\sigma(2)\ldots \sigma(n)$ est une permutation d'ordre~$n$
telle que $\sigma(n)=i$, on pose $\sigma=\sigma'\,i$, o\`u, par cons\'equent,
$\sigma':=\sigma(1)\sigma(2)\ldots \sigma(n-1)$. Si la bijection~$\phi$ a
\'et\'e construite pour les permutations d'ordre inf\'erieur ou \'egal
\`a~$(n-1)$, on l'\'etend, de fa\c con naturelle, aux permutations de la suite
$1,\ldots,(i-1),(i+1),\ldots,n$ \`a l'aide de la bijection $\red_i$ d\'efinie
dans l'introduction. En effet, si
l'on pose $\phi_i:=\red_i^{-1}\circ \phi\circ \red_i$, on d\'efinit
$$
\phi(\sigma)=\phi(\sigma'\,i):=\gamma_i(\phi_i(\sigma'))\,i,
$$
o\`u $\gamma_i$ est un {\it r\'earrangement} de la permutation $\phi_i(\sigma')$
qu'il faut pr\'eciser. Remarquons que cette d\'efinition de~$\phi$
{\it pr\'eserve la derni\`ere lettre}~$i$.

La premi\`ere \'etape de la construction de~$\phi$ est donc de d\'efinir
$\tau':=\gamma_i(\phi_i(\sigma'))$, puis $\tau:=\tau'\,i$. Remarquons que
$\phi\circ\red_i(\sigma')$ est une permutation de $1,2,\ldots, n-1$,
alors que $\tau'$ est une permutation de $1,\ldots,(i-1),(i+1),\ldots,n$.
Dans toute la suite, nous adoptons la convention : 
$\Majcode\tau':=\Majcode\phi\circ\red_i(\sigma')$.  Si l'on d\'esigne par
$x(1)\ldots x(i-1)x(i+1)\ldots x(n)$ le maj-codage de~$\tau'$, on d\'efinit
aussi
$$
\Majcode_i\tau':=x(1)\ldots x(i-1)\bullet x(i+1)\ldots x(n),\leqno(3.1)
$$
o\`u le gros point ``$\bullet$", plac\'e dans la $i$\ieme\ position, satisfait
l'in\'egalit\'e $\bullet <0$. Cette convention s'av\`erera tr\`es utile dans la suite,
car on montrera que l'on a, en fait,
$$
\Iligne\sigma=\Rise\circ\Majcode_i\tau'.\leqno(3.2)
$$

Pour $n\ge 2$, on partitionne ${\cal S}_n$ en deux classes disjointes
${\cal S}'_n$ et ${\cal S}''_n$. La premi\`ere classe est form\'ee de toutes les
permutations~$\sigma$ telle que $\sigma(n-1)<\sigma(n)$ ou telles que
$\sigma(n)=1$ et donc ${\cal S}''_n$ se compose de toutes les
permutations~$\sigma$ telles que $\sigma(n-1)>\sigma(n)\ge 2$. Pour les
permutations~$\sigma$ appartenant \`a ${\cal S}'_n$, le
r\'earrangement~$\gamma_i$ est simplement l'application identique, de sorte que
$\phi(\sigma):=\phi_i(\sigma')\,i$.


Pour les permutations $\sigma$ appartenant \`a ${\cal S}_n''$, on d\'etermine
toujours $\tau'=\phi_i(\sigma')$ et $\tau=\tau'\,i$, une permutation qui
appartient encore \`a ${\cal S}_n''$. Le r\'earrangement~$\gamma_i$, qu'il
faut appliquer \`a~$\tau'$, peut \^etre visualis\'e en se reportant \`a la
Figure~1, o\`u l'on a reproduit la partie droite du graphe de la permutation
$\tau$. La lettre~$\tau(j)$ est la lettre la plus \`a droite de la
permutation~$\tau$ qui soit inf\'erieure \`a $\tau(n)=i\ge 2$. Cette lettre
existe et est bien d\'efinie pour $n\ge 3$. Soient~$l$ la plus petite lettre entre
$\tau(j)$ et~$i$, puis~$L$ la seconde plus petite lettre, si elle existe ; sinon, on
pose $L:=n+1$.


On forme alors les $(L-i-1)$ permutations
$$\eqalign{
\tau_{i+1}&:=(i+1,i+2)\cdots (l-2,l-1)(l-1,l)\,\tau\cr
\ldots&\qquad\ldots\cr
\tau_{l-2}&:=(l-2,l-1)(l-1,l)\,\tau\cr
\tau_{l-1}&:=(l-1,l)\,\tau\cr
\tau_{l}&:=\tau\cr
\tau_{l+1}&:=(l+1,l)\,\tau\cr
\tau_{l+2}&:=(l+2,l+1)(l+1,l)\,\tau\cr
\ldots&\qquad\ldots\cr
\tau_{L-1}&:=(L-1,L-2)\cdots (l+2,l+1)(l+1,l)\,\tau\cr}\leqno(3.3)
$$
qui se d\'eduisent de~$\tau$ par application de ces produits de transpositions.
Comme elles se terminent toutes par~$i$, on pose
$\tau_k:=\tau'_k\,i$ pour $k=i+1,i+2,\ldots, L-1$.
La construction de~$\phi$ utilise la propri\'et\'e suivante.


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

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

\setbox\boxpermu=\vbox{\vskip
25mm\offinterlineskip 
%
\segment(0,0)\dir(1,6)\long{10}
\segment(10,60)\dir(1,-6)\long{5}
\segment(15,30)\dir(1,3)\long{5}
\segment(20,45)\dir(1,1)\long{5}
\segment(25,50)\dir(1,-2)\long{5}
\segment(35,55)\dir(1,-6)\long{7.5}
\segment(30,40)\dir(1,3)\long{5}
%
\segment(0,10)\dir(1,0)\long{42.5}
%
\centerput(0,-1){$\bullet$}
\centerput(10,59){$\bullet$}
\centerput(15,29){$\bullet$}
\centerput(20,44){$\bullet$}
\centerput(25,49){$\bullet$}
\centerput(30,39){$\bullet$}
\centerput(35,54){$\bullet$}
\centerput(42.5,9){$\bullet$}
%
\centerput(0,10){\vrule height 2pt depth 2pt width .5pt}
\centerput(15,10){\vrule height 2pt depth 2pt width .5pt}
\centerput(36.5,10){\vrule height 2pt depth 2pt width .5pt}
%
\centerput(0,6){$j$}
\centerput(11,-1){$\tau(j)=\tau'(j)$}
%\centerput(15,6){$k$}
\centerput(36.5,6){$n\!-\!1$}
\centerput(43,6){$n$}
\centerput(17,28){$l$}
\centerput(32,38.5){$L$}
\centerput(45,8.5){$i$}
%
\fleche(42.5,15)\dir(-1,0)\long{50}
\fleche(42.5,20)\dir(-1,0)\long{50}
\fleche(42.5,25)\dir(-1,0)\long{50}
\fleche(42.5,35)\dir(-1,0)\long{50}
%
\centerput(-16,34){$L\!-\!1$}
\centerput(-16,24){$l\!-\!1$}
\centerput(-16,14){$i\!+\!1$}
%
\segment(42.5,10)\dir(0,1)\long{25}
\segment(0,10)\dir(0,1)\long{25}
%
\centerput(45,44){$\left.\vrule height 1.5cm depth 1.5cm width 0cm
\right\}$}
\centerput(49,44){$E$}
}

$$
\box\boxpermu\hskip4cm
$$

\medskip
\centerline{Fig. 1}
\endinsert

\proclaim Proposition 3.1. Les permutation $\tau_{i+1},\ldots,\tau_{L-1}$
ont toutes m\^eme ligne de route (que~$\tau$). Leurs maj-codages sont tous
distincts et il existe une bijection, que l'on peut explicitement construire, 
$\psi:l\mapsto p$ de l'intervalle $\{i+1,i+2,\ldots, L-1\}$ sur lui-m\^eme, telle
que 
$$
\Rise\circ\Majcode_i\tau'_l=
\Rise\circ\Majcode \tau_p.\leqno(3.4)
$$

Le fait que ces permutations aient m\^eme ligne de route est \'evident,
puisque chaque transposition appliqu\'ee ne permute que deux entiers {\it
cons\'ecutifs}, qui sont {\it non-adjacents} dans la permutation.
Une fois qu'une bijection $l\mapsto p$ de l'ensemble
$\{i+1,\ldots,L-1\}$ sur lui-m\^eme est d\'efinie, la bijection~$\phi$
cherch\'ee est simplement donn\'ee par :
$\phi(\sigma)=\tau_p$, o\`u $p=\psi(l)$. Compte-tenu de (3.2) et (3.4), elle a
alors la propri\'et\'e: $\Iligne\sigma=\Rise\circ\Majcode\phi(\sigma)$. Le
r\'earrangement~$\gamma_i$ qu'il faut d\'efinir est donc
$\gamma_i(\phi_i(\sigma'))=\tau_p'$.


\def\etiq#1|#2|{\vbox{\offinterlineskip\hbox{#1}\vskip3pt\hbox{#2}}}
\def\etiqb#1|#2|{\vbox{\offinterlineskip\hbox{#1}\vskip5pt\hbox{#2}}}

\medskip
{\sl Exemple}.\quad Consid\'erons la permutation
$\tau=6,4,8,7,2,1,9,5,3$ qui appartient \`a ${\cal S}_9''$. L'extr\'emit\'e
droite de son graphe est repr\'esent\'ee dans la Figure~2.
Les $L-i-1=5$ permutations du tableau (3.3) sont donn\'ees par
$$
\eqalignno{
\Ligne\tau_k&=1\hskip13pt 3\hskip5pt 4\hskip5pt 5\hskip13pt 7\hskip5pt 8\cr
\tau_4=(4,5)\,\tau&=6,5,8,7,2,1,9,4,3\cr
\tau_5=\tau&=6,4,8,7,2,1,9,5,3\cr
\tau_6=(6,5)\,\tau&=5,4,8,7,2,1,9,6,3\cr
\tau_7=(7,6)\,(6,5)\,\tau&=5,4,8,6,2,1,9,7,3\cr
\tau_8=(8,7)\,(7,6)\,(6,5)\,\tau&=5,4,7,6,2,1,9,8,3\cr}
$$

\goodbreak
\midinsert
\newbox\boxpermex

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

\setbox\boxpermex=\vbox{\offinterlineskip 
%
\segment(0,0)\dir(1,0)\long{30}
\segment(5,-10)\dir(1,6)\long{5}
\segment(10,20)\dir(1,-2)\long{10}
%
\centerput(5,-11){$\bullet$}
\centerput(10,19){$\bullet$}
\centerput(15,9){$\bullet$}
\centerput(20,-1){$\bullet$}
%
\centerput(2,-11){$1$}
\centerput(16,19){$L=9$}
\centerput(20,9){$l=5$}
\centerput(23,-4){$i=3$}
}

$$
\box\boxpermex\hskip 3cm
$$

\bigskip\bigskip
\centerline{Fig. 2}
\endinsert

Elles ont toutes la m\^eme ligne de route : $1,3,4,5,7,8$. En laissant tomber la
lettre~3 de la fin, on obtient les permutations $\tau'_k$. La d\'etermination des
$\Majcode_3 \tau'_k$ et des $\Majcode \tau_k$ donne le tableau suivant, o\`u la ligne des
mont\'ees, $\Rise w$, appara\^\i t au-dessus de chaque code~$w$.
$$
\eqalignno{
\Majcode_3
\tau'_4&=\etiq 1|0|,1,\etiqb 3|$\bullet$|,\etiq 4|{\bf 0}|,\etiq 5|2|,3,\etiq 7|2|,\etiq 8|5|,7\,;
\quad\Majcode \tau_4=\etiq 1|0|,1,\etiq 3|0|,{\bf 3},\etiq 5|3|,4,\etiq 7|3|,\etiq 8|6|,8\,;\cr
\Majcode_3 \tau'_5&=\etiq 1|0|,1,\etiqb 3|$\bullet$|,2,\etiq 5|{\bf 0}|,3,\etiq 7|2|,\etiq 8|5|,7\,;
\quad\Majcode \tau_5=\etiq 1|0|,1,\etiq 3|0|,\etiq 4|2|,{\bf 4},4,\etiq 7|3|,\etiq 8|6|,8\,;\cr
\Majcode_3 \tau'_6&=\etiq 1|0|,1,\etiqb 3|$\bullet$|,\etiq 4|2|,3,\etiq 6|{\bf 0}|,\etiq
7|2|,\etiq 8|5|,7\,;
\quad\Majcode \tau_6=\etiq 1|0|,1,\etiq 3|0|,\etiq 4|2|,\etiq 5|3|,{\bf 5},\etiq 7|3|,\etiq
8|6|,8\,;\cr
\Majcode_3 \tau'_7&=\etiq 1|0|,1,\etiqb 3|$\bullet$|,\etiq 4|2|,3,2,\etiq 7|{\bf 0}|,\etiq 8|5|,7\,;
\quad\Majcode \tau_7=\etiq 1|0|,1,\etiq 3|0|,\etiq 4|2|,3,\etiq 6|2|,{\bf 6},\etiq
8|6|,8\,;\cr
\Majcode_3 \tau'_8&=\etiq 1|0|,1,\etiqb 3|$\bullet$|,\etiq 4|2|,3,\etiq 6|2|,5,\etiq 8|{\bf 0}|,7\,;
\quad\Majcode \tau_8=\etiq 1|0|,1,\etiq 3|0|,\etiq 4|2|,3,\etiq 6|2|,\etiq 7|5|,
\etiq 8|{\bf 7}|,8.\cr
}
$$
On constate que les ensembles des lignes de mont\'ees des maj-codages
des~$\tau'_k$, d'une part, et des lignes de mont\'ees des maj-codages
des~$\tau_k$, d'autre part, sont identiques. Reste \`a d\'efinir la bonne
bijection (\cf. \S\kern2pt 6). On verra qu'elle repose sur la propri\'et\'e
classique qui veut que si l'on part d'une permutation de $1,2,\ldots,n$ et 
si l'on ins\'ere dans cette permutation, dans les $(n+1)$ interstices
possibles,  un \'el\'ement distinct de ces $n$ entiers, disons $i+1/2$
avec~$i\ge 0$ entier, l'ensemble des lignes de mont\'ees des $(n+1)$
r\'earrangements obtenus {\it ne d\'epend pas} de~$i$, mais seulement de la
permutation initiale.

\goodbreak
On observe aussi les
deux faits suivants :

on passe de $\Majcode_i\tau'_k$ \`a $\Majcode_i\tau_{k}$ en rempla\c cant
le gros point par~0, le z\'ero reproduit en gras par $(k-1)$ et en
augmentant d'une unit\'e les nombres \`a la droite de ce z\'ero gras.

on passe de $\Majcode_i\tau'_k$ \`a $\Majcode_i\tau'_{k+1}$ en
transposant le z\'ero reproduit en gras et la lettre suivante;

Ces deux faits sont d\'emontr\'es dans les Propositions 5.2 et 5.3.

\bigskip
\centerline{\bf 4. Construction de la bijection $\phi$}

\nobreak
\medskip
Cette construction fait appel \`a la r\'eduction ``$\red_i$" et au maj-codage, dont
les d\'efini\-tions ont \'et\'e donn\'ees dans l'Introduction. Une autre d\'efi\-nition
du maj-codage par \'etiquetage sera donn\'ee au paragraphe~5. 

\medskip
{\it Description de la bijection $\phi$}.\quad
Soit $\sigma\in {\cal S}_n$. Si $n=1$ ou~2, on pose $\phi(\sigma)=\sigma$. Si
$n\ge 3$, on pose $i:=\sigma(n)$, $\sigma':=\sigma(1)\sigma(2)\ldots \sigma(n-1)$
et on d\'efinit $\tau':=\red_i\circ\phi\circ\red_i^{-1}(\sigma')$ et $\tau:=\tau'\,i$.

Si $\tau(n-1)< \tau(n)$ ou si $\tau(n)=1$, on pose :
$\phi(\sigma):=\tau$.

Si $\tau(n-1)>\tau(n)\ge 2$, on d\'etermine le plus grand entier~$j$ tel que
$\tau(j)<i$, puis la plus petite lettre~$l$ de~$\tau$ entre $\tau(j)$ et $\tau(n)$
et la seconde plus petite lettre~$L$, aussi entre $\tau(j)$ et $\tau(n)$. Si cette
seconde plus petite lettre n'existe pas, on pose: $L:=n+1$. (Voir Figure~1.)

Si $i+1=L-1$, on pose aussi : $\phi(\sigma):=\tau$.

On forme alors $\Majcode_i\tau':=x(1)\ldots x(i-1)\bullet x(i+1)\ldots x(n)$.
Si $l=i+1$ ou [si $i+2\le l\le L-2$ et $x(l-1)\ge x(l+1)$], on d\'etermine
le {\it plus long facteur croissant strict} $x(l+1)x(l+2)\ldots x(p)$ du mot
$x(l+1)x(l+2)\ldots x(L-1)$, de sorte que l'on a, ou bien $p=L-1$, ou bien
$l+1\le p\le L-2$ et $x(p)\ge x(p+1)$. On pose alors:
$$\leqalignno{\psi(l)&:=p;&(4.1)\cr
\phi(\sigma)&:=\tau_p=(p,p-1)\cdots (l+2,l+1)(l+1,l)\,\tau.&(4.2)\cr}
$$ 
Si $l=L-1$ ou [si $i+2\le l\le L-2$ et $x(l-1)<x(l+1)$], on d\'etermine le
{\it plus long facteur d\'ecroissant au sens large}
$x(p)x(p+1)\ldots x(l-1)$ de $x(i+1)x(i+2)\ldots x(l-1)$, de sorte que l'on a, ou
bien $p=i+1$, ou bien $i+2\le p\le l-1$ et $x(p-1)>x(p)$. On pose alors
$$
\leqalignno{\psi(l)&:=p;&(4.3)\cr
\phi(\sigma)&:=\tau_p=(p,p+1)\cdots (l-2,l-1)(l-1,l)\,\tau.&(4.4)\cr}
$$
Noter que l'on a deux expressions pour $\tau_p$ suivant que $l+1\le p\le L-1$
ou $i+1\le p\le l-1$.

\bigskip
Donnons encore une description algorithmique, qui permet une programmation
informatique quasiment imm\'ediate. 


\bigskip

A{\eightrm LGORITHME}--$\phi$ : une permutation
$\sigma=\sigma(1)\sigma(2)\ldots \sigma(n)$ \'etant donn\'ee, l'algorithme
suivant fournit la permutation $\tau:=\phi(\sigma)$.

\medskip
{\parindent=23pt
\itemitem{($\phi\,$1)\quad}Si $n=1$, {\eightbf RETURN} la permutation~1.

\medskip
\itemitem{($\phi\,$2)\quad}On pose 
\itemitem{}\quad $i:=\sigma(n)$ ;
\itemitem{}\quad $\sigma':=\sigma(1)\sigma(2)\ldots \sigma(n-1)$ ;
\itemitem{}\quad $\tau':=\red^{-1}_{i}\phi\,\red_i(\sigma')$ ;
\itemitem{}\quad $\tau:=\tau'\,i$ ;

\medskip
\itemitem{($\phi\,$2.1)\quad}Si $\tau(n-1)<i$ ou $i=1$, {\eightbf RETURN}
$\tau$ ;

\medskip
\itemitem{($\phi\,$2.2)\quad}On pose
\itemitem{}\quad $j:=\max\{j': 1\le j'\le n-1,\,\tau(j')<i\}$ ;
\itemitem{}\quad $E:=\{\tau(j+1),\tau(j+2),\ldots,\tau(n-1)\}$ ;
\itemitem{}\quad $l:=\min E$ ;
\itemitem{}\quad $L:=\min(E\setminus\{l\}\cup \{n+1\})$ ;
\itemitem{}\quad $x:=\Majcode_i\tau'=x(1)\ldots x(i-1)\bullet x(i+1)\ldots x(n)$ ;

\goodbreak
\medskip
\itemitem{($\phi\,$2.2.1)}Si $i+1=L-1$,  {\eightbf RETURN} 
$\tau$ ;

\medskip
\itemitem{($\phi\,$2.2.2)}Si $l=i+1$ ou si $[\,i+2\le l\le L-2$ et $x(l-1)\ge
x(l+1)\,]$,
\itemitem{}\quad $\tau:=(l,l+1)\,\tau$ ;
\itemitem{}\quad $p:=l+1$ ;
\itemitem{}\quad Tant que [$\,x(p)<x(p+1)$ et $p\le L-2\,$], faire
\itemitem{}\qquad \{$\tau:=(p,p+1)\,\tau$ ;\quad $p:=p+1$ ;\}
\itemitem{}\quad {\eightbf RETURN} $\tau$ ;

\goodbreak
\medskip
\itemitem{($\phi\,$2.2.3)}Si $l=L-1$ ou si $[\,i+2\le l\le L-2$ et
$x(l-1)<x(l+1)\,]$,
\itemitem{}\quad $\tau:=(l,l-1)\,\tau$ ; 
\itemitem{}\quad $p:=l-1$ ;
\itemitem{}\quad Tant que [$\,x(p-1)\ge x(p)$ et $p\ge i+2\,$], faire
\itemitem{}\qquad \{$\tau:=(p,p-1)\,\tau$ ;\quad $p:=p-1$ ;\}
\itemitem{}\quad {\eightbf RETURN} $\tau$ ;

}

\bigskip
\centerline{\bf 5. Propri\'et\'es du maj-codage}

\nobreak
\medskip
Rappelons la construction du maj-codage par {\it \'etiquetage}, tel qu'elle
est bien expos\'ee, par exemple, dans l'article de Rawlings [R81].
Soit~$\sigma$ une permutation d'ordre~$n$. Si
$n=1$, on pose $\Majcode 1=0$. Supposons $n\ge 2$ et notons
$\sigma^-:=\sigma^-(1)\sigma^-(2)\ldots\sigma^-(n-1)$ la permutation
d'ordre~$(n-1)$ d\'eduite de la permutation
$\sigma=\sigma(1)\sigma(2)\ldots
\sigma(n)$ d'ordre~$n$ par suppression de la lettre~$n$. Posons
$\sigma^-(0)=\sigma^-(n):=0$. Soit $(d+1)$ le nombre d'entiers~$i$ tels que
$0\le i\le n-1$ et $\sigma^-(i)>\sigma^-(i+1)$ (on a toujours
$\sigma^-(n-1)>\sigma^-(n)=0$, de sorte que $d\ge 0$). 

En lisant le mot $\sigma^-(0)\sigma^-(1)\ldots \sigma^-(n-1)\sigma^-(n)$ 
{\it de la droite vers la gauche}, on {\it maj-\'etiquette} $0,1,\ldots, d$ les
$(d+1)$ successions de deux lettres $\sigma^-(i)\sigma^-(i+1)$ telles que
$\sigma^-(i)>\sigma^-(i+1)$ $(0\le i\le n-1)$. On lit ensuite le mot
$\sigma^-(0)\sigma^-(1)\ldots \sigma^-(n-1)\sigma^-(n)$ {\it de la gauche vers la
droite} et on maj-\'etiquette $(d+1)$, $(d+2)$, \dots~, $(n-1)$, les
$(n-1-d)$ successions restantes $\sigma^-(i)<\sigma^-(i+1)$. Or, on passe de
$\sigma^-$ \`a $\sigma$ en ins\'erant~$n$ dans l'une des successions
$\sigma^-(i)\sigma^-(i+1)$ $(0\le i\le n-1)$ (et en supprimant les lettres
$\sigma^-(0)$, $\sigma^-(n)$). Soit $y$ la maj-\'etiquette de la succession
o\`u~$n$ est ins\'er\'e. On pose alors
$$
\Majcode\sigma:=w^-\,y,
$$
o\`u, par r\'ecurrence, $w^-$ est le maj-codage de $\sigma^-$.

Nous supposons $n\ge 2$ et nous nous servons de cette d\'efinition par
\'etiquetage pour comparer les maj-codages des permutations~$\tau'$ et~$\tau$,
o\`u
$\tau'=\tau'(1)\dots \tau'(i-1)\tau'(i+1)\ldots\tau'(n)$ est  une
permutation de $1,\ldots, (i-\nobreak1),(i+1),\ldots,n$ et o\`u
$\tau$ est la permutation de $1,2,\ldots,n$ obtenue 
en juxtaposant la lettre~$i$ \`a la droite de~$\tau'$, soit $\tau:=\tau'\,i$.
On note
$x(1)x(2)\ldots x(i-1)  x(i+1)\ldots x(n)$ le maj-codage
de~$\tau'$.

\proclaim Proposition 5.1. Si $\tau'(n)<i$ et si
$$\leqalignno{
\Majcode_i \tau' &=x(1)x(2)\ldots x(i-1)\,\bullet\,x(i+1)\ldots x(n),\cr
\noalign{\hbox{alors}}
\Majcode \tau' \,i&=x(1)x(2)\ldots x(i-1)\,0\,x(i+1)\ldots x(n)&(5.1)\cr
}
$$
et les lettres $x(i+1)$, \dots~, $x(n)$ sont sup\'erieures ou \'egales \`a~$1$.

{\it D\'emonstration}.\quad
La proposition est \'evidente pour $i=n$. Supposons $1\le i\le n-1$ et notons
$\Sub_k \tau'$ le sous-mot de $\tau'$ r\'eduit aux lettres de~$\tau'$,
inf\'erieures ou \'egales \`a~$k$. Par d\'efinition du maj-codage, on a $\Majcode
\Sub_{i-1}\tau'=x(1)x(2)\ldots x(i-1)$ and $\Majcode
\Sub_{i}\tau' i=x(1)x(2)\ldots x(i-1)0$, puisque~$i$ est juxtapos\'e \`a la
droite de $\Sub_{i-1}\tau'$.

Supposons qu'il existe un entier~$j$ tel que $i+1\le j\le n$
et $x(j)=0$; consid\'erons le plus grand entier~$j$ ayant cette propri\'et\'e. Par
d\'efinition du maj-codage, la permutation $\tau'$ aurait une derni\`ere
lettre \'egale \`a~$j>i$. Ceci contredit l'hypoth\`ese: $\tau'(n)<i$. Ainsi tous
les entiers $x(i+1)$, \dots~, $x(n)$ sont sup\'erieurs ou \'egaux \`a~1.

Pour chaque $j\ge i+1$, on a $\Sub_{j-1}(\tau'i)=(\Sub_{j-1}\tau')\, i$.
Dans la construction du maj-codage de~$\tau'$ (resp.
de~$\tau'i$), aucune lettre $j\ge i+1$ ne peut \^etre ins\'er\'ee \`a la droite de
$\Sub_{j-1}\tau'$ (resp. \`a la droite de $\Sub_{j-1}\tau'\,i$
{\it ni} juste avant la lettre finale~$i$). Par cons\'equent, le maj-\'etiquetage
des entiers $i+1$, $i+2$, \dots~, $n$ est identique pour~$\tau'$
et $\tau'\, i$.\cqfd

\medskip
Nous comparons maintenant les maj-codages de $\tau'$ et $\tau=\tau'\,i$
lorsque~$\tau$ appartient \`a ${\cal S}_n''$, c'est-\`a-dire lorsque
$\tau(n-1)>\tau(n)\ge 2$. Les lettres~$l$ et~$L$ conservent les significations
donn\'ees dans la d\'efinition de~$\phi$ ou dans la Figure~1.

\goodbreak
\proclaim Proposition 5.2. Si $\tau$ appartient \`a ${\cal
S}_n''$, la comparaison des maj-codages de~$\tau'$ (deuxi\`eme
ligne) et de~$\tau$ (troisi\`eme ligne) est indiqu\'ee dans la table
suivante :
$$\eightpoint
\matrice{1&\ldots&i\!-\!1&i&i\!+\!1&\ldots&l\!-\!1&l&l\!+\!1&\ldots
&L\!-\!1&\ldots&n\cr
x(1)&\ldots&x(i\!-\!1)&\bullet&x(i\!+\!1)&\ldots&x(l\!-\!1)&0
&x(l\!+\!1)&\ldots&x(L\!-\!1)&\ldots&x(n)\cr
x(1)&\ldots&x(i\!-\!1)&0&x(i\!+\!1)&\ldots&
x(l\!-\!1)&l\!-\!1&\overline x(l\!+\!1)&\ldots&\overline
x(L\!-\!1)&\ldots&\overline x(n)\cr }
$$
o\`u $\overline x(k):=1+x(k)$.
De plus, les lettres $x(i+1),\ldots,x(L-1)$ sont toutes au moins \'egales
\`a~$1$; enfin, si $L\le n$, on a $x(L)=L-2$ ou~$0$; si $l+1\le L-1$, on a:
$x(l+1)\le l-2$. 

{\it D\'emonstration}.\quad
Le sous-mot $\Sub_{l-1}\tau'$ se termine par $\tau(j)<i$ (\cf. Fig.~1). Il
r\'esulte de la Proposition~5.1 que le maj-codage de $\Sub_{l-1}\tau$ vaut
$$
x(1)\ldots x(i-1)\,0\,x(i+1)\ldots x(l-1)
$$
et les lettres $x(i+1),\ldots, x(l-1)$ sont toutes plus grandes que~1.
Lorsque l'on construit le maj-codage de~$\tau$, la lettre~$l$ est ins\'er\'ee
dans la mont\'ee la plus \`a droite $\tau(j)<i=\tau(n)$. On cr\'ee ainsi une
nouvelle descente, qui obtient la maj-\'etiquette~1. Comme cette descente la
plus \`a droite n'appara\^\i t pas dans~$\tau'$, chaque lettre $m\ge l+1$
obtient une maj-\'etiquette $r+1$ dans le maj-codage de~$\tau$, chaque fois
qu'elle obtient la maj-\'etiquette~$r$ dans~$\tau'$.

Maintenant, ou bien $L=n+1$, ou bien $L\le n$ et cette lettre se trouve \`a
droite de~$\tau'(j)$ dans~$\tau'$. On a donc $x(L)=L-2$ ou~0.
Supposons enfin $i+1<L-1$. Lors de la construction du maj-codage de~$\tau'$,
la lettre $(l+1)$ n'a pas \'et\'e ins\'er\'ee dans la mont\'ee la plus \`a droite
$\tau'(j)<i$, qui a la maj-\'etiquette $(l-1)$. On a donc
$x(l+1)\le l-2$.\cqfd

\medskip
\proclaim Proposition 5.3. Si $\tau=\tau'\,i$ appartient \`a ${\cal S}_n''$ 
et si $l+1\le L-1$, la comparaison des maj-codages de~$\tau'$ (deuxi\`eme
ligne) et de
$\upsilon':=(l,l+1)\,\tau'$ (troisi\`eme ligne) est donn\'ee dans la table:
$$\eightpoint
\matrice{1&\!\ldots\!&i\!-\!1&i&i\!+\!1&\!\ldots\!&l\!-\!1&l&l\!+\!1&\!\ldots\!
&L\!-\!1&\!\ldots\!&n\cr
x(1)&\!\ldots\!&x(i\!-\!1)&\bullet&x(i\!+\!1)&\!\ldots\!&x(l\!-\!1)&0
&x(l\!+\!1)&\!\ldots\!&x(L\!-\!1)&\!\ldots\!&x(n)\cr
x(1)&\!\ldots\!&x(i\!-\!1)&\bullet&x(i\!+\!1)&\!\ldots\!&
x(l\!-\!1)&x(l\!+\!1)&0&\!\ldots\!&
x(L\!-\!1)&\!\ldots\!&x(n)\cr
}
$$

{\it D\'emonstration}.\quad
Il existe deux mots~$w_1$, $w_2$, avec $w_2$ non-vide, tels que
$$
\Sub_{l+1}\tau'=w_1\,(l+1)\,w_2\,l
\quad{\rm et}\quad
\Sub_{l}\upsilon'=w_1\,l\,w_2.
$$
Comme l'insertion de~$l$ dans $\Sub_{l-1}\tau'$ cr\'ee une mont\'ee, de
maj-\'etiquette maxima, le maj-\'etiquetage de~$(l+1)$ dans $\Sub_l\tau'$ et
celui de $l$ dans  $\Sub_{l-1}\upsilon'$ sont identiques, tous deux \'egaux \`a
$x(l+1)$. Par ailleurs, la maj-\'etiquette de~$(l+1)$ dans $\upsilon'$
est~0.\cqfd

\medskip
\goodbreak
De m\^eme, le maj-codage de $(l-1,l)\,\tau'$ vaut
$$\eightpoint
\matrice{1&\!\ldots\!&i\!-\!1&i&i\!+\!1&\!\ldots\!&l\!-\!2&l\!-\!1&l&\!\ldots\!
&L\!-\!1&\!\ldots\!&n\cr
x(1)&\!\ldots\!&x(i\!-\!1)&\bullet&x(i\!+\!1)&\!\ldots\!&x(l\!-\!2)&0
&x(l\!+\!1)&\!\ldots\!&x(L\!-\!1)&\!\ldots\!&x(n)\cr
}
$$
et celui de $(i+1,i+2)\cdots (l-2,l-1)(l-1,l)\,\tau'$
$$\eightpoint
\matrice{1&\!\ldots\!&i\!-\!1&i&i\!+\!1&i\!+\!2&\!\ldots\!&l&l\!+\!1
&\!\ldots\!&L\!-\!1&\!\ldots\!&n\cr
x(1)&\!\ldots\!&x(i\!-\!1)&\bullet&0&x(i\!+\!1)&\!\ldots\!&x(l\!-\!1)
&x(l\!+\!1)&\!\ldots\!&x(L\!-\!1)&\!\ldots\!&x(n)\cr
\noalign{\medskip}
\noalign{\hbox{\tenpoint\hskip-1.3cm que l'on {\it r\'ecrit} d\'esormais:}}
\noalign{\medskip}
y(1)&\!\ldots\!&y(i\!-\!1)&\bullet&0&y(i\!+\!2)&\!\ldots\!&y(l)
&y(l\!+\!1)&\!\ldots\!&y(L\!-\!1)&\!\ldots\!&y(n)\cr
}
$$
Utilisant cette nouvelle expression et conservant les notations (2.3), on
obtient ainsi le r\'esultat suivant.

\proclaim Proposition 5.4. Les maj-codages des
permutations $\tau'_{i+1}$, \dots~, 
$\tau'_{l-1}$, $\tau'_l$, $\tau'_{l+1}$, \dots~, $\tau'_{L-1}$ sont donn\'es
par les lignes de la matrice
$$\eightpoint
\petitematrice{1&\ldots& i\!-\!1&i&i\!+\!1
&\ldots
&l\!-\!1&l&l\!+\!1
&\ldots
&L\!-\!1&\ldots &n\cr
y(1)&\ldots& y(i\!-\!1)&\bullet&0
&\ldots 
&y(l\!-\!1)&y(l)&y(l\!+\!1)
&\ldots
&y(L\!-\!1)&\ldots &y(n)\cr
\multispan{13}\dotfill\cr
y(1)&\ldots& y(i\!-\!1)&\bullet&y(i\!+\!2)
&\ldots
&0&y(l)&y(l\!+\!1)
&\ldots
&y(L\!-\!1)&\ldots &y(n)\cr
y(1)&\ldots&y(i\!-\!1)&\bullet&y(i\!+\!2)
&\ldots
&y(l)&0&y(l\!+\!1)
&\ldots
&y(L\!-\!1)&\ldots& y(n)\cr
y(1)&\ldots& y(i\!-\!1)&\bullet&y(i\!+\!2)
&\ldots
&y(l)&y(l\!+\!1)&0
&\ldots
&y(L\!-\!1)&\ldots& y(n)\cr
\multispan{13}\dotfill\cr
y(1)&\ldots &y(i\!-\!1)&\bullet&y(i\!+\!2)
&\ldots
&y(l)&y(l\!+\!1)&y(l\!+\!2)
&\ldots
&0&\ldots&y(n)\cr
}
$$
tandis que les maj-codages des permutations $\tau_{i+1}$, \dots~, 
$\tau_{l-1}$, $\tau_l$, $\tau_{l+1}$, \dots~, $\tau_{L-1}$ sont donn\'es
par les lignes de la matrice
$$\eightpoint
\petitematrice{1&\ldots& i\!-\!1&i&i\!+\!1
&\ldots
&l\!-\!1&l&l\!+\!1
&\ldots
&L\!-\!1&\ldots &n\cr
y(1)&\ldots& y(i\!-\!1)&0&i
&\ldots 
&\overline y(l\!-\!1)&\overline y(l)&\overline y(l\!+\!1)
&\ldots
&\overline y(L\!-\!1)&\ldots &\overline y(n)\cr
\multispan{13}\dotfill\cr
y(1)&\ldots& y(i\!-\!1)&0&y(i\!+\!2)
&\ldots
&l\!-\!2&\overline y(l)&\overline y(l\!+\!1)
&\ldots
&\overline y(L\!-\!1)&\ldots &\overline y(n)\cr
y(1)&\ldots&y(i\!-\!1)&0&y(i\!+\!2)
&\ldots
&y(l)&l\!-\!1&\overline y(l\!+\!1)
&\ldots
&\overline y(L\!-\!1)&\ldots&\overline  y(n)\cr
y(1)&\ldots& y(i\!-\!1)&0&y(i\!+\!2)
&\ldots
&y(l)&y(l\!+\!1)&l
&\ldots
&\overline y(L\!-\!1)&\ldots&\overline  y(n)\cr
\multispan{13}\dotfill\cr
y(1)&\ldots &y(i\!-\!1)&0&y(i\!+\!2)
&\ldots
&y(l)&y(l\!+\!1)&y(l\!+\!2)
&\ldots
&L-2&\ldots&\overline y(n)\cr
}
$$
De plus, on a les in\'egalit\'es suivantes:
$$\displaylines{{\rm(5.2)}\ 
1\le y(i+2)\le i-1,\ 1\le y(i+3)\le i,\ \ldots\ ,\ 1\le y(L-1)\le L-4;\hfill\cr
\rlap{\rm(5.3)}\hfill
y(L)=0\quad{\rm ou}\quad y(L)=L-2.\hfill\cr}
$$

\bigskip
\centerline{\bf 6. La correspondance entre lignes de mont\'ees}

\nobreak
\medskip
Se reportant \`a l'\'enonc\'e de la Proposition~5.4, nous nous proposons de
montrer qu'\`a toute ligne du premier tableau correspond biunivoquement une
ligne du second tableau ayant m\^eme ligne de route. Observons, tout d'abord,
qu'avec la convention $\bullet<0$ et l'in\'egalit\'e $1\le y(i+2)$, il y a une
descente en position $i-1$ et une mont\'ee en~$i$ dans {\it toutes} les lignes
des deux tableaux. 

\goodbreak
Supposons $L\le n$. Si $y(L)=0$, alors $y(L-1)\ {\rm ou}\ 0\ge y(L)$ dans
le premier tableau et $\overline y(L-1)\ {\rm ou}\ L-2\ge 1=\overline y(L)$
dans le second tableau, puisque $i\le 2$ entra\^\i ne $L\ge 3$. Ainsi {\it
toutes} les lignes des deux tableaux ont une descente en position~$L-1$.
Si $y(L)=L-2$, alors $y(L-2)<y(L)$, d'apr\`es (5.2) et donc
$\overline y(L-2)<\overline y(L)$. Par ailleurs, $0\le y(L)$ et
$L-2<L-1=\overline y(L)$, toujours d'apr\`es (5.2). {\it Toutes} les lignes des
deux tableaux ont alors une mont\'ee en position~$L-1$.

Il suffit donc de d\'efinir une bijection entre les lignes du premier et du
second tableau r\'eduites aux colonnes d'indices $i+1,i+2,\ldots, L-1$.
D'apr\`es~(5.2), on a $y(i+2)\le i-1$, d'o\`u $i\ge \overline y(i+2)$. De
m\^eme, pour $i+3\le l\le L-2$, on a $y(l)\le l-3$ et $y(l+1)\le l-2$, d'o\`u
$y(l)<l-1$ et $l-1\ge \overline y(l+1)$. Enfin, $y(L-1)<L-2$. Il en r\'esulte
qu'il suffit de d\'efinir une bijection, qui conserve la ligne de mont\'ees, entre
les lignes not\'ees $B'_{i+1},\ldots,B'_{L-1}$
et $B_{i+1},\ldots,B_{L-1}$, des matrices bord\'ees
$$\eightpoint
\displaylines{
B':=
\bordermatrix{&i+1&i+2&\ldots
&L-2&L-1\cr
i+1&0&y(i+2)&\ldots
&y(L-2)&y(L-1)\cr
i+2&y(i+2)&0&\ldots
&y(L-2)&y(L-1)\cr
\ \ldots&\multispan{5}\dotfill\cr
L-2&y(i+2)&y(i+3)&\ldots
&0&y(L-1)\cr
L-1&y(i+2)&y(i+3)&\ldots
&y(L-1)&0\cr
}\cr
\noalign{\medskip}
B:=
\bordermatrix{&i+1&i+2&\ldots
&L-2&L-1\cr
i+1&\infty&y(i+2)&\ldots
&y(L-2)&y(L-1)\cr
i+2&y(i+2)&\infty&\ldots
&y(L-2)&y(L-1)\cr
\ \ldots&\multispan{5}\dotfill\cr
L-2&y(i+2)&y(i+3)&\ldots
&\infty&y(L-1)\cr
L-1&y(i+2)&y(i+3)&\ldots
&y(L-1)&\infty\cr}\cr}
$$
o\`u on a supprim\'e les barres sur les lettres, devenues inutiles pour la seule
comparaison des lignes de mont\'ees et aussi remplac\'e les coefficients
diagonaux dans la seconde matrice par le symbole~$\infty$. 

Pour obtenir les lignes de la matrice~$B'$ (resp.~$B$), on part du mot
$y(i+2)y(i+3)\ldots y(L-1)$ et on ins\`ere la lettre~0 (resp.~$\infty$) dans les
diff\'erents $(L-i-1)$ interstices. Ceci implique, en particulier, que
les lignes des matrice~$B'$ et~$B$ ont des lignes de mont\'ees {\it
distinctes}. 

La construction de la bijection s'inspire du principe bien connu
pour les permutations, qui veut que si l'on ins\`ere une
lettre quelconque, mais {\it distincte} de toutes les lettres pr\'esentes, 
dans les $(L-i-1)$ interstices, on obtient toujours le m\^eme ensemble de
lignes de mont\'ees pour les $(L-i-1)$ mots ainsi form\'es.

On d\'efinit alors des lettres soulign\'ees, que l'on entrelace avec les entiers de
la fa\c con suivante :
$$
\underline 0=0<1<\underline 1<2<\underline 2<\cdots
<L-3<\underline{L-3}<L-2<\underline{L-2}=\infty.
$$
Soit $w\,a\,\underline m\,b\,w'$ la ligne d\'eduite de $B'_l$ par le
remplacement du~0 par~$\underline m$ et o\`u le symbole $-\infty$ a \'et\'e
mis en d\'ebut et en fin de ligne, de sorte que les lettres~$a$
et
$b$ sont toujours d\'efinies et les mots $w,w'$ \'eventuellement vides.

On pose alors
$$
\delta(w\,a\,\underline m\,b\,w')=\cases{w\,a\,m+1\,\underline{m+1}\,b\,w',&si
$a,b\not=m+1$;\cr
w\,a\,m+1\,\underline{m+1}\,w',&si $a\not=b=m+1$;\cr
w\,\underline{m+1}\,m+1\,b\,w',&si $b\not=a=m+1$;\cr
w\,m+1\,m+1\,\underline{m+1}\,\,w',&si $a=b=m+1$.\cr
}$$
Il est imm\'ediat que la transformation~$\delta$ pr\'eserve la ligne des
mont\'ees et est bijective. La bijection~$\psi:l\mapsto p$ est simplement
donn\'ee par:
$$\psi(l)=p\ \hbox{si et seulement si }\delta^{L-2}(B'_l)=B_p.\leqno(6.1)
$$

\medskip
{\it Exemple}.\quad
Prenons $i=2$, $L=9$ et $B'_{i+1}=B'_3=0,1,4,4,5,1$, de sorte que
$B'_5=1,4,0,4,5,1$. On obtient:
$$\eqalignno{
\delta^3(B'_5)&=1,4,\underline 3,4,5,1\cr
\delta^4(B'_5)&=1,4,4,\underline 4,5,1\cr
\delta^5(B'_5)&=1,4,4,5,\underline 5,1\cr
\delta^7(B'_5)&=1,4,4,5,\underline 7,1=B_7.\cr
}
$$
d'o\`u $\psi(5)=7$.
Avec cette bijection~$\psi$ bien d\'efinie, la Proposition~3.1 est
d\'emontr\'ee. On peut v\'erifier que cette d\'efinition est exactement la
m\^eme que celle donn\'ee dans l'algorithme de~$\phi$ au paragraphe~4.

\bigskip
\centerline{\bf 7. Fin de la d\'emonstration du Th\'eor\`eme 1.1}

\medskip
Reprenons la d\'efinition de~$\phi$ donn\'ee au paragraphe~3. On peut
supposer $n\ge 3$. Partant d'une permutation~$\sigma$ d'ordre~$n$ se
terminant par $\sigma(n)=i$, on d\'efinit une permutation~$\tau=\tau'\,i$,
se terminant aussi par la lettre~$i$. Puisque, par induction,
$\phi$ a \'et\'e appliqu\'e \`a la r\'eduction de
$\sigma(1)\sigma(2)\ldots \sigma(n-1)$, on a aussi :
$\sigma(n-1)=\tau(n-1)$. Par cons\'equent,
$$
\Ligne\sigma=\Ligne\tau.\leqno(7.1)
$$
D'autre part,
$\Iligne\sigma=(\red^{-1}_{i}
\Iligne\red_i\sigma')\cup\{i\}\setminus\{i-1\}$, de plus, par r\'ecurrence, 
on a : $\Iligne \red_i\sigma'=\Rise\circ\Majcode(\red_i\tau')$. Comme $i$
est aussi la derni\`ere lettre de~$\tau$, on en d\'eduit
$$
\eqalignno{
\Iligne\sigma&=\red^{-1}_{i}\Rise\circ
\Majcode(\red_i\tau')\cup\{i\}\setminus\{i-1\}\cr
&=\Rise\circ
\Majcode_i\tau',\cr
}
$$
qui est la relation (3.2).

\goodbreak
Si $\sigma$ appartient \`a~${\cal S}_n'$ 
et se termine par~$i$, alors
$\phi(\sigma)=\tau=\tau'\,i$ et naturellement
$\Rise\circ
\Majcode_i\tau'=\Rise\circ\Majcode \tau$. La relation (1.4) est \'etablie 
d'apr\`es (3.2) et (7.1).

Si $\sigma$ appartient \`a~${\cal S}_n''$, on a $\phi(\sigma)=\tau_p$, o\`u,
avec les notations de la Proposition~3.1, on a $\tau_l:=\tau$ et
$p=\psi(l)$. La relation (1.4) r\'esulte encore de (3.2) et (7.1) et du fait
que $\tau_p$ a m\^eme ligne de route que~$\tau$.

\medskip
{\it Remarque}.\quad
La transformation $\Psi$ introduite
dans [Fo68], d\'efinie sur toute classe de r\'earrangements de mots
et \`a valeurs dans la m\^eme classe, satisfait $\imaj w=\inv\Psi(w)$.
Lorsqu'on la restreint au groupe sym\'etrique, on sait
(\cf. [FS78]) qu'elle satisfait l'identit\'e
$$
(\Ligne, \imaj)\,\sigma=(\Ligne,\inv)\,\Psi(\sigma).
$$
Posons $w'':=\Invcode\circ\Psi(\sigma)$. On en d\'eduit l'identit\'e
$$
(\Ligne,\imaj)\,\sigma=(\Rise,\tot)\,w'',
$$
mais, en g\'en\'eral, $\ides\sigma\not=\eul w''$. La bijection
$\sigma'\mapsto w'$ d\'efinie dans la Propri\'et\'e~2.3 a donc une
propri\'et\'e suppl\'ementaire.

\bigskip
\centerline{\bf 8. Un calcul analytique}

\medskip
\'Etablissons le Th\'eor\`eme 2.5, lorsque le polyn\^ome $A_L(t,q)$ est le
polyn\^ome g\'en\'erateur des permutations de ligne de route~$L$ par le couple
$(\ides,\imaj)$. On r\'eadapte une technique de calcul de
fonctions sym\'etriques, que D\'esarm\'enien (\cf. [Lo02], chap.~11) a utilis\'ee
dans le cas $t=1$.

Il est bien connu (voir, par exemple, [Lo02], p. 333) ou vite v\'erifi\'e
que l'on a:
$$
{\ell+r\brack r}=\sum_{r\ge b_1\ge\cdots\ge b_\ell\ge 0}
q^{b_1+\cdots+b_r}.
$$
Reprenons les notations de l'introduction, o\`u $L=\{\ell_1,\ldots,\ell_k\}$
d\'esigne un sous-ensemble de l'intervalle~$\{1,2,\ldots,n-1\}$ et o\`u
$\ell_0:=0$ et $\ell_{k+1}:=n$. Par ailleurs, d\'esignons par $W_r(L,n)$
l'ensemble des mots
$w=w_1w_2\ldots w_n$, de longueur~$n$, dont les lettres sont des entiers
positifs qui satisfont les in\'egalit\'es
$$\displaylines{(*)_{(L,n)}\quad
r\ge w_1\ge\cdots\ge w_{\ell_1}\ge 0;\quad
r\ge w_{\ell_1+1}\ge\cdots\ge w_{\ell_2}\ge 0;\quad\ldots\hfill\cr
\hfill
r\ge w_{\ell_k+1}\ge\cdots\ge w_{n}\ge 0;\quad\cr
w_{\ell_1}<w_{\ell_1+1},\quad 
w_{\ell_2}<w_{\ell_2+1}\quad,\ldots,\quad
w_{\ell_k}<w_{\ell_k+1}.\cr }
$$

\proclaim Proposition 8.1. On a l'identit\'e:
$\displaystyle
\sum_{w\in W_r(L,n)}q^{\tot w}=\det N_r(L,n)$.

{\it D\'emonstration}.\quad
La proposition est \'evidemment vraie pour $k=1$. Pour $k\ge 2$, on
d\'eveloppe le d\'eterminant de $N_r(L,n)$ suivant les \'el\'ements de
la derni\`ere ligne. Par r\'ecurrence, on obtient
$$\displaylines{\quad
\det N_r(L,n)=\det
N_r(\{\ell_1,\ldots,\ell_{k-1}\},\ell_k){\ell_{k+1}-\ell_k+r\brack r}
\hfill\cr
\hfill{}
-\det N_r(\{\ell_1,
\ldots,\ell_{k-1}\},n).\quad\cr}
$$
La proposition est ainsi prouv\'ee, puisque
le premier (resp. le second) terme du membre de droite est le
polyn\^ome g\'en\'erateur des mots $w=w_1w_2\ldots w_n$
satisfaisant les conditions
$(*)_{(L,n)}$, sauf \'eventuellement (resp. sauf express\'ement) la
sous-condition $w_{\ell_k}<w_{\ell_k+1}$.\cqfd

\medskip
Nous appliquons maintenant aux mots de $W_r(L,n)$ la
bijection qui les envoie sur des couples $(\sigma,s)$, o\`u
$\sigma$ est une permutation de $1,2,\ldots,n$, de ligne de route
\'egale \`a~$L$ et o\`u $s=s_1s_2\ldots s_n$ est un mot
d\'ecroissant ayant les propri\'et\'es:
$$
r\ge s_1\ge s_2\ge\cdots\ge s_n\ge 0;\ \Ligne\sigma=L;\ 
i\in \Iligne\sigma\Rightarrow s_i>s_{i+1}.\leqno(8.1)
$$ 
Pour d\'efinir le couple~$(\sigma,s)$ correspondant \`a
$w=w_1w_2\ldots x_n\in W_r(L,n)$, on proc\`ede comme suit:
supposons que le r\'earrangement croissant de~$w$ soit de la forme
$i_1^{a_1}\ldots i_m^{a_m}$, avec $i_1<\cdots <i_m$ et $a_1\ge
1$, \dots~, $a_m\ge 1$. On lit~$w$ {\it de gauche \`a droite}, en
donnant les \'etiquettes 1, 2, \dots~, $a_m$ aux $a_m$ lettres
rencontr\'ees \'egales
\`a~$i_m$; on continue, toujours de gauche \`a droite, en donnant les
\'etiquettes $a_m+1$, \dots~, $a_m+a_{m-1}$ aux $a_{m-1}$
lettres rencontr\'ees \'egales \`a~$i_{m-1}$ et ainsi de suite. La
lecture finale de ces \'etiquettes de gauche \`a droite fournit une
permutation $\sigma=\sigma(1)\sigma(2)\ldots\sigma(n)$. Le
mot~$s$ est simplement d\'efini comme le r\'earrangement
d\'ecroissant du mot~$w$.

\medskip
{\it Exemple}.\  
Soient $n=9$, $r=8$, $L=\{2,5,7\}$ et 
$\Bigl(\petitematrice {L\cr
w\cr}\Bigr)= \Bigl(\petitematrice{&2&&&5&&7&&\cr
5&5&7&4&1&3&0&4&4\cr}\Bigr)$ un mot de $N_8(L,9)$. La
permutation~$\sigma$ s'\'ecrit
$\Bigl(\petitematrice {L\cr
\sigma\cr}\Bigr)=
\Bigl(\petitematrice{&2&&&5&&7&&\cr
2&3&\bf1&4&8&\bf7&9&5&\bf6\cr}\Bigr)$ et le
mot~$s$ par
$\Bigl(\petitematrice {\Iligne\sigma\cr
s\cr}\Bigr)=
\Bigl(\petitematrice{\bf1&&&&&\bf6&\bf7&&\cr
7&5&5&4&4&4&3&1&0\cr}\Bigr)$. Les \'el\'ements de $\Iligne\sigma$
ont \'et\'e reproduits en gras.

\medskip
On se persuade ais\'ement que $w\mapsto (\sigma,s)$ est une
bijection de $W_r(L,n)$ sur les couples $(\sigma,s)$ ayant la
propri\'et\'e~(8.1). Une d\'emonstration en est donn\'ee par
D\'esarm\'enien (voir [Lo02], Th\'eor\'eme~11.3.2), dans le cas o\`u les lettres
du mot~$w$ ne sont pas major\'ees par un entier~$r$.

Compte tenu des Propri\'et\'es 2.2 et 2.3, pour d\'emontrer le Th\'eor\`eme
2.5, il suffit d'\'etablir la proposition suivante.

\proclaim Proposition 8.2. On a:
$$
{\displaystyle\sum_{\sigma,\,\Ligne\sigma=L}
t^{\ides\sigma}\,q^{\imaj\sigma}
\over (t;q)_{n+1}}
=\sum_{r\ge 0} t^r\,\det N_r(L,n).
$$

{\it D\'emonstration}.\quad
L\`a encore, c'est une technique d\'ej\`a utilis\'ee dans la th\'eorie des
fonctions sym\'etriques qui conduit au r\'esultat (voir [Lo02],
pp.~371-372 pour la version dite non born\'ee et aussi [DF85],
Th\'eor\`eme~4.1, ou encore [Ma95], p.~82, lorsque l'on manipule des tableaux).
On part d'un couple $(\sigma,s)$ ayant les propri\'et\'es~$(8.1)$ et on appelle
$d=d_1d_2\ldots d_n$ le mot dont les lettres $d_i$ sont d\'efinies par
$$
d_i:=\cases{s_i-s_{i+1}-\chi(i\in \Iligne\sigma),&si $1\le i\le
n-1$;\cr
s_n,&si $i=n$.\cr}
$$
On a alors $d_1+\cdots+d_n+\ides\sigma=s_1$; on peut donc poser
$d_0:=r-s_1\ge 0$ et ainsi $d_0+d_1+\cdots+d_n+\ides\sigma=r$.
Par ailleurs,
$1\cdot d_1+2\cdot d_2+\cdots+ n\cdot
d_n+\imaj \sigma=\tot s$. L'application $(\sigma,s)\mapsto
(\sigma,(d_0,d_1,\ldots,d_n))$ est une bijection des couples $(\sigma,s)$
satisfaisant (8.1) sur les couples
$(\sigma,(d_0,d_1,\ldots,d_n))$ tels que $\Ligne\sigma=L$ et o\`u les entiers
$d_0$, $d_1$, \dots~, $d_n$ sont positifs et satisfont
$d_0+d_1+\cdots+d_n+\ides\sigma=r$. On en tire:
$$\eqalignno{\sum_{r\ge 0}t^r\,\det N_r(L,n)&=
\sum_{r\ge 0}t^r
\sum_{w\in W_r(L,n)}q^{\tot w}
=\sum_{r\ge 0}t^r\sum_{(\sigma,s)}q^{\tot s}\cr
&=\sum_{r\ge 0}\sum_\sigma\sum_{d_0,\ldots,d_n}
t^{d_0+\cdots+d_n+\ides\sigma}
q^{1.d_1+\cdots+n.d_n+\imaj\sigma}\cr
&=\sum_\sigma t^{\ides\sigma}q^{\imaj\sigma}
\sum_{r\ge\ides\sigma}
\sum_{\scriptstyle d_0+\cdots+d_n\atop\scriptstyle
{}=r-\ides\sigma}
t^{d_0}(tq)^{d_1}\cdots (tq^n)^{d_n}\cr
&=\sum_\sigma t^{\ides\sigma}q^{\imaj\sigma}
{1\over (t;q)_{n+1}}.\qed\cr
}
$$

{\it Remarque}.\quad L'identit\'e (2.11) a \'et\'e ainsi d\'emontr\'ee lorsque
le polyn\^ome $A_L(t,q)$ est le polyn\^ome g\'en\'erateur suivant le couple
$(\ides,\imaj)$. La Propri\'et\'e~2.2 permet de conclure que l'identit\'e est
encore vraie lorsque $A_L(t,q)$ est le polyn\^ome g\'en\'erateur  suivant le
couple $(\eul\circ\Invcode,\inv)$. Nous ne proposons pas de m\'ethode de
calcul direct dans ce dernier cas, alors que la sp\'ecialisation de (2.11) pour
$t=1$, \`a savoir $A_L(q)/(q;q)_n=\det N$, o\`u $N=(N_{i,j})$ $(1\le i,j\le
k+1)$ est la matrice $(k+1)\times (k+1)$ donn\'ee par
$$
N_{i,j}:=\cases{1/(q;q)_{\ell_j-\ell_{i-1}},&si $i\le j$;\cr
1,&si $i=j+1$;\cr
0,&autrement;\cr}
$$
peut \^etre obtenue lorsque $A_L(q)$ est, ou bien le polyn\^ome
g\'en\'erateur suivant ``imaj", ou bien suivant ``inv" (\cf. [Lo02], chap.~11).
Notons encore que le calcul de $A_L(q)$ suivant ``inv" est aussi fait dans
Stanley ([St86], p.~70) et qu'il $q$-g\'en\'eralise le vieux r\'esultat de
MacMahon ([Mac15], p.~190).

Remarquons, enfin, que si l'on somme l'identit\'e de la Proposition 8.2, en
rempla\c cant toutefois $\det N_r(L,n)$ par son expression de la
Proposition~8.1, sur tous les sous-ensembles $L\subset
\{1,\ldots,n-1\}$, on obtient, de nouveau, l'identit\'e des polyn\^omes
$q$-Eul\'eriens~(2.5).

\bigskip
\centerline{\bf Un exemple num\'erique}
\medskip


La tableau suivant donne la construction compl\`ete
de $\phi(\sigma)$ pour $\sigma=649821753$ en utilisant
l'algorithme-$\phi$ d\'ecrit dans la paragraphe 4. 
Il doit \^etre lu colonne par colonne de la gauche vers
la droite. On note que le calcul de $\phi(\red_i(\sigma'))$
utilise la valeur obtenue dans la colonne suivante.
On obtient $\phi(\sigma)=658721943$.

\bigskip
% -- 

\def\tableau
    {\vtop\bgroup
      \def\th{\noalign{\hrule}}
       \offinterlineskip\halign\expandafter\bgroup
        }

\def\endtableau{\egroup\egroup}

\def\tvi{\vrule height 12pt depth 5pt width 0pt}
\def\tv{\tvi\vrule}


\def\mytvi{\vrule height 5pt depth 5pt width 0pt}
\def\mytv{\mytvi\vrule}

\def\mypreambule[#1]{%
     \mytv\hfil\kern#1$##$\kern#1\hfil\mytv&&
      \mytvi\hfil\kern#1$##$\kern#1\hfil\mytv\cr}
 


\centerline{\eightpoint
\def\condone{\hbox{$%
\matrix{
\tau(n\!-\!1)<i\cr 
\noalign{\vskip -10pt} \cr
\hbox{\rm ou\ } i=1 ? \cr}
$} }
\def\NON{\hbox{Non}}
\def\OUI{\hbox{Oui}}
\def\redi{\hbox{$\hbox{r\'ed}_i$}}
\tableau\mypreambule[2pt]
\th\tvi
%
\sigma & 649821753 & 53872164 & 4376215 & 436521 & 32541 & 2143 & 213 & 21\cr
\th
\tvi
%
 i     & 3         &  4       &    5    &  1     &   1   &  3   &  3  &  1\cr
\redi(\sigma') & 53872164& 4376215& 436521& 32541& 2143& 213& 21& 1\cr
\phi(\redi(\sigma')) & 53762184& 4376215& 436521&32541  & 2143& 213& 21& 1\cr
\tau' & 64872195& 5387216& 437621&43652& 3254& 214& 21& 2\cr
\tau & 648721953& 53872164& 4376215&436521& 32541& 2143& 213& 21\cr
\condone     & \NON      &  \NON     &    \OUI    &  \OUI     &   \OUI   &  \NON   &  \OUI  &  \OUI\cr
\tvi
 (j,l,L)     & (6,5,9) &  (6,6,9) &    - &  - &   - &  (2,3,5) &  - &  - \cr
 i\!+\!1\!=\!L\!-\!1?     & \NON &  \NON &    - &  - &   - &  \OUI &  - &  - \cr
 x     & 01\!\bullet\! 203257&  012\!\bullet\! 3025&    - &  - &   - &  -&  - &  - \cr
 \hbox{\fivebf RETURN\ \rm par}     & (\phi2.2.3) &  (\phi2.2.2) & (\phi2.1) & (\phi2.1) & (\phi2.1) &  (\phi2.2.1) &  (\phi2.1) & (\phi2.1) \cr
\phi(\sigma)=?\tau & (45)\tau& (87)(76)\tau& \tau&\tau& \tau& \tau& \tau& \tau\cr
\th
\tvi
\phi(\sigma) & 658721943& 53762184& 4376215&436521& 32541& 2143& 213& 21\cr
\th\endtableau}


\bigskip
\bigskip
{\it Calcul des statistiques utilis\'ees}.\quad
Pour $\sigma=649821753$, on obtient :
$$
\eqalignno{
&w =\Invcode \sigma  = 0\ 1\ 0\ 1\ 4\ 5\ 2\ 4\ 6;\cr
&v =\Majcode \sigma  = 0\ 1\ 0\ 2\ 4\ 4\ 6\ 5\ 6;\cr
&\Iligne \sigma  = \{1, 3, 5, 7, 8\};\cr
&\Rise w = \Eul v = \Ligne \sigma  = \{1, 3, 4, 5, 7, 8\};\cr
&\Eul w  = \{1, 3, 4, 7, 8\}.\cr
}$$
D'o\`u
$$
\eqalignno{
&\des \sigma = \# \Ligne \sigma = \# \Eul v = \# \Rise w = 6 ; \cr
&\maj \sigma = \Sigma \Ligne \sigma = \Sigma \Eul v = \Sigma \Rise w = 28 ; \cr
&\ides \sigma= 5; \quad \imaj\sigma = 24; \cr
&\inv \sigma = \tot w = \Sigma \Eul w = 23; \cr
&\eul w = \#\Eul w = 5. \cr
}
$$
Le calcul suivant pour $\phi(\sigma)=658721943$ illustre 
l'identit\'e (1.4). 
$$
\eqalignno{
&\Ligne \phi (\sigma) = \{1,3,4,5,7,8\} = \Ligne \sigma ; \cr
&t= \Majcode \phi(\sigma) = 0\ 1\ 0\ 3\ 3\ 4\ 3\ 6\ 8;\cr
&\Rise t = \{1,3,5,7,8\} = \Iligne \sigma.\cr
}
$$





\bigskip
{\it Remerciements}.\quad
Le premier auteur remercie Doron Zeilberger pour d'utiles discussions, qui sont
\`a l'origine de cet article. Il remercie \'egalement Jean-Pierre
Bourguignon, Michel Brou\'e, Fran\c cois Digne, Guy Henniart, Bernhard
Keller, Yvette Kosmann-Schwarzbach et Marc Rosso d'avoir organis\'e ce beau
Colloque des 17 et 18 juin 2002 \`a Paris en l'honneur de Pierre Cartier.

\vfill\eject

\vglue 1cm
\vskip 0pt minus 5pt

\centerline{\bf Bibliographie}

{\eightpoint
\bigskip\vskip0pt minus 5pt
\article AR01|Ron M. Adin and Yuval Roichman|The flag major index and
group actions on polynomial rings|Europ. J. Combin.|22|2001|431--446|

\article ABR01|Ron M. Adin, Francesco Brenti and Yuval Roichman|Descent
Numbers and Major Indices for the Hyperoctahedral
Group|Adv. in Appl. Math.|27|2001|210--224|

\article Br94|Francesco Brenti|$q$-Eulerian Polynomials
Arising from Coxeter Groups|Europ. J.
Combinatorics|15|1994|417--441|

\article Ca54|L. Carlitz|$q$-Bernouli and 
Eulerian numbers|Trans.
Amer. Math. Soc.|76|1954|332--350|

\divers Ca62|Pierre Cartier|Fluctuations dans les suites de
variables al\'eatoires ind\'epen\-dan\-tes,
{\sl S\'eminaire Bourbaki}
[Expos\'es 241--258, Paris. $\oldstyle 1962$/$\oldstyle 1963$], expos\'e
n\omini~241, p.~241--01-18\pointir New York, Amsterdam,
Benjamin, $\oldstyle 1966$|

\article Ca72|Pierre Cartier|On the structure of free Baxter
algebras|Advances in Math.|9|1972|253--265| 

\divers Ca80|Pierre Cartier|Arrangements d'hyperplans : un chapitre de
g\'eom\'etrie combinatoire, {\sl S\'eminaire Bourbaki} [Expos\'es 551--578, Paris.
$\oldstyle 1980$/$\oldstyle 1981$], expos\'e n\omini~561,
p.~561--01-22\pointir Berlin, Springer-Verlag, $\oldstyle 1982$
({\sl Lecture Notes in Math., {\bf 901}})|

\divers Ca82|Pierre Cartier|La th\'eorie classique et moderne des
fonctions sym\'etriques, {\sl S\'eminaire Bourbaki} [Expos\'es 597--600, Paris.
$\oldstyle 1982$/$\oldstyle 1983$], expos\'e
n\omini~597, p.~597--01-24\pointir Paris, N.~Bourbaki, $\oldstyle 1983$|

\divers Ca90|Pierre Cartier|Nouvelles aventures au pays des $q$-analogues,
{\sl S\'em. Lothar. Comb.}, B23a, 1990, 28 pages.
[{\tt http://www.mat.univie.ac.at/\char126slc}]|

\divers Ca91|Pierre Cartier|D\'emonstration ``automatique"
d'identit\'es et fonctions hyperg\'eom\'etriques [d'apr\`es Zeilberger], {\sl
S\'eminaire Bourbaki} [Expos\'es 745--749, Paris. $\oldstyle
1991$/$\oldstyle 1992$], expos\'e n\omini~746, p.~746--01-43\pointir
Paris, N.~Bourbaki, $\oldstyle 1991$|

\divers Ca00|Pierre Cartier|Mathemagics,
{\sl S\'em. Lothar. Comb.}, B44d, {\oldstyle 2000}, 71 pages.
[{\tt http://www.mat.univie.ac.at/\char126slc}]|

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

\livre Di90|Volker Diekert|Combinatorics on Traces|Berlin, 
Springer-Verlag, {\oldstyle 1990} ({\sl Lecture
Notes in Computer Science, {\bf 454}})|

\article DF85|Jacques D\'esarm\'enien et Dominique Foata|Fonctions
sym\'etriques et s\'eries hyperg\'eom\'etriques basiques multivari\'ees|Bull.
Soc. Math. France|113|1985|3-22|

\article Fo68|Dominique Foata|On the Netto inversion 
number of a sequence|Proc. Amer. Math. Soc.|19|1968|236--240|


\article FH97|Dominique Foata et Guo-Niu Han|Calcul basique des
permutations sign\'ees,~I : longueur et nombre d'inversions|Adv. in Appl.
Math.|18|1997|489--509|

\article FS78|Dominique Foata
and Marcel-Paul Sch\"utzenberger|Major Index and Inversion
number of Permutations|Math. Nachr.|83|1978|143--159|

\article GG79|Adriano M. Garsia and Ira Gessel|Permutations Statistics and
Partitions|Adv. in Math.|31|1979|288--305|

\article Ha90|Guo-Niu Han|Distribution Euler-mahonienne: une
correspondance|C. R. Acad. Sci. Paris|310|1990|311--314|

\divers La01|Bodo Lass|Calcul Combinatoire Ensembliste, Th\`ese Univ.
Strasbourg, {\oldstyle 2001}. Pr\'epubl. IRMA 2000/043, 147 pages|

\divers Le60|D. H. Lehmer|Teaching combinatorial tricks to a computer, Proc.
Sympos. Appl. Math., vol.~{\bf 10}, {\oldstyle1960}, p. 179--193. Amer. Math. Soc.,
Providence, R.I|

\livre
Lo02|M. Lothaire|Algebraic Combinatorics on Words|Cambridge Univ.
Press, {\oldstyle 2002} (Encyclopedia of Math. and its Appl., {\bf 90})|

\livre Ma95|Ian G. Macdonald|Symmetric Functions and Hall Polynomials, {\rm
Second Edition}|Clarendon Press, Oxford, {\oldstyle 1995}|

\livre Mac15|P. A. MacMahon|Combinatory Analysis, {\rm vol.~1}|Cambridge Univ.
Press, {\oldstyle 1915}|


\article Ra81|Don P. Rawlings|Generalized Worpitzky identities with
applications to permutation enumeration|Europ. J. 
Comb.|2|1981|67-78|


\article Re93a|V. Reiner|Signed permutation statistics|Europ. J.
Combinatorics|14|1993|553--567|

\article Re93b|V. Reiner|Signed permutation statistics and cycle
type|Europ. J. Combinatorics|14|1993|569--579|


\article Re93c|V. Reiner|Upper binomial posets and signed
permutation statistics|Europ. J.
Combinatorics|14|1993|581--588|

\article Re95a|V. Reiner|Descents and one-dimensional characters for
classical Weyl groups|Discrete Math.|140|1995|129--140|

\divers Re95b|V. Reiner|The distribution of descents and length
in a Coxeter group, {\sl Electronic J. Combinatorics}, vol.~{\bf 2},
{\oldstyle 1995}, \# R25.\hfil\break
[{\tt http://www.emis.de/journals/EJC/}]|

\divers Sc77|M.-P. Sch\"utzenberger|La correspondance de Robinson, 
{\sl Combinatoire et Repr\'esentation du Groupe Sym\'etrique}. [Actes Table
Ronde Strasbourg. $\oldstyle 1976$], p. 59--113. Berlin,
Springer-Verlag, {\oldstyle 1977} ({\sl Lecture Notes in Math., {\bf 579}})|

\divers Sk01|Mark Skandera|An Eulerian partner for inversions, {\sl S\'em.
Lothar. Combin.}, vol.~{\bf 46}, B46d, {\oldstyle 2001}, 19 pages.
[{\tt http://www.mat.univie.ac.at/\char126slc}]|


\article Sp56|Frank Spitzer|A combinatorial lemma and its applications to
Probability Theory|Trans. Amer. Math. Soc.|82|1956|323--339|

\article St73|Richard P. Stanley|Acyclic orientations of graphs|Discrete
Math.|5|1973|171--178|

\article St76|Richard P. Stanley|Binomial posets, M\"obius
inversion, and permutation enumeration|J. Combinatorial
Theory Ser.~A|20|1976|336--356|

\livre St86|Richard P. Stanley|Enumerative Combinatorics, {\rm
vol.~1}|Wads\-worth \& Brooks, {\oldstyle 1986}|

\article StE94|Einar
Steingr\'\i msson|Permutation Statistics of Indexed 
Per\-mu\-ta\-tions|Europ. J. 
Combinatorics|15|1994|187--205|

\article StJ92|John Stembridge|Eulerian numbers, tableaux, and
the Betti numbers of a toric variety|Discrete
Math.|99|1992|307--320|

\article Ze90|D. Zeilberger|A holonomic system approach
to special functions identities|J. Comput. and Appl. Math.|32|1990|321--368|
}

\bigskip\bigskip
\hbox{\vtop{\halign{#\hfil\cr
Dominique Foata \cr
D\'epartement de math\'ematique\cr
Universit\'e Louis Pasteur\cr
7, rue Ren\'e-Descartes\cr
F-67084 Strasbourg, France\cr
\noalign{\smallskip}
{\tt foata@math.u-strasbg.fr}\cr}}
\qquad
\vtop{\halign{#\hfil\cr
Guo-Niu Han\cr
I.R.M.A. UMR 7501\cr
Universit\'e Louis Pasteur et CNRS\cr
7, rue Ren\'e-Descartes\cr
F-67084 Strasbourg, France\cr
\noalign{\smallskip}
{\tt guoniu@math.u-strasbg.fr}\cr}}
}

\bye
