\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=eufm7 at 8pt
\font\eightbboard=msbm8
\font\sevengoth=eufm7
\font\sevenbboard=msbm7
\font\sixgoth=eufm6
\font\fivegoth=eufm5

\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


\frenchspacing

\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\qed{\quad\raise -2pt\hbox{\vrule\vbox to 10pt{\hrule width 4pt
\vfill\hrule}\vrule}}

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

\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 }

\catcode`\@=12
% 0 1 2 3 4 5 6 7 8 9
% a b c d e f g h i j


\def\Cafe  {1} % Ca54
\def\Cafj  {2} % Ca59
\def\Cahb  {3} % Ca71
\def\CaFogj{4} % CaFo69
\def\Cljf  {5} % Cl95
\def\ClFoje{6} % ClFo94
\def\ClFojf{7} % ClFo95
\def\ClFojfa{8}% ClFo95a ??
\def\Denja {9} % Den90
\def\Fogf {10} % Fo65
\def\FoZeja{11}% FoZe90
\def\Hajd {12} % Ha93
\def\Hajf{13}  % Ha95
\def\Knhd{14}  % Kn73
\def\Loid{16}  % Lo83
\def\Macbd{17} % Mac13
\def\Machi{18} % Mac78
\def\Macbf{19} % Mac15
\def\Knutha{15} 

%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},
     #3, {\sl #4} {\bf #5} (#6), #7.\par}}
%reference pour un livre :
\def\livre#1|#2|#3|#4|
    {{\leftskip=7mm\noindent
    \hangindent=2mm\hangafter=1
    \llap{#1.\hskip.35em}{#2},
    {``#3,"} #4.\par}}
%reference complementaire :
\def\divers#1|#2|#3|
    {{\leftskip=7mm\noindent
    \hangindent=2mm\hangafter=1
     \llap{#1.\hskip.35em}{#2},
     #3.\par}}
%


\def\edate{\ifcase\month\or January\or February\or March\or 
April\or May\or
   June\or  July \or August\or September\or
October \or November\or December\fi\space
   \number\day,\space\number\year}

\def\ligne{\mathop{\rm ligne}\nolimits}
\def\iligne{\mathop{\rm iligne}\nolimits}

\def\exc{\mathop{\rm exc}\nolimits}
\def\des{\mathop{\rm des}\nolimits}
\def\den{\mathop{\rm den}\nolimits}
\def\maj{\mathop{\rm maj}\nolimits}
\def\inv{\mathop{\rm inv}\nolimits}
\def\imv{\mathop{\rm imv}\nolimits}
\def\Exc{\mathop{\rm Exc}\nolimits}
\def\Nexc{\mathop{\rm Nexc}\nolimits}
\def\sep{\,|\,}

\def\Com{\mathop{\rm Com}\nolimits}
\def\stat{\mathop{\rm stat}\nolimits}
\def\excindex{\mathop{\rm excindex}\nolimits}
\def\id{\mathop{\rm id}\nolimits}

\def\il{\bigl]\kern-.25em\bigl]}
\def\ir{\bigr]\kern-.25em\bigr]}
\def\bfu{{\bf u}}
\def\bfv{{\bf v}}
\def\bfc{{\bf c}}
\def\bfd{{\bf d}}

\catcode`\@=11
\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 }}}\,}
\catcode`\@=12

\newbox\rightcrochet
\setbox\rightcrochet=\vbox{\halign{#\hfil\cr
\offinterlineskip
\vrule width 3pt height 0pt depth 1pt\cr
\noalign{\vskip -1pt}
\kern2pt \vrule width 1pt height 10pt depth 0pt\cr
\noalign{\vskip -12pt}
\vrule width 3pt height 0pt depth 1pt\cr
}}

\newbox\leftcrochet
\setbox\leftcrochet=\vbox{\halign{#\hfil\cr
\offinterlineskip
\vrule width 3pt height 0pt depth 1pt\cr
\noalign{\vskip -1pt}
\vrule width 1pt height 10pt depth 0pt\cr
\noalign{\vskip -12pt}
\vrule width 3pt height 0pt depth 1pt\cr
}}

\def\sep{\,|\,}

%%%% file grille

 \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}

\def\image(#1,#2)#3{\vbox to #1{\offinterlineskip
    \vss #3 \vskip #2}}

\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

\def\cput(#1,#2)#3{\noalign{\nointerlineskip\centerput(#1,#2){#3}
                             \nointerlineskip}}

%%% end of file grille

\titrecourant={TRANSFORMATIONS ON WORDS}
\auteurcourant={DOMINIQUE FOATA AND GUONIU HAN}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%        page 1
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\rightline{\edate}


\vglue 1mm\vfill

\centerline{\bf  TRANSFORMATIONS ON WORDS}
\vskip 10mm
\centerline{By}
\vskip 10mm
\centerline{Dominique FOATA}
\smallskip
\centerline{D\'epartement de math\'ematique}
\centerline{Universit\'e Louis Pasteur}
\centerline{7, rue Ren\'e-Descartes,}
\centerline{F-67084 Strasbourg, France}
\centerline{email: {\tt foata@math.u-strasbg.fr}}
\vskip 10mm
\centerline{and}
\vskip 10mm
\centerline{Guo-Niu HAN}
\smallskip
\centerline{{I.R.M.A.}}
\centerline{Universit\'e Louis Pasteur et {C.N.R.S.}}
\centerline{7, rue Ren\'e-Descartes}
\centerline{ F-67084 Strasbourg, France}
\centerline{email: {\tt guoniu@math.u-strasbg.fr}}




\vfill\eject


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%        page 2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\vglue 1mm\vfill

\centerline{\bf Abstract}
\vskip 1cm
The purpose of this paper is to give the description
of a single algorithm that specializes into several
classical transformations derived on words,  namely the
Cartier-Foata transform, its contextual extension due to Han and
the two $k$-extensions proposed by Clarke and Foata.


\vfill\eject


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%        page 3
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section 1. Introduction|When sorting was systematically
studied in the sixties and seventies, in particular for comparing
the different methods used in practice (see, e.g. [\Knhd]), it
was essential to go back to the classics, to the works
by MacMahon and especially to his treatise on Combinatory
Analysis [\Macbf]. He had made an extensive study of the
distributions of several {\it statistics} on permutations, or
more generally, on permutations with repeated elements, simply
called  {\it words} in the sequel. The most celebrated of those
statistics is probably the classical {\it number of inversions}
which stands for a  very natural measurement of how far a
permutation is from the identity. There are several other
statistics relevant to sorting or to statistical theory, such as
the {\it number of descents}, the {\it number of excedances},
the {\it major index}, and more recently the {\it Denert
statistic}.

MacMahon [\Macbf] had already calculated the distributions of
the early statistics and proved that some of them were equally
distributed on each class of rearrangements of a given word.
Let us state one of his basic results. To this end
suppose that $X$ is a finite non-empty set, referred to as an {\it
alphabet}. For convenience, take $X$ to be the subset
$[\,r\,]=\{1,2,\ldots, r\}$ $(r\ge 1)$ of the positive integers,
equipped with its standard ordering. Let
$\bfc=(c_1,c_2,\ldots,c_r)$ be a sequence of $r$ nonnegative
integers and  $v$ be the nondecreasing word
$v=1^{c_1}2^{c_2}\ldots r^{c_r}$, i.e., 
$v=y_1y_2\ldots y_m$ with $m=c_1+c_2+\cdots+c_r$ and
$y_1=\cdots=y_{c_1}=1$, $y_{c_1+1}=\cdots=y_{c_1+c_2}=2$,
\dots\ , $y_{c_1+\cdots+c_{r-1}+1}=\cdots=y_m=r$. The class
of all rearrangements of~$v$, i.e., the class of all the words~$w$
that can be obtained from~$v$ by permuting  its letters in some
order will be denoted by $R(\bfc)$.

If $w=x_1x_2\ldots x_m$ is  such a word, the number of
excedances, $\exc w$, and the number of descents, $\des w$,
of~$w$  are  classically defined as
$$\eqalign{
\exc w&= \#\{i:1\le i\le m, x_i>y_i\},\cr
\des w&=\#\{i:1\le i\le m-1, x_i>x_{i+1}\}.\cr}
\eqno(1.1)
$$

\goodbreak
Let $A^{\exc}_{\bfc}(t)$ (resp. $A^{\des}_{\bfc}(t)$)
be the generating polynomial
for the class $R(\bfc)$ by the statistic ``exc" (resp.
``des"), i.e., 
$$
A^{\exc}_{\bfc}(t)=\sum_w t^{\exc w},\qquad
A^{\des}_{\bfc}(t)=\sum_w t^{\des w}\quad(w\in R(\bfc)).
$$
MacMahon [\Macbd] showed that those two polynomials were equal
for every $\bfc$. Accordingly, the two statistics ``exc" and
``des"  are {\it equidistributed} on each rearrangement class
$R(\bfc)$. MacMahon also derived an explicit formula for the
generating function for those polynomials.

Back in the sixties, when it was natural to prove such
equidistribution properties in a {\it bijective} manner,  the late
Sch\"utzenberger asked whether a bijection~$\Phi$ could be
constructed on each rearrangement class~$R(\bfc)$ with the
property that
$$
\exc w=\des \Phi(w)\eqno(1.2)
$$
holds for every~$w$. Such a transformation $\Phi$ was devised in
[\Fogf]. A further presentation was made in [\Knhd, p. 24--29], a
more algebraic version appeared in [\CaFogj] and also in [\Loid,
chap.~10].

In the nineties three extensions of that equidistribution
property have been derived. First, by taking pairs of statistics
into account, second, by extending the property to the  case of
an alphabet with two classes of letters; third,  by combining
those two extensions. 

In (1.1) when the {\it number of the} $i$'s is replaced by the
{\it sum of the}~$i$'s we define respectively
$$\eqalign{
\excindex w&= \sum\{i:1\le i\le m, x_i>y_i\},\cr
\maj w&=\sum\{i:1\le i\le m-1, x_i>x_{i+1}\},\cr}
\eqno(1.3)
$$
i.e., the {\it excedance index} and the {\it major index} (also
called the {\it greater index} and already studied by MacMahon
({\it op. cit.})). The major index has been often associated with
the number of descents, for instance in the study of the
$q$-Eulerian polynomials [\Cafe, \Cafj, \Cahb]. Moreover, the joint
distribution of the pair $(\des,\maj)$ was already derived by
MacMahon [\Macbf, vol.~2, p.~211]. It was then natural to  try to
introduce a statistic ``stat" on words, such that the pair
$(\des,\maj)$ was equidistributed with the pair $(\exc,\stat)$ on
each rearrangement class $R(\bfc)$. We could imagine that
``excindex" would be the appropriate statistic ``stat." However
a careful study of the generating polynomials for small values
of~$\bfc$ showed that that assumption was not correct. However
by adding a {\it correcting term} to ``excindex" a new statistic,
``den," called the {\it Denert statistic},  could be formed and
fitted the requirements of ``stat."

Surprisingly, ``den" was discovered in a very different context, by
Denert [\Denja] for the calculation of the genus zeta function of
hereditary orders in some simple algebras. Its explicit
definition is given in (8.4). The construction of a bijection
$\Phi^q$ that maps every rearrangement class $R(\bfc)$
onto itself and satisfies
$$
(\exc,\den)\,w= (\des,\maj)\,\Phi^q(w)\eqno(1.4)
$$ 
was derived in [\Hajd].

\medskip
The previous results were further extended to the case of an
alphabet with two kinds of letters. Keep the same alphabet
$\{1,\ldots, r\}$ as above, but suppose given two nonnegative
integers~$s$ and $\ell$ such that $s+\ell=r$. A letter~$x$
in~$[\,r\,]$ is said to be {\it small} (resp. {\it large}) if 
$x\le s$ (resp. if $x\ge s+1$). Whenever such an alphabet is
considered we will use the notation ${}_sX_\ell$.

\goodbreak
Let $w=x_1x_2\ldots x_m$ be a word in the
alphabet~${}_sX_\ell$ whose  nondecreasing rearrangement is
$v=y_1y_2\ldots y_m$. An integer~$i$ such that $1\le i\le m$
is said to be a $\ell$-{\it excedance} of~$w$ if either
$x_i>y_i$, or $x_i=y_i$ and $x_i$ large; it is said to be a
$\ell$-{\it descent} of~$w$, if either $x_i>x_{i+1}$, or
$x_i=x_{i+1}$ and $x_i$ large (by convention,
$x_{m+1}=s+{1\over 2}$.) The number of $\ell$-excedances (resp.
of $\ell$-descents) of the word~$w$ will be denoted by
$\exc_\ell w$ (resp. by $\des_\ell w$).

Again when we {\it add} the integers~$i$ which are
$\ell$-excedances (resp. $\ell$-descents) of~$w$, we define
the $\ell$-{\it excedance index}, $\excindex_\ell w$
(resp. the $\ell$-{\it major index}, $\maj_\ell w$), of~$w$.

The extension of the equidistribution property (1.2) consists of
constructing a bijection ${}_s\Phi_\ell$ of each rearrangement
class onto itself satisfying
$$
\exc_\ell w= \des_\ell\, {}_s\kern-1pt \Phi_\ell(w).\eqno(1.5)
$$ 
Such a bijection was derived in [\ClFoje].

Finally, an extension of the previous result to bivariate
statistics (or, equivalently, an extension of (1.4) to the
alphabet with two classes of letters) was proposed in [\ClFojf]
in the following way. When adding a ``correcting term" (see
section~6) to the statistic ``$\excindex_\ell$" we can form  the
$\ell$-{\it Denert statistic} ``$\den_\ell$." We can then show
that the two pairs $(\des_\ell,\maj_\ell)$ and
$(\exc_\ell,\den_\ell)$ are equidistributed on each
rearrangement class, by constructing a bijection
$_s\kern-1pt \Phi_\ell^q$ of each rearrangement class onto itself
satisfying
$$
(\exc_\ell,\den_\ell)\, w= (\des_\ell,\maj_\ell)\, {}_s\kern-1pt
\Phi_\ell^q(w).\eqno(1.6)
$$ 
Such a transformation ${}_s\kern-1pt \Phi_\ell^q$ was
constructed in [\ClFojf].

The constructions of bijections having properties $(1.2)$,
$(1.4)$, $(1.5)$, $(1.6)$ have been given in four papers, namely
[\CaFogj, \Hajd, \ClFoje, \ClFojf], respectively. Each time the
notations used have been different. It was also unclear whether
there was a general principle presiding over all those
constructions. The purpose of this paper is to give the
description of a {\it single algorithm} (the algorithm~{\bf
T} in section~5) which, once a commutation rule on pairs of
letters is given and once a linear ordering on the
alphabet~$X$ is defined,  gives the description of each of the
four transformations $\Phi$, $\Phi^q$, ${}_s\Phi_\ell$,
${}_s\Phi_\ell^q$.

There is no special device
to introduce for the constructions of ${}_s\Phi_\ell$ and
${}_s\Phi_\ell^q$, as it was done in [\ClFoje] and [\ClFojf],
where a subsidiary letter ``$\star$" was added to the initial
alphabet~$X$ to make the algorithms work. Also, as was noticed by
Knuth [\Knutha] in a private communication, there is no need to
derive the cancellation law [\Hajd, Theorem~3.1] for the
contextual multiplication in the construction of~$\Phi^q$.

First, we introduce the notion of {\it biword} and give the
description of the {\it straightening} algorithm of a biword
based upon a given sequence of commutations (section~3).
Although any commutation rule can be integrated into our main
algorithm, the two commutations that yield the constructions of
our four bijections are the so-called {\it Cartier-Foata}
commutation and the {\it contextual} commutation. Both are
described in section~4. Our main algorithm~{\bf T} and its
reverse ${\bf U}={\bf T}^{-1}$ are presented in sections~5 and~6.
In sections~7 and~8 we have gathered the definitions of all the
statistics involved. We conclude the paper by giving the main
properties of the bijections constructed by means of
algorithm~{\bf T}.


\section 2. Words and biwords|In the sequel the alphabet
$X$  will be equipped either with its standard ordering, or with a
well-defined ordering. A {\it biword} is an ordered pair of
words of the same length, written as $\alpha=(h,b)$ (``$h$"
stands for ``high" and ``$b$" for ``bottom") or as
$$
\alpha=\pmatrix{h\cr b\cr}=
\pmatrix{h_1h_2\ldots h_m\cr
b_1b_2\ldots b_m\cr}.
$$
For easy reference we shall sometimes indicate the {\it places} 
1, 2, \dots~, $m$ of the letters on the top of the biword:
$$\left[\matrice{\id\cr h\cr b\cr}\right]
=\left[\matrice{1&2&\ldots&m\cr
h_1&h_2&\ldots&h_m\cr 
b_1&b_2&\ldots&b_m\cr}\right].
$$
The word $h$ (resp. $b$) is the {\it top} (resp. {\it bottom}) word
of the biword $(h,b)$. Each biword $h\choose b$ can also be seen
as a word whose letters are the {\it biletters}
$h_1\choose b_1$, \dots~, $h_m\choose b_m$. The integer~$m$ is
the {\it length} of the biword~$w$. A triple $(h,b;i)$ where $i$ is
an integer satisfying $1\le i\le m-1$ is called a {\it pointed
biword}. When $h$ and $b$ are rearrangements of each other, the
biword $(h,b)$ is said to be a {\it circuit}.

\goodbreak
Two classes of {\it circuits} will play a special role in the
paper. First, we introduce the {\it standard circuits}
$\Gamma(b)$ which are circuits of the form $\overline
b\choose b$, where $\overline b$ is the nondecreasing
rearrangement of the word~$b$ with respect to the standard
ordering.  Clearly~$\Gamma$ maps each word onto a standard
circuit in a bijective manner.

For the second class of circuits we fix a total order ``$\preceq$"
on~$X$, not necessarily identical with the standard order and
make use of the obvious notations: ``$\prec$," ``$\succ$,"
``$\succeq$."  A nonempty word 
$h=h_mh_1\ldots h_{m-2}h_{m-1}$ is said to be {\it
$\preceq$-dominated}, if $h_m \succ h_1$, $h_m\succ
h_2$, \dots~, 
$h_m\succ h_{m-1}$. The {\it right to left cyclic shift} of~$h$ is
defined to be the word $\delta h=h_1h_2\ldots h_{m-1}h_{m}$. A
biword of the form $\delta h\choose h$ with $h$
$\preceq$-dominated is called a {\it
$\preceq$-dominated cycle}.

As is known (see, e.g. [\Loid, Lemma~10.2.1]) or easily verified,
each word $b$ is the juxtaposition product
$u^1u^2\ldots$ of $\preceq$-dominated words 
whose first letters ${\rm pre}(u^1)$, ${\rm pre}(u^2)$, \dots\ are
in nondecreasing order with respect to ``$\preceq$" :
$$
{\rm pre}(u^1) \preceq {\rm pre}(u^2)\preceq \cdots{}
\eqno(2.1)
$$
This factorization, called the {\it
increasing factorization} of~$b$, is unique. 

\goodbreak
Given the increasing factorization $u^1u^2\ldots$ of a
word~$b$ with respect of an order ``$\preceq$," we can form the
juxtaposition product 
$$
\Delta(b)=\left(\matrice{\delta u^1&\delta u^2&\ldots\cr
 u^1&u^2&\ldots\cr}\right)\eqno(2.2)
$$
of the $\preceq$-dominated cycles.
Clearly $\Delta$ maps each word onto a product of 
$\preceq$-dominated cycles satisfying inequalities
(2.1), in a bijective manner. Such a product, written as a biword
(2.2), will be called a {\it well-factorized circuit}.

For instance, $4\sep 4\,5\sep1\sep 3\,1\,2\sep 3\,5$ is such an
increasing factorization of a word~$b$ with respect to the 
ordering $5\prec 4\prec 1\prec 2\prec 3$. The corresponding
well-factorized circuit reads:
$$
\Delta(b)=\left(\matrice{4\cr
4\cr}\right|\left.\matrice{5&4\cr
4&5\cr}\right|\left.
\matrice{1\cr 1\cr}\right|\left.
\matrice{1&2&3\cr
3&1&2\cr}\right|\left.
\matrice{5&3\cr 3&5\cr}\right).
$$

\section 3. Commutations|Suppose given a four-variable Boolean
function $Q(x,y;z,t)$ (also written as 
$Q\displaystyle {x,y\choose z,t}$) defined on quadruples of
letters in~$X$. The {\it commutation} ``Com" induced by the
Boolean function $Q(x,y;z,t)$ is defined to be a mapping  that
maps each pointed biword $(h,b;i)$ onto a biword
$(h',b')=\Com(h,b;i)$ with the following properties: if 
$$
\pmatrix{h\cr b\cr}=
\pmatrix{h_1h_2\ldots h_m\cr
b_1b_2\ldots b_m\cr}\quad
{\rm and}\quad
\pmatrix{h'\cr b'\cr}=
\pmatrix{h'_1h'_2\ldots h'_{m'}\cr
b'_1b'_2\ldots b'_{m'}\cr},
$$
then

(C0) $m'=m$ ;

(C1) $h'_j=h_j$, $b'_j=b_j$ for every $j\not=i, i+1$;

(C2) $h'_{i+1}=h_i$, $h'_i=h_{i+1}$ (the $i$-th and $(i+1)$-st
letters of the top word are transposed);

(C3) $b_i'=b_i$ and $b_{i+1}'=b_{i+1}$ if
$Q(h_i,h_{i+1};b_i,b_{i+1})$ true ; 
$b'_i=b_{i+1}$ and $b'_{i+1}=b_i$ if
$Q(h_i,h_{i+1};b_i,b_{i+1})$ false.

\medskip
\noindent
We can also describe the commutation by the following pair of
mappings 
$$\eqalign{
h=h_1\ldots h_{i-1}h_ih_{i+1}h_{i+2}\ldots h_m
&\mapsto h'=h_1\ldots h_{i-1}h_{i+1}h_ih_{i+2}\ldots h_m;\cr
b=b_1\ldots b_{i-1}b_ib_{i+1}b_{i+2}\ldots b_m
&\mapsto b'=b_1\ldots b_{i-1}\,z\,t\,b_{i+2}\ldots
b_m;\cr}
$$
where either $z=b_i$, $t=b_{i+1}$ if
$Q(h_i,h_{i+1};b_i,b_{i+1})$ true, or
$z=b_{i+1}$, $t=b_i$ if
$Q(h_i,h_{i+1};b_i,b_{i+1})$ false.

\medskip

\medskip
{\it Definition}\pointir 
A Boolean function $Q(x,y;z,t)$ is said to be
{\it bi-symmetric} if it is symmetric in the two sets of parameters
$\{x,y\}$, $\{z,t\}$.

\th Lemma 3.1|Let ``$\Com$" be the commutation induced by a
bi-symmetric Boolean function $Q(x,y;z,t)$. Then the mapping
$(h,b;i)\mapsto \Com(h,b;i)$ is involutive.
\finth

The proof of the lemma is a simple verification and will
be omitted.

\medskip
In the rest of the paper we will assume that all the four-variable
Boolean functions $Q(x,y;z,t)$ are bi-symmetric.

\medskip
Two extreme cases are worth being mentioned, when
$Q$ is the Boolean function $Q_{\rm true}$ ``always true" (resp.
$Q_{\rm false}$ ``always false"). The commutation $\Com_{\rm
true}$, associated with $Q_{\rm true}$, permutes only the $i$-th
and
$(i+1)$-st {\it letters} of the {\it top word}~$b$, while $\Com_{\rm false}$, associated with
$Q_{\rm false}$, permutes the $i$-th and $(i+1)$-st
{\it biletters} of the {\it biword} $(h,b)$.

Sorting a biword is defined as follows. Again consider a biword
$(h,b)$ of length~$m$ and let $(h',b')=\Com(h,b;i)$ with $1\le i\le
m-1$. If $1\le j\le\nobreak m-\nobreak 1$, we can form the
pointed biword $(h',b';j)$ and further apply the commutation
``Com" to $(h',b';j)$. We obtain the biword
$\Com(h',b';j)=\Com(\Com(h,b;i);j)$, which we shall denote by
$\Com(h,b;i,j)$. By induction we can define
$\Com(h,b;i_1,\ldots, i_n)$, where $(i_1,\ldots, i_n)$ is a given
sequence of integers less than~$m$.

As each commutation always permutes two adjacent letters
within the {\it top} word (condition (C2)), we
can transform each biword $(h,b)$ into a biword $(h',b')$ whose
top word $h'$ is {\it non-decreasing} by applying a sequence of
commutations. We can also say that for each biword $(h,b)$ there
exists a sequence $(i_1,\ldots, i_n)$ of integers such that the
top word in the resulting biword $\Com(h,b;i_1,\ldots,i_n)$ is 
non-decreasing. Such a biword is called a {\it minimal} biword
and the sequence $(i_1,\ldots,i_n)$ a {\it commutation sequence}.

When using the commutations $\Com_{\rm true}$ or $\Com_{\rm false}$ we
always reach the same minimal biword, but the commutation
sequence is not unique.  With an arbitrary commutation ``Com" 
neither the minimal biword, nor the commutation sequence are
necessarily unique. We then define a particular commutation
sequence $(i_1,\ldots,i_n)$ called the {\it minimal sequence} by
the following two conditions:

(i) it is of minimum length;

(ii) it is minimal with respect to the lexicographic order.

\noindent
Clearly the minimal sequence is uniquely defined by those two
conditions and depends only on the top word~$h$ in $(h,b)$. The
minimal biword derived from $(h,b)$ by using the minimal sequence
is called the {\it straightening} of the biword $(h,b)$. The
derivation is described in the following algorithm {\eightbf
SORTB}.

\smallskip
{\bf Algorithm {\eightbf SORTB}: sorting a biword}\pointir Given a
biword $(h,b)$ and a commutation ``Com" the following algorithm
transforms $(h,b)$ into its straightening $(h',b')$.

\smallskip
{\parindent= 20pt
Prototype $(h',b'):=\hbox{\eightbf SORTB}(h,b,\Com)$.

\item{(1)} Let $(h',b'):=(h,b)$.

\item{(2)} If $h'$ is non-decreasing, {\eightbf RETURN} $(h',b')$.

\item{(3)} Else, let $j$ be the smallest integer such that
$h'(j)>h'(j+1)$. Then let $(h',b'):=\Com(h',b';j)$. Go to (2).

}
\goodbreak

\section 4. The two commutations|We shall introduce two
commutations associated with two specific Boolean
functions~$Q$.

\ssection $4.1$. The Cartier-Foata commutation|We
denote by
$\Com_{CF}$ the commutation induced by the following Boolean
function $Q_{CF}$:
$$\eqalignno{\noalign{\vskip-7pt}
Q_{CF}{x,y\choose z,t}
\ {\rm true\quad}&{\rm if\ and\ only\ if}\quad
x=y.&(4.1)\cr
\noalign{\vskip-7pt}}
$$

\ssection $4.2$. The contextual commutation|We now take the
alphabet ${}_sX_\ell$ (see the Introduction) and denote by
$\Com_H$ the commutation induced by the following Boolean
function $Q_H$: let $x^\pm=x+{1\over 2}$ if $x$ is
small and $x^\pm=x-{1\over 2}$ if $x$ is large; then
$$\eqalignno{\noalign{\vskip-7pt}
&Q_H{x,y\choose z,t}\ 
{\rm true}\cr
{\rm if\ and\ only\ if}\quad&
(z-x^\pm)(z-y^\pm)(t-x^\pm)(t-y^\pm)>0.&(4.2)\cr
\noalign{\vskip-7pt}}
$$

\rema Remarks|

a) Notice that those two
commutations are bi-symmetric, so that the mapping
$(h,b;i)\mapsto \Com(h,b;i)$ is involutive when Com is
equal either to $\Com_{CF}$, or $\Com_H$.

b) {\it Cyclic intervals}\pointir The second commutation was
introduced in the case $\ell=0$ (no large letters) in [\Hajd] and for
an arbitrary~$\ell$ $(0\le \ell\le r)$ in [\ClFojf]. In both papers the
commutations were defined by means of so-called ``cyclic
intervals" that can be defined as follows. Place the $r$ elements
$1, 2,\ldots, s, s+1,\ldots,(r-1), r$ on a circle counterclockwise
and place a bracket on each of those elements as shown in Fig.~1. 
For $x,y\in X$ $(x\not=y)$ the cyclic interval $\il x,y\ir$ is the
subset of all the elements that lie between~$x$ and~$y$ when
the circle is read counterclockwise. The brackets (in the French
notation) indicate if the ends of the interval are to be included
or not. 


\medskip


\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}}}

\newbox\cycleSab

\def\crochet{\vrule width1pt height 3pt depth 0pt
\vrule width 10pt height 1pt depth 0pt
\vrule width1pt height 3pt depth 0pt}

\setbox\cycleSab=\vbox{\offinterlineskip 
\segment(0,0)\dir(0,-1)\long{30}
\segment(0,0)\dir(1,0)\long{30}
\fleche(30,0)\dir(-1,0)\long{16}
\segment(30,0)\dir(0,-1)\long{30}
\fleche(0,-30)\dir(1,0)\long{16}
\segment(0,-30)\dir(1,0)\long{30}
\centerput(0,-5){\crochet}
\centerput(0,-10){\crochet}
\centerput(-5,-5){$1$}
\centerput(-5,-10){$2$}
\centerput(-5,-25){$s$}
\centerput(0,-25){\crochet}
\centerput(30,-5){\crochet}
\centerput(30,-10){\crochet}
\centerput(35,-5){$r$}
\centerput(38,-10){$(r-1)$}
\centerput(38,-25){$(s+1)$}
\centerput(30,-25){\crochet}
\fleche(0,0)\dir(0,-1)\long{15}
\fleche(30,-30)\dir(0,1)\long{15}
\centerput(15,-34.5){Fig. 1}
}


\midinsert
\centerline{\box\cycleSab\hskip30mm}
\vskip 3.8cm
\endinsert



For instance, suppose $1<s<s+1<r$. Then
$\il 1,s\ir=\{2,\ldots,s\}$ (the origin~1 excluded, but the
end~$s$ included), while $\il 1,s+1\ir=\{2,\ldots, s\}$ (both ends
are excluded); also $\il r,s\ir=\{r,1,\ldots ,s\}$ (both ends are
included) and $\il r,s+1\ir=\{r,1,\ldots, s\}$ (the origin~$r$
included, but the end~$(s+1)$ excluded). Finally, define $\il
x,x\ir=\emptyset$ or~$X$ depending on whether $x$ is small or
large.


Then $Q_H\displaystyle {x,y\choose z,t}$ true 
if both $z,t$ are in $\il x,y\ir$ or neither in $\il x,y\ir$.
 
\rem Example|Consider the alphabet ${}_sX_\ell$ with
$s=3$ and $\ell=2$, and the biword
$\alpha=\left[\matrice{1&2&3&4&5&6&7&8&9\cr
4&5&4&1&1&2&3&5&3\cr
4&4&5&1&3&1&2&3&5\cr}\right]$. 
The minimal sequence is then
$2,3,2,1,4,3,2,5,4,3,6,5,4,8,7,6,5$. 
By using $\Com_H$ in {\eightbf
SORTB} we obtain the sequence of commutations
$$\displaylines{
\alpha=\left[\matrice{1&\bf 2&\bf 3\ldots\cr 
4&5&4\ldots\cr
4&4&5\ldots}\right]
\mapsto
\left[\matrice{1&2&\bf 3&\bf 4\ldots\cr 
4&4&5&1\ldots\cr
4&5&4&1\ldots}\right]
\mapsto
\left[\matrice{1&\bf 2&\bf 3&4\ldots\cr 
4&4&1&5\ldots\cr
4&5&1&4\ldots}\right]
\mapsto
\left[\matrice{\bf 1&\bf 2&3&4\ldots\cr 
4&1&4&5\ldots\cr
4&5&1&4\ldots}\right]\cr
\cdots\ \mapsto
\left[\matrice{1&2&3&4&\bf  5&\bf  6&7&8&9\cr 
1&1&2&3&4&3&4&5&5\cr
4&5&1&4&1&3&2&3&5}\right]
\mapsto
\left[\matrice{1&2&3&4& 5& 6&7&8&9\cr 
1&1&2&3&3&4&4&5&5\cr
4&5&1&4&1&3&2&3&5}\right]
=\hbox{\eightbf SORTB}(\alpha,\Com_H)\cr}
$$

\section 5. The main algorithm|In the description of the
following algorithm we take the alphabet ${}_sX_\ell$ having
$s$ small letters $1,2,\ldots,s$ and $\ell$ large letters
$(s+1),\ldots, r$ $(s+\ell=r)$.

The total order used on the {\it places} will always be the
natural order of the integers. However the order ``$\preceq$"
used on the {\it letters} of the words will be the order
``$\preceq$" defined by
$$
r\prec (r-1)\prec \cdots \prec (s+1) \prec
1\prec 2\prec \cdots \prec s. \eqno(5.1)
$$
If there are no large letters so that $\ell=0$ and $s=r$, the
order ``$\preceq$" is identical with the usual order~``$\le$."
To avoid any kind of ambiguity we make precise each time which one
of the orderings is involved by using notations such as
``$\preceq$-greatest" or ``$\le$-nondecreasing"\dots

\goodbreak
\section Algorithm T|Let Com be a commutation induced by a
four-variable Boolean function~$Q$. The following algorithm
transforms each word~$b$ into a rearrangement~$c$ of~$b$.

\medskip
{\parindent=20pt
Prototype $c:={\bf T}(b,\Com)$.

\item{(1)} Let $h$ be the $\le$-nondecreasing
rearrangement of $b$. Form the standard circuit
$\Gamma(b)=(h,b)$:
$$\left[\matrice{\id\cr h\cr b\cr}\right]
=\left[\matrice{1&2&\ldots&m\cr
h_1&h_2&\ldots&h_m\cr 
b_1&b_2&\ldots&b_m\cr}\right],
$$
let $c:=b$ and $\alpha$ be the empty cycle 
$\alpha=\left(\matrice{.\cr .\cr .\cr}\right)$.

\goodbreak
\item{(2a)} If all the places $1,2,\ldots, m$  occur in~$\alpha$, 
{\eightbf RETURN}~$c$ (the juxtaposition product of the bottom
words in~$\alpha$.) 

\item{(2b)} Else, let $D$ be the $\le$-greatest {\it place} not
occurring in $\alpha$.

\item{(2c)} Let $M$ be the $\preceq$-greatest {\it letter}
in~$h$  not in~$\alpha$. Let $i$ be the $\le$-rightmost {\it place}
such that $M=h_i$ and $i\le D$. If $i\le D-1$ apply the
commutation
$$
(h,c):=\Com(h,c;i,i+1, \ldots, D-1).
$$
[If there are no large letters in~$h$, we always have
$i=D$ and the above commutation is bypassed.]
At the end of (2c) we have $h_D=M$ so that 
the initial biword has been
changed  into:
$$\eqalignno{\noalign{\vskip-12pt}
&\kern 1.9cm \alpha\cr
\noalign{\vskip -8pt}
&\ \hbox to 3.8cm{\downbracefill}\cr
\left[\matrice{\id\cr h\cr c\cr}\right]
=\left[\matrice{*&\ldots&*&D\cr
*&\ldots&*&M\cr
*&\ldots&*&*\cr}\right]&
\left(\matrice{*&\ldots&*\cr *&\ldots&*\cr
*&\ldots&*\cr}\right)
\cdots
\left(\matrice{*&\ldots&*\cr *&\ldots&*\cr
*&\ldots&*\cr}\right).\cr}
$$

\item{(3a)} Let $B:=c_D$.

\smallskip
\item{(3b)} If $B=M$, terminate the $\preceq$-dominated cycle
$\left(\matrice{*&\ldots&*\cr 
*&\ldots&M\cr 
M&\ldots&*\cr}\right)$ 
(possibly of length~1) and add it to the left of $\alpha$, so that
the new~$\alpha$ reads
$\left(\matrice{*&\ldots&*\cr 
*&\ldots&M\cr 
M&\ldots&*\cr}\right)\alpha$. 
Go to (2a).

\smallskip
\item{(3c)} Else, look for the $\le$-greatest {\it place}~$j\le
D-1$ such that
$B=h_j$; in short
$$\left[\matrice{\id\cr h\cr c\cr}\right]
=\left[\matrice{\ldots&j&\ldots&D&\ldots&*\cr
\ldots&B&\ldots&*&\ldots&M\cr
\ldots&*&\ldots&B&\ldots&*\cr}\right]
\left(\matrice{*&\ldots&*\cr *&\ldots&*\cr *&\ldots&*\cr}\right)
\cdots
\left(\matrice{*&\ldots&*\cr *&\ldots&*\cr
*&\ldots&*\cr}\right).
$$
If $j\le D-2$, apply the commutation:
$$(h,c)=\Com(h,c;j,j+1,\ldots, D-2),$$
so that $h_{D-1}=B$ after
running the commutation; in short:
$$\left[\matrice{\id\cr h\cr c\cr}\right]
=\left[\matrice{\ldots&j&\ldots&D-1&D&\ldots&*\cr
\ldots&*&\ldots&B&*&\ldots&M\cr
\ldots&*&\ldots&*&B&\ldots&*\cr}\right]
\left(\matrice{*&\ldots&*\cr *&\ldots&*\cr *&\ldots&*\cr}\right)
\cdots
\left(\matrice{*&\ldots&*\cr *&\ldots&*\cr
*&\ldots&*\cr}\right).
$$

\item{(3d)} Let $D:=D-1$ and go to (3a).

}

\goodbreak
\medskip 
We can verify that each step in the previous algorithm is
feasible. For example, the place~$j$ in step (3c) is
well-defined: at this stage ${h\choose c}$ is the product of the
left factor (in square brackets)  $h'\brack c'$ by~$\alpha$ and
$h'$ is necessarily a rearrangement of~$c'$.

\medskip
The algorithm {\bf T} will also be denoted by
${}_s{\bf T}_\ell$ when we want to emphasize that it is applied to
words in the alphabet ${}_sX_\ell$. With $r=s+\ell$ and using
the two commutations $\Com_{CF}$ and $\Com_H$ we can derive
four different trans\-formations:  
$$\eqalign{
\Phi(b)&={}_r{\bf T}_0(b,\Com_{CF}),\kern15pt
\Phi^q(b)={}_r{\bf T}_0(b,\Com_H),\cr
{}_s\Phi_\ell(b)&={}_s{\bf T}_\ell(b,\Com_{CF}),\quad
{}_s\Phi_\ell^q(b)={}_s{\bf T}_\ell(b,\Com_H).\cr}
\eqno(5.2)
$$

\rem Example|Consider the biword
$$
\left[\matrice{\id\cr h\cr
b\cr}\right]
=\left[\matrice{1&2&3&4&5&6&7&8&9\cr
1&1&2&3&3&4&4&5&5\cr
4&5&1&4&1&3&2&3&5\cr}\right].
$$
We calculate the image of~$b$ under the four transformations
defined in (5.2). 

\medskip
For $\Phi(b)= {}_r{\bf T}_0(b,\Com_{CF})$ we obtain
$$
\left[\matrice{\id\cr h\cr
c\cr}\right]
\mapsto\left(\matrice{1&2\cr
3&4\cr 4&3\cr}\right)
\left(\matrice{3&4&5\cr 
1&2&4\cr
4&1&2\cr}\right)
\left(\matrice{6&7&8\cr
1&3&5\cr 
5&1&3\cr}\right)
\left(\matrice{9\cr
5\cr 
5\cr}\right),
$$
so that $c=\Phi(b)=
4\,3\,4\,1\,2\,5\,1\,3\,5$.

\goodbreak
\medskip
We next calculate $\Phi^q(b)={}_r{\bf T}_0(b,\Com_H)$. We get
$$
\left[\matrice{\id\cr h\cr
c\cr}\right]
\mapsto\left(\matrice{
1&2&3&4&5&6&7&8\cr 
4&4&1&1&3&2&3&5\cr  
5&4&4&1&1&3&2&3\cr}\right)
\left(\matrice{9\cr
5\cr 
5\cr}\right),
$$
so that $c=\Phi^q(b)={}_r{\bf T}_0(b,\Com_H)=
5\,4\,4\,1\,1\,3\,2\,3\,5$.

\goodbreak\medskip
For the next two transformations assume that 1, 2, 3 are small
letters, while 4, 5 are large letters, so that $s=3$ and
$\ell=2$. The total order ``$\preceq$" is then:
$5\prec 4\prec 1\prec 2\prec 3$. The calculation of
${}_s\Phi_\ell(b)={}_s{\bf T}_\ell(b,\Com_{CF})$ yields:
$$
\left[\matrice{\id\cr h\cr
c\cr}\right]
\mapsto\left(\matrice{
1&2&3&4&5\cr 
4&1&2&4&3\cr  
3&4&1&2&4\cr}\right)
\left(\matrice{6&7&8&9\cr
5&5&1&3\cr 
3&5&5&1\cr}\right),
$$
so that $c={}_s\Phi_\ell(b)={}_s{\bf T}_\ell(b,\Com_{CF})=
3\,4\,1\,2\,4\,3\,5\,5\,1$.

\medskip
\goodbreak
Finally, ${}_s\Phi_\ell^q(b)={}_s{\bf T}_\ell(b,\Com_H)$  is
then 
$$
\left[\matrice{\id\cr h\cr
c\cr}\right]
\mapsto\left(\matrice{1\cr
4\cr 4\cr}\right)
\left(\matrice{2&3\cr 
5&4\cr
4&5\cr}\right)
\left(\matrice{4\cr
1\cr 
1\cr}\right)
\left(\matrice{5&6&7\cr
1&2&3\cr 
3&1&2\cr}\right)
\left(\matrice{8&9\cr
5&3\cr 
3&5\cr}\right),
$$
so that $c={}_s\Phi_\ell^q(b)={}_s{\bf T}_\ell(b,\Com_H)=
4\,4\,5\,1\,3\,1\,2\,3\,5$.

\section 6. The algorithm U|Again we take the
alphabet ${}_sX_\ell$ and the order defined in (4.1).

\section Algorithm ${\bf U}$|Given a commutation $\Com$, the
following algorithm transforms a word~$c$ into a word $b$ such
that  $b={\bf U}(c,\Com)$.

\medskip
{\parindent=20pt
Prototype $b:={\bf U}(c,\Com)$.

\item{(1)} Let $i:=1$, $S:=c_1$;

\item{(2a)} If $i={\rm length}(c)$, let
$h_i:=S$, $(h,b):=\hbox{\eightbf SORTB}(h,c,\Com)$. {\eightbf
RETURN}~$b$.  

\item{(2b)} Else, let $B:=c_{i+1}$.

\item{(2c)} If $B\succeq S$, let 
$h_i:=S$, $S:=B$. Else, let $h_i:=B$.

\item{(3)} Let $i:=i+1$. Go to (2a).

}
\goodbreak
\th Property|Algorithm $\bf U$ is
the inverse of algorithm~$\bf T$, i.e., for each word~$b$ we have
$$
{\bf U}({\bf T}(b,\Com),\Com)=
{\bf T}({\bf U}(b,\Com),\Com)=b.
$$
\finth

{\bf Proof}\pointir
First examine algorithm {\bf T}. Before returning~$c$ in
step~(2a) the algorithm provides the juxtaposition product
$\alpha=\gamma^1\gamma^2\ldots$ of cycles. Let $u^1$, $u^2$,
\dots\ be the bottom words of those cycles and let
${\rm pre}(u^1)$, ${\rm pre}(u^2)$, \dots\ be the first letters of
those bottom words. Steps~(2c) and~(3b) say that each cycle
$\gamma^i$ was terminated as soon as ${\rm pre}(u^i)$ was
$\preceq$-greater than all the other letters in the cycle.
Accordingly, all the cycles $\gamma^i$ are $\preceq$-{\it
dominated}. Furthermore, ${\rm pre}(u^1) \preceq
{\rm pre}(u^2)\preceq \cdots{}$

Thus $u^1u^2\ldots$ is the increasing factorization of~$c$
(in the terminology of section~2), while 
$\alpha=\gamma^1\gamma^2\ldots
=\left(\matrice{\delta u^1&\delta u^2&\ldots\cr 
u^1&u^2&\ldots\cr}\right)$ is the {\it increasing} product of
$\preceq$-dominated cycles, i.e., $\alpha$ is equal to the
well-factorized circuit $\Delta(c)$
We can say that the algorithm~{\bf T} transforms each {\it
standard circuit} $\Gamma(b)$ into a {\it well-factorized
circuit}~$\Delta(c)$, the word~$c$ being a rearrangement of~$b$.
As  each commutation applied to a pointed biword is involutive,
{\bf T} is a bijection.

Now examine Algorithm ${\bf U}$ and let $u^1u^2\cdots$ be
the increasing factorization of~$c$ as a product of
$\preceq$-dominated words. Once we have reached step~(2a),
verified that the test $i={\rm length}(c)$ was positive and
executed $h_i:=S$, the biword
$(h,c)$ is exactly the well-factorized circuit
$$
\Delta(c)=\left(\matrice{h\cr c\cr}\right)
=\left(\matrice{\delta u^1&\delta u^2&\ldots\cr
u^1&u^2&\ldots\cr}\right).
$$
Thus Algorithm ${\bf U}$ first builds up the
well-factorized circuit $\Delta(c)$ and applies
algorithm $\hbox{\eightbf SORTB}$ to $\Delta(c)$ to produce a
standard circuit $\Gamma(b)$. Again as each local commutation
applied to a pointed biword is involutive, 
${\bf U}$ is a bijection.

Finally, to prove that {\bf T} and ${\bf U}$ are inverse of
each other, we simply examine algorithm {\bf T}. The
commutations are made only in steps~(2c) and~(3c). In both
steps the reverse operation can be written as
$$
(h,c):=\hbox{\eightbf SORTB}(h,c,\Com).\qed
$$

\section 7. Statistics on circuits|We keep the alphabet
${}_sX_\ell$ and consider the class of circuits with letters in
${}_sX_\ell$. Remember that a circuit is a pair
of words $\alpha={v\choose w}$, where $v=y_1y_2\ldots y_m$ and 
$w=x_1x_2\ldots x_m$ are rearrangements of each other and $v$ is
{\it not} necessarily non-decreasing. For each circuit
$\alpha={v\choose w}$, we define
$\exc_\ell{v\choose w}$ to be the number of integers~$i$ such
that $1\le i\le m$ and either $x_i>y_i$, or $x_i=y_i$ and $x_i$
large.

The definition of $\den_\ell{v\choose w}$ is based on
the notion of {\it cyclic interval}, as introduced in section~4.
For each place~$i$ $(1\le i\le m)$ define $p_i$ to be the number
of $j$ such that $1\le j\le i-1$ and $x_j\in \il x_i,y_i\ir$. Also
let $p_{m+1}$ be the number of large letters in~$w$. The
sequence $(p_1,p_2,\ldots, p_{m+1})$ is said to be the
$\ell$-{\it den-coding} of~${v\choose w}$. Furthermore,
define
$$
\den_\ell{v\choose w}
=p_1+p_2+\cdots+p_m+p_{m+1}.\eqno(7.1)
$$

\rem Example|Consider an alphabet with $s=3$ small
letters 1, 2, 3 and $\ell=2$ large letters 4, 5 and form
the circuit
$$
\alpha=\left[\matrice{\id\cr v\cr
w\cr}\right]
=\left[\matrice{1&2&3&4&5&6&7&8&9\cr
4&5&4&1&1&2&3&5&3\cr
4&4&5&1&3&1&2&3&5\cr}\right].
$$
It has a $\ell$-excedence at places 1, 3, 5, 9, so that
$\exc_\ell \alpha=4$. For its $\ell$-Denert coding we first
have $p_1=0$. As $4\in \il 4,5\ir=\{4\}$, we have $p_2=1$. As
$4\not\in\il 5,4\ir=\{5,1,2,3\}$, we have $p_3=0$. Also $p_4=0$
as $\il 1,1\ir$ is empty. As 4, 4, 5, 1 belong to $\il
3,1\ir=\{4,5,1\}$, $p_5=4$. As $\il 1,2\ir=\{2\}$, we have
$p_6=0$. Also $\il 2,3\ir=\{3\}$, so that
$p_7=1$ and $\il 3,5\ir=\{4\}$, so that $p_8=2$. As $\il
5,3\ir=\{5,1,2,3\}$, we get $p_9=6$. Finally,
as there are 4 large letters in~$w$, we get $p_{10}=4$.
Thus $\den_\ell\alpha= 0+1+0+0+4+0+1+2+6+4=18$.

\goodbreak
\medskip
The definitions of $\des_\ell {v\choose w}$ and of $\maj_\ell
{v\choose w}$ depend only on the bottom word~$w$. Put
$x_{m+1}=s$ (the largest small letter) and $x_{m+2}=\infty$
(an auxiliary letter greater than every letter of~$X)$. Then for
each
$i=1,2,\ldots, m+1$ define $q_i$ to be the number of $j$ such
that $1\le j\le i-1$ and $x_j\in \il x_i,x_{i+1}\ir$. The
sequence $(q_1,q_2,\ldots, q_m,q_{m+1})$ is said to be the
$\ell$-{\it maj-coding} of~$\alpha$. Define
$$
\maj_\ell {v\choose w}
=q_1+q_2+\cdots+q_m+q_{m+1}.\eqno(7.2)
$$

Taking the same example as above we can verify that
$(\des_\ell,\maj_\ell)\,\alpha=
(4,18)$, which is also the value
of $(\exc_\ell,\den_\ell)\,\alpha$. In fact the above circuit is
well-factorized and for that class of circuits the two pairs
of statistics have the same values, as proved in the next
theorem. 

\th Theorem 7.1|If $\alpha={v\choose w}$ is a well-factorized
circuit, then
$$
(\exc_\ell,\den_\ell)\, \alpha=(\des_\ell,\maj_\ell)\,
\alpha.\eqno(7.3)
$$
\finth

\def\trait{\vrule height 5.5pt depth 16pt width.4pt}
\def\minitrait{\vrule height 6pt depth 6pt width.4pt}
\def\miniminitrait{\vrule height 6pt depth 3.5pt width.4pt}
\def\minimoderetrait{\vrule height 6pt depth 4pt width.4pt}
\def\minimoyentrait{\vrule height 6pt depth 15pt width .4pt}
\def\autretrait{\vrule height 8.5pt depth 3pt width .4pt}

{\it Proof}\pointir
Let
$\left(\matrice{a_2&\ldots &a_{i+1}&a_{i+2}&\ldots&
a_k&a_1\cr
a_1&\ldots &a_{i}&a_{i+1}&\ldots&
a_{k-1}&a_k\cr}\right)$
and $\left(\matrice{b_2&\ldots\cr
b_1&\ldots\cr}\right)$
be two successive $\preceq$-dominated cycles in the
increasing factorization of~$\alpha$, so that
$$
\alpha
=\left(\matrice{\ldots&a_2&\ldots
&\smash{\trait\overline{ a_{i+1}}\minitrait}&a_{i+2}&\ldots&
a_k&\smash{\minimoyentrait
\overline{a_1}\miniminitrait}&b_2&\ldots\cr
\ldots&a_1&\ldots &\underline{\kern 5pt
a_{i\vphantom{+}}\kern5pt}&
\kern-4pt\underline{\overline{\kern4pt
a_{i+1}}}\minimoderetrait&\ldots&
a_{k-1}&\underline{\kern1pt a_k\kern1pt}&
\kern-3.5pt\underline{\overline{\kern3.5pt
b_1}}\autretrait&\ldots\cr}\right).
$$
Inside each $\preceq$-dominated cycle  a pair like
$(a_i,a_{i+1})$ occurs horizontally and vertically, so that 
there is a $\ell$-descent $a_ia_{i+1}$ if and only if there
is a $\ell$-excedance $a_{i+1}\choose a_i$. Furthermore, the
letters in~$w$ to the left of~$a_i$ that fall into the
cyclic interval $\il a_i,a_{i+1}\ir$ bring the same contribution
in both $\maj_\ell \alpha$ and $\den_\ell \alpha$. If
$a_{i+1}\choose a_i$ is the $j$-th biletter of~$\alpha$ (when
read from left to right), we have $p_j=q_j$ in the notations
used in (7.2) and~(7.3).

\goodbreak
At the end of a $\preceq$-dominated cycle we have to compare
the contributions of the horizontal pair $(a_k,b_1)$ with the
contribution of the vertical pair $a_1\choose a_k$. But
$a_k \prec a_1\preceq b_1$ by definition of the increasing
factorization. If $b_1$ is large, then $a_k$ and $a_1$ are also
large and we have $a_k>a_1\ge b_1$, so that the
letter~$a_k$ creates an $\ell$-excedence and an
$\ell$-descent. If $b_1$ is small, then
$a_k>a_1$ is an $\ell$-excedance if and only if $a_k$ is large.
This is also equivalent to saying that $a_k>b_1$ is an
$\ell$-descent.

Now if $a_1=b_1$, the two cyclic intervals $\il a_k,b_1\ir$
and $\il a_k, a_1\ir$ that serve in the calculation of $\maj_\ell
\alpha$ and $\den_\ell\alpha$ are identical. 
If $a_1\prec b_1$, there is no letter~$x$ in~$w$ to the
left of~$b_1$ such that $a_1\prec x\preceq b_1$. Four cases are to
be considered: (1) $a_1,b_1,a_k$ all small; (2) $a_1,b_1$ small,
$a_k$ large; (3) $a_1,b_1,a_k$ all large; (4) $a_1$ large, $b_1$
small, $a_k$ large. For any two sets $A, B$ let $A+B$ denote the
union of~$A$ and~$B$ when the intersection $A\cap B$ is empty.
In cases~(1) and~(2) we have
$$\displaylines{
\il a_k,b_1\ir=\il a_k,a_1\ir+\{x:a_1\prec x\preceq b_1\},\cr
\noalign{\hbox{while}}
\il a_k,a_1\ir=\il a_k,b_1\ir+\{x:a_1\prec x\preceq b_1\}\cr
}
$$
in cases (3) and (4). Consequently there
are as many letters to the left of~$a_k$ falling into the interval
$\il a_k,b_1\ir$ as letters falling into $\il a_k, a_1\ir$.

Suppose that $\alpha$ is of length~$m$ and take up again the
notations of (7.1) and (7.2). We still have to compare
the pairs $(q_m,q_{m+1})$ and $(p_m,p_{m+1})$. 
Let $y_m\choose x_m$ be the rightmost biletter of
$\alpha$. If $w$ contains small letters, the
letter~$y_m$ is necessarily equal to the greatest small letter
occurring in~$w$. Hence the cyclic intervals $\il x_m,s\ir$
used for evaluating $q_m$ and $\il x_m,y_m\ir$ for evaluating
$p_m$ are equal. If $w$ contains only large letters, $y_m$ is
equal to the smallest large letter in~$w$ and again the
previous two cyclic intervals are equal. Finally,
$p_{m+1}=q_{m+1}$, as both coefficients count the large letters
in~$w$.\cqfd

\section 8. Statistics on words|To get the definitions of
$\des_\ell w$, $\maj_\ell w$, $\exc_\ell w$ and $\den_\ell w$ for
a word~$w$ in the alphabet ${}_sX_\ell$ we simply form the
{\it standard circuit} $\Gamma(w)$ and put
$$\eqalign{
\des_\ell w=\des_\ell \Gamma(w),&\quad
\maj_\ell w=\maj_\ell \Gamma(w),\cr
\exc_\ell w=\exc_\ell \Gamma(w),&\quad
\den_\ell w=\den_\ell \Gamma(w).\cr}\eqno(8.1)
$$
The definitions given for $\des_\ell w$ and $\exc_\ell w$ are
identical with the definitions given in the introduction. The
definition of $\den_\ell w$ is new, while that of
$\maj_\ell w$ differs from the definition given in the
introduction.

\th Theorem 8.1|The statistic $\maj_\ell w$ given in $(8.1)$ and
the statistic $\maj_\ell w$ given in the introduction are identical.
\finth

As can be found in [\Hajd] for $\ell=0$ and in [\ClFojf] for an
arbitrary~$\ell$, Theorem~8.1 is easy to prove by induction on
the length of the word.

\medskip
The $\ell$-{\it excedance index} of~$w$ was defined in the
introduction as the sum, $\excindex_\ell w$, of all~$i$ such that
$i$ is a $\ell$-excedance in~$w$. When a certain correcting term
is added to $\excindex_\ell w$, we get the second definition of
$\den_\ell w$. To fully describe that correcting term we need
the further definitions. For each word~$w=x_1x_2\ldots x_m$ let
$$\eqalign{
\inv_\ell w&=\#\{1\le i<j\le m: x_i>x_j\ {\rm or}\ x_i=x_j\ge
s+1\}\cr
&\kern3.5cm{}+\#\{1\le i\le m : x_i\ge s+1\},\cr
\imv_\ell w&=\#\{1\le i<j\le m : x_i>x_j\ {\rm or}\ x_i=x_j\le
s\}.\cr}\eqno(8.2)
$$
Notice that $\inv_0=\inv$ (the usual number of inversions) and
$\imv_0=\imv$ (the number of weak inversions). 

Now if $\exc_\ell w=e$, let $i_1<i_2<\cdots <i_e$ be the
increasing sequence of the $\ell$-excedances of~$w$ and let
$j_1<j_2<\cdots <j_{m-e}$ be the complementary sequence.
Form the two subwords
$$
\Exc_\ell w=x_{i_1}x_{i_2}\ldots x_{i_e}\,;\qquad
\Nexc_\ell w=x_{j_1}x_{j_2}\ldots x_{j_{m-e}}.
$$
Then the $\ell$-{\it Denert statistic} of $w$ is also defined to
be
$$\displaylines{\hfill
\den_\ell w=\excindex_\ell w
+\imv_\ell\Exc_\ell w+\inv_\ell \Nexc_\ell w.
\hfill\llap{(8.3)}\cr
\noalign{\hbox{For $\ell=0$ we simply speak of the {\it Denert
statistic}}}
\hfill\den w=\den_0 w.\hfill\llap{(8.4)}\cr}
$$

\th Theorem 8.2|For every word~$w$ the two definitions of
$\den_\ell w$ occurring in $(8.1)$ and $(8.3)$ are identical.
\finth

The concept of the Denert statistic is due to Denert [\Denja].
The equivalence between definitions (8.1) and (8.3) when
$\ell=0$ and when $w$ is a permutation (without repetitions)
was already given in [\FoZeja]. Another proof of that result
appeared in [\Cljf]. Theorem~8.2 that states the equivalence of
those two definitions for arbitrary words was proved in [\Hajd] for
$\ell=0$ and in [\Hajf] for an arbitrary~$\ell$.

\section 9. Equidistribution properties|The fundamental
properties of the commutations $\Com_{CF}$ and $\Com_H$
introduced in section~4 are stated in the next theorem. The
underlying alphabet is ${}_sX_\ell$.

\th Theorem 9.1|The commutation ``$\Com$" being given, let 
$\alpha=(v,w)$ be a circuit of length~$m$ and let
$\alpha'=(v',w')=\Com(v,w;i)$ $(1\le i\le m-1)$ be the image of
that pointed circuit under the commutation ``$\Com$."

If $\Com=\Com_{CF}$, then
$$\displaylines{\hfill
\exc_\ell{v'\choose w'}
=\exc_\ell{v\choose w}.\hfill\llap{\rm(9.1)}\cr
\noalign{\hbox{\indent If $\Com=\Com_H$, then}}
\hfill
(\exc_\ell,\den_\ell)\,{v'\choose w'}
=(\exc_\ell,\den_\ell)\,{v\choose w}.\hfill\llap{\rm (9.2)}\cr}
$$
\finth

\goodbreak
Property (9.1) is evident, as biletters are preserved when the
commutation ``$\Com_{CF}$" is applied. With notations slightly
different (9.2) has been proved in [\Hajd, Lemma~5.2] in
the case $\ell=0$  and for arbitrary~$\ell$ in [\ClFojf,
Lemma~3.6]. We do not reproduce the proof here, as it
essentially consists of a lengthy but easy verification.

\th Theorem 9.2|The transformations 
$$\eqalign{
\Phi&:b\mapsto {}_r{\bf T}_0(b,\Com_{CF}),\kern15pt
\Phi^q:b\mapsto {}_r{\bf T}_0(b,\Com_H),\cr
{}_s\Phi_\ell&:b\mapsto {}_s{\bf T}_\ell(b,\Com_{CF}),\quad
{}_s\Phi_\ell^q:b\mapsto{}_s{\bf T}_\ell(b,\Com_H).\cr}
$$ 
defined in $(5.2)$ have the equidistribution
properties 
$$\eqalign{
\exc(w)&= \des\,\Phi(w),\kern28pt
(\exc,\den)\, w= (\des,\maj)\, \Phi^q(w),\cr
\exc_\ell(w)&= \des_\ell\, {}_s\kern-1pt
\Phi_\ell(w),\kern10pt
(\exc_\ell,\den_\ell)\, w= (\des_\ell,\maj_\ell)\, {}_s\kern-1pt
\Phi_\ell^q(w).\cr}
$$
\finth

{\it Proof}\pointir
With each of those transformations we start with a word~$b$,
form the standard circuit $\Gamma(b)={\overline b\choose b}$
and apply a well-defined sequence of Cartier-Foata
commutations (resp. of contextual commutations) to reach a
well-factorized circuit $\Delta(c)$.

If the commutation used is the Cartier-Foata commutation, we
have
$$\eqalignno{
\exc_\ell(b)&=\exc_\ell{\overline b\choose b}
&\hbox{[by definition of ``$\exc_\ell$"]}\cr
&=\exc_\ell\,\Delta(c)
&\hbox{[because of (9.1)]}\cr
&=\des_\ell \,\Delta(c)
&\hbox{[by Theorem 7.1]}\cr
&=\des_\ell(c).
&\hbox{[by definition of ``$\des_\ell$."]}\cr
\noalign{\hbox{If we use the contextual commutation, we have the
properties}}
(\exc_\ell,\den_\ell)\,(b)
&=(\exc_\ell,\den_\ell)\,{\overline b\choose b}
&\hbox{[by definition of ``$(\exc_\ell,\den_\ell)$"]}\cr
&=(\exc_\ell,\den_\ell)\,\Delta(c)
&\hbox{[because of (9.2)]}\cr
&=(\des_\ell,\maj_\ell)\,\Delta(c) 
&\hbox{[by Theorem 7.1]}\cr
&=(\des_\ell,\maj_\ell)\,(c).\qed\kern4cm
&\hbox{[by definition of ``$\maj_\ell$."]}\cr}
$$

\bigskip
{\sl Acknowledgements}\pointir
The authors should like to thank the referee for his
careful reading.

\vglue 1cm
\vskip1cm plus .2cm minus .2cm


{
%%\eightpoint
\centerline{\bf REFERENCES}
\vskip 10pt

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

\article \Cafj|L. Carlitz|Eulerian numbers and polynomials|Math.
Magazine|33|1959|247--260|

\article \Cahb|L. Carlitz|A combinatorial property of
$q$-Eulerian numbers|Amer. Math. Monthly|82|1975|51--54|

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

\article \Cljf|R. J. Clarke|A short proof of a result of Foata
and Zeilberger|Adv. Appl. Math.|16|1995|129--131|

\article \ClFoje|R. J. Clarke and D.
Foata|Eulerian Calculus, I: Univariable Statistics|Europ. J.
Combinatorics|15|1994|345--362|

\article \ClFojf|R. J. Clarke and D.
Foata|Eulerian Calculus, II: An Extension of Han's
Fundamental Transformation|Europ. J.
Combinatorics|16|1995|221--252|

\article \ClFojfa|R. J. Clarke and D.
Foata|Eulerian Calculus, III: The Ubiquitous Cauchy Formula|Europ.
J. Combinatorics|16|1995|329--355|

\article \Denja|M. Denert|The genus zeta function of
hereditary orders in central simple algebras over global
fields|Math. Comp.|54|1990|449--465|

\article \Fogf|D. Foata|Etude alg\'ebrique de certains
probl\`emes d'analyse combinatoire et du calcul des
probabilit\'es|Publ. Inst. Statist. Univ. Paris|14|1965|81--241|

\article \FoZeja|D. Foata and D. Zeilberger|Denert's
permutation statistic is indeed Euler-Mahonian|Studies in
Appl. Math.|83|1990|31--59|

\article \Hajd|G. N. Han|Une transformation fondamentale
sur les r\'earrangements de mots|Advances in 
Math.|105|1994|26--41|

\article \Hajf|G. N. Han|The $k$-Extension of a Mahonian
Statistic|Adv. Appl. Math.|16|1995|297--305|

\livre \Knhd|D. E. Knuth|The Art of Computer
Programming,  {\rm vol.~3}, Sorting and
Searching|Addison-Wesley, Reading,  {1973}|

\divers \Knutha|D. E. Knuth|Private communication,
{\oldstyle 1996}|

\livre \Loid|M. Lothaire|Combinatorics on
words|Reading, Addison-Wesley, $1983$ 
({\sl Encyclopedia of Math. and its Appl.}, {\bf 17})|

\article \Macbd|P. A. MacMahon|The indices of
permutations and the derivation therefrom of functions of
a single variable associated with the permutations of any
assemblage of objects|Amer. J. Math.|35|1913|314--321|

\divers \Machi|P. A. MacMahon|``Collected
Papers, vol.~1" [G.E. Andrews, ed.],
Cambridge, Mass., The M.I.T. Press, 1978|

\livre \Macbf|P. A. MacMahon|Combinatory
Analysis, {\rm vol.~1}|Cambridge, Cambridge Univ. Press,
1915 (Reprinted by Chelsea, New York, 1955)|


}



\bye
