%\input tex8bits
\catcode'32=9
\magnification=1200

% particularite du pilote canon

\voffset=1cm
\hoffset=0cm
%\hoffset=1cm
\font\tenpc=cmcsc10
%\font\eightpc=cmcsc8

% 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

%���������������������� 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}, t.\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�s 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.$}}


\catcode`\@=12

%end format

%some macros from LaTeX

\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

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



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

\def\boucle{\vbox{\offinterlineskip
\leftput(0,4){\vector(0,-1){3}}
\segment(0,0)\dir(-1,1)\long{4}
\segment(-4,4)\dir(1,0)\long{4}
}}

%end of LaTeX macros
\auteurcourant={D. FOATA}
\titrecourant={COMMUTATION ET R\'EARRANGEMENTS}

%some local macros
\def\des{\mathop{\rm des}\nolimits}
\def\maj{\mathop{\rm maj}\nolimits}
\def\imaj{\mathop{\rm imaj}\nolimits}
\def\den{\mathop{\rm den}\nolimits}
\def\inv{\mathop{\rm inv}\nolimits}
\def\exc{\mathop{\rm exc}\nolimits}
\def\pre{\mathop{\rm pre}\nolimits}
\def\[{[\![}
\def\]{]\!]}

\catcode`\@=11
\def\petitematrice#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

\vglue44pt



\centerline{\bf COMMUTATION ET R\'EARRANGEMENTS,}
\vskip 5pt
\centerline{\bf HIER ET AUJOURD'HUI}
\vskip 2.8 mm
\centerline{\sevenrm PAR}
\vskip 2.8mm
\centerline{{\petcap Dominique} FOATA} 
\vskip 24 pt plus 6pt
\rightline{\it en hommage \`a Pierre CARTIER\qquad}
\section 1. Introduction|On ne s'\'etonnera pas de trouver 
le nom de Pierre \pc CARTIER| associ\'e aux probl\`emes de nature
combinatoire ou algorithmique. Plusieurs de ses expos\'es au
S\'eminaire Bourbaki ont port\'e sur ces sujets. D\'ej\`a en 1962
(\cf. [Ca62]), il expliquait les incidences de l'identit\'e de
Spitzer dans les fluctuations de sommes de variables
al\'eatoires ; plus r\'ecemment (\cf. [Ca80, Ca82, Ca91]), il
traitait d'arrangements d'hyperplans, d'alg\`ebre classique
avec le renouveau de l'\'etude des fonctions sym\'etriques et
enfin des travaux de \pc ZEILBERGER| sur la d\'emonstration
``automatique" des identit\'es hyperg\'eom\'etriques.

Plus \'etonnant est de trouver son nom associ\'e
au {\it parall\'elisme}. En fait, comme il sera expliqu\'e ici, la
base th\'eorique de cette discipline a pris sa source dans le
m\'emoire ``Probl\`emes combinatoires de
commutation et r\'earrangements," que \pc CARTIER| et
moi-m\^eme avions r\'edig\'e \`a la fin des ann\'ees
soixante [CaFo79]. J'ai repris une partie de ce titre ici, car,
derni\`erement, les techniques d\'evelopp\'ees dans ce
m\'emoire ont \'et\'e reprises par le jeune Guo-Niu \pc HAN|
dans une \'etude de statistiques bivari\'ees sur une classe
de r\'earrangements de mots, lui permettant notamment de
prouver une conjecture de \pc DENERT| sur l'\'evaluation de
la fonction z\^eta d'ordres h\'er\'editaires.

Le but de cet article est de montrer comment et dans quels
domaines les probl\`emes de commutation sont apparus et
quelles sont les techniques qui ont \'et\'e utilis\'ees pour les
r\'esoudre, enfin comment  \pc HAN|
[Ha92] s'est servi de ces techniques de commutation pour
prouver la conjecture de \pc DENERT|.


 \section 2. Parall\'elisme|Nous reprenons ici
l'exemple trait\'e par Volker \pc DIEKERT|~[Die] dans son
trait\'e sur la combinatoire des traces. Consid\'erons une
base de donn\'ees compos\'ee d'un ensemble de donn\'ees,
suppos\'ees enti\`eres, $x$, $y$, $z$, \dots\ et d'un ensemble
de transactions pouvant \^etre ex\'ecut\'ees simultan\'ement
ou non :
$a$, $b$, $c$, \dots\ Ces transactions agissent sur chaque
base de la fa\c con suivante :
$$\displaylines
{(a)\ x:=x+y\,; \qquad 
(b)\ x:=w+x\,; \qquad 
(c)\ y:=y+z\,; \qquad 
(d)\ w:=2y+z\,; \cr 
(e)\ z:=y+2z\,; \qquad 
(f)\ x:=w+x+y\,; \qquad 
(g)\ x:=w+x+2y.\cr}
$$
Les transactions qui ne peuvent \^etre ex\'ecut\'ees
simultan\'ement sont celles qui contiennent des variables en
commun, par exemple $(a)$ et $(b)$. On peut donc b\^atir un
diagramme de {\it d\'ependance} entre ces
transactions, comme indiqu\'e dans la figure :


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

\midinsert

\newbox\boxdiag

\setbox\boxdiag=\vbox{\vskip 15mm
\offinterlineskip 
\centerput(0,0){$a$}
\centerput(0,30){$b$}
\centerput(15,15){$f$}
\centerput(30,15){$g$}
\centerput(44,0){$c$}
\centerput(44,30){$d$}
\centerput(58,15){$e$}
%les segment obliques :
\segment(1,2)\dir(0,1)\long{26}
\segment(2,2)\dir(1,1)\long{12}
\segment(2,28)\dir(1,-1)\long{12}
\segment(3,1)\dir(2,1)\long{25}
\segment(17,15)\dir(1,0)\long{9}
\segment(3,29)\dir(2,-1)\long{24}
\segment(3,0)\dir(1,0)\long{38}
\segment(3,30)\dir(1,0)\long{39}
\segment(17,13)\dir(2,-1)\long{24}
\segment(17,17)\dir(2,1)\long{24}
\segment(33,13)\dir(1,-1)\long{11}
\segment(33,17)\dir(1,1)\long{11}
\segment(45,2)\dir(0,1)\long{25}
\segment(46,2)\dir(1,1)\long{11}
\segment(46,28)\dir(1,-1)\long{11}
}

\vskip1.5cm
$$
\hbox{\box\boxdiag\hskip55mm}
$$

\endinsert




Deux suites de transactions conduisant aux m\^emes
op\'erations sur les donn\'ees sont dites \'equivalentes. Par
exemple, les deux suites
$p=adbcafg$ et $p'=dacbafg$ sont \'equivalentes, puisque l'on
peut faire simultan\'ement les transactions $a$ et $d$, d'une
part, et $b$ et $c$, d'autre part.  Durant les ann\'ees 70, les
sp\'ecialistes du parall\'elisme \'etudiant le
comportement non-s\'equentiel de syst\`emes concurrents
ont donc cherch\'e un mod\`ele math\'ematique
permettant de manipuler non plus ces suites de transactions, mais
les {\it classes d'\'equivalence} de telles suites, qu'ils ont appel\'ees
{\it traces}. Ils ont cherch\'e \`a repr\'esenter les traces par des
graphes orient\'es. Si une trace est de
longueur~$n$, c'est-\`a-dire si elle est compos\'ee de suites
de longueur~$n$, on lui associe un {\it graphe} de $n$ sommets $v_1$,
$v_2$, \dots~, $v_n$, dont les \'etiquettes sont prises dans l'ensemble
des transactions ; de plus, on convient de joindre le sommet $v_i$ au
sommet $v_j$ par un arc, si $i<j$ et si les \'etiquettes de $v_i$ et
$v_j$ sont {\it d\'ependantes}. Par exemple, pour $p=adbcafg$, on
obtient le graphe dit de d\'ependance :

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


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

\midinsert

\newbox\boxtrace

\setbox\boxtrace=\vbox{\vskip
25mm\offinterlineskip 
\centerput(0,0){$d$}
\centerput(30,0){$c$}
\centerput(0,30){$a$}
\centerput(30,30){$b$}
\centerput(60,15){$a$}
\centerput(80,15){$f$}
\centerput(100,15){$g$}
%
\fleche(2,1)\dir(1,0)\long{26}
\fleche(2,2)\dir(1,1)\long{26}
\fleche(2,30)\dir(1,-1)\long{27}
\fleche(2,31)\dir(1,0)\long{26}
\fleche(32,30)\dir(2,-1)\long{25}
\fleche(32,2)\dir(2,1)\long{25}
\fleche(62,16)\dir(1,0)\long{16}
\fleche(82,16)\dir(1,0)\long{16}
}

\vskip.4cm
$$
\hbox{\box\boxtrace\hskip95mm}
$$

\endinsert



Il est clair que le graphe de d\'ependance caract\'erise la trace. Il
sugg\`ere, de plus, un moyen de faire ex\'ecuter les transactions {\it
en parall\`ele} : on ex\'ecute, d'abord les transactions qui sont
minimales dans le graphe de d\'ependance, puis retirant celles-ci du
graphe, celles qui sont minimales dans le graphe r\'esultant et ainsi
de suite. Pour le graphe de d\'ependance ci-dessus on obtient une suite
{\it en parall\`ele} de cinq ensembles de transactions, \`a savoir :
$$
\{a,d\}\,\{c,b\}\,\{a\}\,\{f\}\,\{g\}.
$$
On va voir, dans un instant, que chaque trace est caract\'eris\'ee par
une telle suite.

\section 3. Mono\"ides soumis \`a des relations de commutation|Pour
rendre compte des manipulations ci-dessus, on introduit un couple
$(X,D)$, o\`u $X$ est un ensemble non-vide, appel\'e {\it alphabet}
 et o\`u $D$ est une relation sur $X$, qui est r\'eflexive et
sym\'etrique. On forme ensuite le mono\"ide libre $X^*$ engendr\'e
par~$X$, compos\'e de tous les mots $w=x_1x_2\ldots x_m$, o\`u les
$x_i$ sont des \'el\'ements de~$X$. L'op\'eration sur $X^*$ est le
produit de juxtaposition des mots. On suppose l'existence d'un mot
vide not\'e~$\varepsilon $. 

Posons $I=X\times X\setminus D$ et notons $\equiv_I$ la relation
d'\'equivalence sur $X^*$ engendr\'ee par les couples de la forme
$(uxyv,uyxv)$, o\`u $u$ et $v$ sont des mots de $X^*$ et o\`u
$(x,y)\in I$. Cette relation d'\'equivalence est compatible avec le
produit dans~$X^*$. Le mono\"ide quotient
$X^*/\equiv_I$ est appel\'e {\it mono\"ide libre partiellement
commutatif} ou {\it mono\"ide des traces}, ou encore {\it mono\"ide
soumis \`a des relations de commutation}. On le note $M(X,D)$. 

D\'esignons par $[x]$ la classe d'\'equivalence d'une lettre $x$
de~$X$. L'appli\-ca\-tion $x\mapsto [x]$ est injective et $M(X,D)$ est
engendr\'e par l'ensemble des \'el\'ements de la forme $[x]$

On dit qu'une partie $F$ de $X$ est un {\it pas \'el\'ementaire}, si elle
est finie, non-vide, et si deux de ses \'el\'ements commutent toujours.
On pose dans ce cas $[F]=\prod _{x\in F} [x]$. Comme tous les
\'el\'ements de $F$ commutent, la notation $[F]$ d\'efinit bien une
trace.

Le fait que toute trace est caract\'eris\'ee par son graphe de
d\'ependance  est exprim\'e dans le th\'eor\`eme suivant.

\th Th\'eor\`eme 1|Toute trace s'exprime, de fa\c con unique, comme un
produit dans $M(X,D)$, de pas \'el\'ementaires
$[F_1]\ldots [F_r]$ $(r\ge 0)$ tels que  pour tout $i=2,\dots,r$ et
tout $b\in F_i$, il existe  un $a\in F_{i-1}$ satisfaisant
$(a,b)\in D$. \finth

Les mono\"ides libres partiellement
commutatifs  sont
l'objet de nombreuses  \'etudes dans les milieux de l'informatique
th\'eorique. Le pr\'ec\'edent th\'eor\`eme, par exemple, a \'et\'e
popularis\'e par les sp\'ecialistes du parall\'elisme (\cf. [Maz77],
[Du86], [Di90]). La notion de commutation partielle a  \'et\'e
r\'ecemment exploit\'ee par \pc DUCHAMP| et \pc KROB| [DuKr90] pour
introduire les groupes libres partiellement commutatifs, les
alg\`ebres de Lie partiellement commutatives, l'alg\`ebre libre
partiellement commutative. Pourtant, lorsque ces objets ont \'et\'e
introduits par \pc CARTIER|-\pc FOATA| [CaFo69], rien ne laissait
pr\'evoir une telle popularit\'e. Il s'agissait de d\'egager l'outil
math\'ematique qui sous-tendait les probl\`emes de
r\'earrangement de suites et l'\'etablissement de certaines
identit\'es d'inversion. Le pr\'ec\'edent th\'eor\`eme, par exemple,
permet imm\'ediatement d'\'etablir le r\'esultat suivant :

\th Th\'eor\`eme 2|Dans l'alg\`ebre ${\bboard Z}\langle\langle
M\rangle\rangle$ des s\'eries formelles du mono\"ide des traces
$M=M(X,D)$, l'inverse de la s\'erie caract\'eristique 
$\sum t$ $(t\in M)$ est donn\'e par la s\'erie
$1+\sum (-1)^{\left |F\right |}[F]$, o\`u $F$ varie dans l'ensemble des
pas \'el\'ementaires.
\finth

A son tour, le pr\'ec\'edent th\'eor\`eme a permis de trouver des
{\it versions non-commutatives} au ``Master Theorem" de \pc MAC|\pc
MAHON| qui s'\'enonce comme suit :

\th Th\'eor\`eme 3|Soient $X_1$, $X_2$, \dots, $X_n$ $n$ variables qui
commutent et $B=(b(i,j))$ $(1\le i,j\le n)$ une matrice \`a
coefficients dans un anneau. Pour tout mon\^ome 
$h=X_1^{c_1}\ldots X_n^{c_n}$ notons $\nu (h)$ le coefficient du
mon\^ome~$h$ dans le d\'eveloppement de
$$\displaylines{
\Bigl(\sum _jb(1,j)X_j\Bigr)^{c_1}\ldots \Bigl(\sum
_jb(n,j)X_j\Bigr)^{c_n}.\cr
\noalign{\hbox{On a alors l'identit\'e :}}
\left|\matrix{1-b(1,1)X_1&\ldots&-b(1,n)X_n\cr
\ldots&\ldots&\ldots\cr
-b(n,1)X_1&\ldots&1-b(n,n)X_n\cr}\right|^{-1}=\sum h \nu (h).\cr}
$$
\finth

Naturellement ce th\'eor\`eme 3 peut se d\'emontrer de bien des fa\c
cons, et \pc CARTIER| dans un s\'eminaire \`a Strasbourg en
1971 [Ca71] en avait donn\'e neuf d\'emonstrations. Cependant, \pc
MAC|\pc MAHON| l'utilisant pour d\'emontrer un r\'esultat statistique sur
les suites de nombres, r\'esultat qu'on pouvait \'etablir par d'autres
techniques, il importait de voir si ces techniques ne pouvaient pas
permettre de trouver aussi des extensions
{\it non-commutatives} du Master Theorem de MacMahon (\cf. [CaFo69]).

\section 4. R\'earrangements de suites|Supposons que l'alphabet
$X$ est totalement ordonn\'e. A tout mot croissant
$u=y_1y_2\ldots y_m$ on fait correspondre la classe $R(u)$ de
tous les {\it r\'earrangements} du mot~$u$, c'est-\`a-dire l'ensemble
de tous les mots de la forme $y_{i_1}y_{i_2}\ldots y_{i_m}$, o\`u
$i_1i_2\ldots i_m$ est une permutation de $12\ldots n$. Si
$w=x_1x_2\ldots x_m$ est un mot de cette classe, son {\it
r\'earrangement croissant}, \`a savoir~$u$ lui-m\^eme, est encore
not\'e $\overline w=u$. Les statistiques suivantes sont classiques : 
$$\displaylines{
\des w=\left |\{i\mid x_i>x_{i+1}\}\right |\,;\qquad
\exc w=\left |\{i\mid x_i>y_i\}\right |\,;\cr
\maj w=\sum \{i\mid x_i>x_{i+1}\}\,;\qquad
\inv w=\left |\{i<j\mid x_i>x_j\}\right |.\cr}
$$
Les statistiques ``des," ``exc," ``maj" et ``inv" sont traditionnellement
appel\'ees {\it nombre de descentes}, {\it nombre d'exc\'edances}, {\it
indice majeur}, {\it nombre d'inversions}.


 Le th\'eor\`eme suivant est d\^u \`a \pc MAC|\pc MAHON| (\cf.
[CaFo69] :

\th Th\'eor\`eme 4|Dans toute classe de r\'earrangements $R(u)$,
pour tout nombre~$k\ge 0$, il y a autant de mots $w$ tels que 
$\exc w=k$ que de mots $w'$ tels que $\des w'=k$.
\finth

Ce th\'eor\`eme suppose donc que pour toute classe $R(u)$ on doit
pouvoir construire une bijection~$\Phi$ de $R(u)$ sur elle-m\^eme
satisfaisant la propri\'et\'e
$$
\exc w=\des\Phi(w),
$$
identiquement.

Une telle bijection est donn\'ee dans le m\'emoire de \pc
CARTIER|-\pc FOATA| [CaFo69] et repose sur les propri\'et\'es des
mono\"ides de traces. C'est m\^eme \`a cause de la recherche de cette
bijection que ces mono\"ides ont \'et\'e introduits. On s'y prend
comme suit.

On part de l'alphabet $X\times X$, les lettres de l'alphabet \'etant
repr\'esent\'ees par des matrices \`a deux lignes
${\bf x}=\bigl({x'\atop x}\bigr)$. La relation de {\it d\'ependance} que
l'on s'impose est constitu\'ee par l'ensemble des bilettres
$\bigl({\bf x}=\bigl({x'\atop x}\bigr),{\bf y}=\bigl({y'\atop
y}\bigr)\bigr)$ telles que $x'=y'$. Autrement dit, deux bi-lettres
commutent si et seulement si leurs lettres sur la ligne {\it du haut}
sont diff\'erentes. Le mono\"ide soumis \`a ces relations de
commutation est appel\'e {\it mono\"ide des flots} et not\'e $F(X)$. 
Comme pr\'ec\'edemment, la classe contenant le bi-mot
${\bf w}=\bigl({w'\atop w}\bigr)$ est 
not\'ee~$[{\bf w}]=\bigl[{w'\atop w}\bigr]$. Lorsque le
mot~$w'$ est un r\'earrangement du mot~$w$, la classe d'\'equivalence
$\bigl[{w'\atop w}\bigr]$ est appel\'ee {\it circuit}. Il est clair que
l'ensemble $C(X)$ de tous les circuits est un sous-mono\"ide de $F(X)$,
appel\'e {\it mono\"ide des circuits}.

Pour tout mot $w=x_1x_2\ldots x_m$ de $X^*$, on note $\delta w$ le
cyclage circulaire $\delta w=x_2x_3\ldots x_mx_1$. Le mot $w$ est
dit {\it domin\'e}, si sa premi\`ere lettre, not\'ee $\pre(w)$, est
strictement sup\'erieure \`a toutes ses autres lettres. Un
circuit ${\bf c}$ est {\it domin\'e}, s'il contient un bimot de la forme
$$
{\bf w}=\left ({ \delta w\atop w}\right ),
$$
avec $w$ domin\'e. Tout circuit domin\'e contient un et un seul
bimot de cette forme, appel\'e  {\it repr\'esentant
canonique} du circuit domin\'e. On pose alors $\pre({\bf c})=\pre(w)$.

Soient $x$, $y$ deux lettres de $X$, 
$[{\bf c}]=\left [\matrix{  w'\cr w\cr}\right ]
=\left [\matrix{x'_1\,x'_2\,\ldots\,x'_m\cr
x_1\,x_2\,\ldots\,x_m\cr}\right ]$ un circuit. On note
$\exc_{x,y} ({\bf c})$ le nombre d'indice~$i$ tels que
$1\le i\le m$ et $x'_i=x$, $x_i=y$. On note \'egalement
$\des_{x,y}(w)$ le nombre d'indices~$i$ tels
que $1\le i\le m-1$ et $x_i=y$, $x_{i+1}=x$. Autrement dit,
$\exc_{x,y} ({\bf c})$ est le nombre d'occurrences de bilettres 
(verticales)
$\bigl[{x\atop y}\bigr]$ dans {\bf c} et
$\des_{x,y}(w)$ le nombre de facteurs $yx$ dans~$w$ :
$$
[{\bf c}]
=\left [\matrix{\ldots x \ldots\cr
\ldots y \ldots\cr}\right ]
=\left [\matrix{\ldots \ldots \ldots\cr
\ldots y x \ldots\cr}\right ]
$$




Pour permettre un parall\`ele avec le mono\"ide de Han qui sera
introduit plus loin, on va num\'eroter les propri\'et\'es utiles du
mono\"ide des circuits $1_c$, $2_c$, \dots

\th Propri\'et\'e $1_c$|Tout circuit ${\bf c}$ a un et un seul repr\'esentant
de la forme $\bigl[{\overline  w\atop w}\bigr]$, o\`u $\overline w$ est
le r\'earrangement croissant de~$w$.
\finth

\th Propri\'et\'e $2_c$|Tout circuit non vide {\bf c} admet une
factorisation unique de la forme
$$
{\bf c}={\bf d}^1 {\bf d}^2\ldots {\bf d}^r,
$$
o\`u les facteurs ${\bf d}^i$ sont des circuits domin\'es avec la
condition 
$$
\pre({\bf d}^1)\le \pre({\bf d}^2)\le  \cdots \le \pre({\bf d}^r).
$$
\finth


\th Propri\'et\'e $3_c$|Si ${\bf c}$ est un circuit domin\'e,
dont le repr\'esentant canonique est $\bigl({\delta w\atop w}\bigr)$, on a
pour tout couple $(x,y)$ tel que $x<y$ la propri\'et\'e $$
\exc_{x,y}({\bf c})=\des_{x,y}(w).
$$
\finth



\th Propir\'et\'e $4_c$|Soit
$
{\bf c}={\bf d}^1 {\bf d}^2\ldots {\bf d}^r
$
la factorisation (unique) d'un circuit {\bf c} en circuits domin\'es
(\cf. \pc PROPRI\'ET\'E|~$2_c$), dont les mots de la seconde ligne
sont $u^1$, $u^2$, \dots~, $u^r$. Alors pour tout $x<y$ on a : 
$$
\des_{x,y}(u^1u^2\ldots u^r)=\des_{x,y}(u^1)+\des_{x,y}(u^2)
+\cdots+\des_{x,y}(u^r). 
$$
\finth

La construction de la bijection $w\mapsto \Phi(w)$ est faite alors comme
suit : on part d'un mot $w$ auquel on associe, de fa\c con forc\'ement
unique, le circuit $\bigl[{\overline w\atop w}\bigr]$. Ce circuit se
factorise, d'apr\`es la \pc PROPRI\'ET\'E|~$2_c$ en un produit de circuits
domin\'es ${\bf d}^1{\bf d}^2\ldots {\bf d}^r$. Chaque circuit~${\bf d}^i$
domin\'e a un et un seul repr\'esentant $\bigl({\delta u^i\atop u^i}\bigr)$.
On d\'efinit alors $\Phi(w)$ comme \'etant le produit de juxtaposition
$$
\Phi(w)=u^1u^2\ldots u^r.
$$

\rem Exemple|Par exemple, partons du mot
$$
\displaylines{w=3\ 1\ 5\ 1\ 4\ 2\ 2\ 6\ 6\ 7\ 2\ 6\ 1\ 5\cr
\noalign{\hbox{dont le r\'earrangement croissant est :}}
\overline w= 1\ 1\ 1\ 2\ 2\ 2\ 3\ 4\ 5\ 5\ 6\ 6\ 6\ 7.\cr}
$$
D'apr\`es la \pc PROPRI\'ET\'E|~$1_c$, il lui correspond un unique circuit
$$
\left [{\overline w\atop w}\right ]=
\left[\vcenter{\halign{&\hfil$\;#\;$\hfil\cr
\bf 1&1&\bf 1&2&\bf 2&2&2&\bf 4&\bf 5&\bf 5&6&6&6&7\cr
\bf 3&1&\bf 5&1&\bf 4&2&2&\bf 6&\bf 6&\bf 7&2&6&1&5\cr
}}\right ].
$$
La factorisation de ce circuit en circuits domin\'es s'obtient en extrayant
ceux-ci de la droite vers la gauche, comme indiqu\'e ci-dessous :
$$\displaylines{\hskip 1.5cm
\left[\vcenter{\halign{&\hfil$\;#\;$\hfil\cr
\bf 1&1&\bf 1&2&\bf 2&2&3&\bf 4&\bf 5&6&6&6\cr
\bf 3&1&\bf 5&1&\bf 4&2&2&\bf 6&\bf 6&2&6&1\cr
}}\right ]
\left[\vcenter{\halign{&\hfil$\;#\;$\hfil\cr
\bf 5&7\cr
\bf 7&5\cr
}}\right ]\hfill\cr
\hskip 1.5cm
\left[\vcenter{\halign{&\hfil$\;#\;$\hfil\cr
\bf 1&1&2&\bf 2&2&3&\bf 4&6&6\cr
\bf 3&1&1&\bf 4&2&2&\bf 6&2&6\cr
}}\right ]
\left[\vcenter{\halign{&\hfil$\;#\;$\hfil\cr
\bf 5&\bf 1&6\cr
\bf 6&\bf 5&1\cr
}}\right ]
\left[\vcenter{\halign{&\hfil$\;#\;$\hfil\cr
\bf 5&7\cr
\bf 7&5\cr
}}\right ]\hfill\cr
\hskip 1.5cm
\left[\vcenter{\halign{&\hfil$\;#\;$\hfil\cr
\bf 1&1&2&\bf 2&2&3&\bf 4&6\cr
\bf 3&1&1&\bf 4&2&2&\bf 6&2\cr
}}\right ]
\left[\vcenter{\halign{&\hfil$\;#\;$\hfil\cr
6\cr
6\cr
}}\right ]
\left[\vcenter{\halign{&\hfil$\;#\;$\hfil\cr
\bf 5&\bf 1&6\cr
\bf 6&\bf 5&1\cr
}}\right ]
\left[\vcenter{\halign{&\hfil$\;#\;$\hfil\cr
\bf 5&7\cr
\bf 7&5\cr
}}\right ]\hfill\cr
\hskip 1.5cm
\left[\vcenter{\halign{&\hfil$\;#\;$\hfil\cr
\bf 1&1&2&3\cr
\bf 3&1&1&2\cr
}}\right ]
\left[\vcenter{\halign{&\hfil$\;#\;$\hfil\cr
\bf 4&\bf 2&2&6\cr
\bf 6&\bf 4&2&2\cr
}}\right ]
\left[\vcenter{\halign{&\hfil$\;#\;$\hfil\cr
6\cr
6\cr
}}\right ]
\left[\vcenter{\halign{&\hfil$\;#\;$\hfil\cr
\bf 5&\bf 1&6\cr
\bf 6&\bf 5&1\cr
}}\right ]
\left[\vcenter{\halign{&\hfil$\;#\;$\hfil\cr
\bf 5&7\cr
\bf 7&5\cr
}}\right ]\hfill\cr
}
$$
La juxtaposition des mots {\it du bas} de chaque circuit domin\'e fournit
le mot
$$
\Phi(w)=3\ 1\ 1\ 2\ 6\ 4\ 2\ 2\ 6\ 6\ 5\ 1\ 7\ 5,
$$
dont les descentes successives 
31, 64, 42, 65, 51, 75 correspondent aux exc\'edances apparaissant en gras
dans les diff\'erentes expression du circuit 
$\bigl[{\overline w\atop w}\bigr]$.

\medskip




A l'aide de la construction pr\'ec\'edente, on obtient donc bien une
bijection~$\Phi$ de $R(u)$ sur elle-m\^eme satisfaisant la
propri\'et\'e 
$$
\exc w=\des\Phi(w),
$$
identiquement (\cf. \pc CARTIER|-\pc FOATA| [CaFo69]).

\goodbreak
\section 5. Les distributions Euler-mahoniennes|Les statistiques ``des" 
et ``maj" ont \'et\'e d\'efinies sur les mots (au d\'ebut de la section~4). La
distribution jointe de ces deux statistiques sur une classe de
r\'earrangements de  mots
quelconques est connue depuis \pc MACMAHON| (1916). Notons 
$R({\bf m})$ la classe des r\'earrangements du mot
$1^{m_1}2^{m_2}\ldots r^{m_r}$ et $A_{\bf m}(t,q)$ le polyn\^ome
 g\'en\'erateur du couple $(\des,\maj)$ sur la classe $R({\bf m})$.
Autrement dit, 
$$
A_{\bf m}(t,q)=\sum _w t^{\des w} q^{\maj w}\qquad (w\in R({\bf m})).
$$
Utilisons aussi les notations classiques de la 
$q$-factorielle montante :
$$\displaylines{
\eqalign{(a;q)_n&=\cases{1,&si $n=0$ ;\cr
                               (1-a)(1-aq)\,
                               \ldots\,
                               (1-aq^{n-1}),&si $n\geq 1$ ;\cr}\cr
               (a;q)_{\infty }&=\lim\nolimits_n(a;q)_n=
{\textstyle \prod _{n\geq 0}(1-aq^n)}\,;\cr}\cr
\noalign{\hbox{et des $q$-coefficients multinomiaux :}}
\left [{m_1+m_2+\ldots +m_r\atop
m_1,m_2,\ldots,m_r}\right ]={\textstyle (q;q)_{m_1+m_2+\cdots+m_r}
\over (q;q)_{m_1} (q;q)_{m_2}\ldots (q;q)_{m_r} }.
\cr
}$$
Posons \'egalement $\left|{\bf m}\right|=m_1+m_2+\ldots+m_r$ 
et ${\bf u}^{\bf m}=u_1^{m_1}u_2^{m_2}\ldots u_r^{m_r}$.
On sait, depuis \pc MACMAHON| que ``maj" a la distribution $q$-multinomiale sur
$R({\bf m})$ :
$$\displaylines{
A_{\bf m}(t=1,q)=\left [{m_1+m_2+\ldots +m_n\atop
m_1,m_2,\ldots,m_n}\right ] \qquad (w\in R({\bf m})),\cr
\noalign{\hbox{identit\'e qu'on peut r\'ecrire :}}
\sum _{{\bf m}} A_{\bf m}(t=1,q) 
{{\bf u}^{\bf m}\over (q;q)_{\left|{\bf m}\right|}}
={1\over (u_1;q)_\infty \ldots (u_r;q)_\infty }\,;\cr
}$$
et la distribution du couple   $(\des,\maj)$ sur $R({\bf m})$ n'est autre que la
``$t$-extension" de cette identit\'e :
$$
\sum _{{\bf m}} A_{\bf m}(t,q) 
{{\bf u}^{\bf m}\over (q;q)_{1+\left|{\bf m}\right|}}
=\sum _{s\ge 0}{t^s\over (u_1;q)_{s+1} \ldots (u_r;q)_{s+1} }.
$$
Ces deux derni\`eres identit\'es peuvent s'\'etablir directement \`a partir de la
formule de Cauchy 
$$ 
\sum _\lambda  S_\lambda (x)S_\lambda (y)=\prod _{i,j}
(1-x_iy_j)^{-1}
\quad{\rm et}\quad
\sum _\lambda  S_\lambda (x)S_{\lambda'} (y)=\prod _{i,j}
(1+x_iy_j).
$$
sur les produits des fonctions de Schur (\cf. [Fo92]). On peut
\'egalement trouver des formules de r\'ecurrence pour les coefficients
du polyn\^ome $A_{\bf m}(t,q)$ (\cf. \pc RAWLINGS| [Ra79]). En
r\'esum\'e, on a plusieurs formes analytiques pour la distribution de
$(\des,\maj)$ sur toute classe de r\'earran\-ge\-ments.

On dit qu'un couple de statistiques d\'efini sur $R({\bf m})$ est {\it
Euler-mahonien}, s'il a m\^eme distribution que le couple $(\des,\maj)$
sur $R({\bf m})$. Comme ``exc" et ``des" ont aussi m\^eme distribution sur
toute classe $R({\bf m})$, d'apr\`es la section pr\'ec\'edente, il restait
donc \`a imaginer la d\'efinition d'une statistique, disons
``den,"  ayant m\^eme distribution que ``maj," telle que le couple
(exc, den) soit Euler-mahonien. 

Il est curieux de constater que
depuis \pc MACMAHON| ou m\^eme depuis la construction de la premi\`ere
transformation fondamentale $\Phi$ d\'ecrite dans la section~4, personne
ne se soit int\'eress\'e \`a imaginer une telle statistique. Il a fallu
attendre \pc DENERT|, [Den90] qui, en 1990,  se proposant de calculer la
fonction zeta d'un $R$-ordre h\'er\'editaire dans des alg\`ebres
centrales simples, a \'et\'e amen\'ee \`a introduire une nouvelle
statistique sur les mots, plus tard appel\'ee ``den." Elle a constat\'e
pour les premi\`eres valeurs de~$n$ que le couple $(\exc,\den)$ \'etait
Euler-mahonien sur le groupe sym\'etrique ${\goth S}_n$ et a fait la
conjecture que le r\'esultat devait se prolonger sur toute classe de
r\'earrangements~$R({\bf m})$.


\section 6. La conjecture de Denert|La d\'efinition de la
statistique ``den" (revue par \pc HAN|~[Han92]) est  mieux
comprise, si on introduit l'{\it intervalle cyclique}
$$
\]x,y \] = \cases{
]x,y]    &si $x\leq y$,\cr
[1,y]+\mathopen]x,n] &si $x>y$; \cr   }
$$
Soit alors $w=x_1x_2\ldots x_m$ un mot, soit 
$\overline w=x'_1x'_2\ldots x'_m$ son r\'earrangement croissant.
 On pose alors
$$
\den w=\sum _{1\le k\le m}
\left | \{i\le k-1 :  x_i\in \]x_k,x'_k\]\right\} |.
$$
Par exemple, pour le mot $w$ suivant
$$\eqalignno{
\left ({\overline w\atop w}\right )&=
\left(\vcenter{\halign{&\hfil$\;#\;$\hfil\cr
 1&1& 1&2& 2&2&2& 4& 5& 5&6&6&6&7\cr
3&1&2&1& 2& 4& 6& 2&6& 5&6&1& 7&5\cr
}}\right )\cr
\noalign{\vskip 5pt }
&\hskip22pt \vbox{\halign{&\hfil$\;#\;$\hfil\cr
0&0&2&1&0&4&5&2&7&0&0&9&\omit\hfil1\kern-1pt 2\hfil&4\cr
}}\cr}
$$
on obtient : $\den w=46$.

Pour une permutation $\sigma =\sigma (1)\sigma
(2)\ldots \sigma (n)$, la statistique $\den\sigma $ est simplement
$$
\den\sigma =\sum _{1\le k\le m}
\left | \{i\le k-1 : \sigma (i)\in \]\sigma (k),k\]\right\} |.
$$
G\'eom\'etriquement, le coefficient de rang~$k$ dans la sommation
ci-dessus est le nombre de points du graphe de~$\sigma $ contenus dans le
rectangle $ABCD$, lorsque $\sigma (k)\le k$, et dans les rectangles
$ABCD$ et $EFGH$, lorsque $\sigma (k)>k$, comme indiqu\'e dans la
figure ci-dessus.

\medskip



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

\midinsert

\newbox\boxdenert

\setbox\boxdenert=\vbox{\vskip
25mm\offinterlineskip 
\centerput(25,-5){$k\!\!-\!\!1$}
\centerput(30,-5){$k$}
\centerput(-5,10){$\sigma (k)$}
\centerput(0,10){\vrule height .4pt depth 0pt width 4pt }
\centerput(-7,15){$\sigma (k){+}1$}
\centerput(30,9){$\bullet$}
\centerput(2,12){$A$}
\centerput(23,12){$B$}
\centerput(2,27){$D$}
\centerput(23,27){$C$}
\segment(0,15)\dir(1,0)\long{30}
\segment(25,0)\dir(0,1)\long{30}
\segment(30,0)\dir(0,1)\long{30}
\segment(0,30)\dir(1,0)\long{30}
\segment(0,0)\dir(1,0)\long{50}
\segment(0,0)\dir(1,1)\long{50}
\segment(0,0)\dir(0,1)\long{50}
\segment(50,0)\dir(0,1)\long{50}
\segment(0,50)\dir(1,0)\long{50}
\centerput(25,-10){$\sigma (k)\le k$}
}

\newbox\boxdenerta

\setbox\boxdenerta=\vbox{\vskip
25mm\offinterlineskip 
\centerput(25,-5){$k\!\!-\!\!1$}
\centerput(30,-5){$k$}
\centerput(-5,40){$\sigma (k)$}
\centerput(0,40){\vrule height .4pt depth 0pt width 4pt }
\centerput(-7,45){$\sigma (k){+}1$}
\centerput(-3,50){$n$}
\centerput(30,39){$\bullet$}
\centerput(4,1){$A$}
\centerput(23,1){$B$}
\centerput(2,27){$D$}
\centerput(23,27){$C$}
\centerput(2,42){$E$}
\centerput(23,42){$F$}
\centerput(2,51){$H$}
\centerput(23,51){$G$}
\segment(0,45)\dir(1,0)\long{30}
\segment(25,0)\dir(0,1)\long{50}
\segment(30,0)\dir(0,1)\long{50}
\segment(0,30)\dir(1,0)\long{30}
\segment(0,0)\dir(1,0)\long{50}
\segment(0,0)\dir(1,1)\long{50}
\segment(0,0)\dir(0,1)\long{50}
\segment(50,0)\dir(0,1)\long{50}
\segment(0,50)\dir(1,0)\long{50}
\centerput(25,-10){$\sigma (k)> k$}
}

\vskip2.8cm
\centerline{\hbox{\box\boxdenert\hskip6.5cm\box\boxdenerta\hskip5cm}}
\vskip 1.5cm

\endinsert


%\vskip 1.1cm


Le th\'eor\`eme suivant fut conjectur\'e par \pc DENERT| dans une forme
diff\'erente, mais \'equivalente.



\th Th\'eor\`eme|Le couple de statistiques $(\exc,\den)$ a m\^eme
distribution que $(\des,\maj)$ sur toute classe de r\'earrangements 
$R({\bf m})$
de mots.
\finth

Lorsque $R({\bf m})={\goth S}_n$, \`a savoir le groupe des permutations
d'ordre~$n$, le th\'eor\`eme a
\'et\'e prouv\'e par \pc FOATA| et \pc ZEILBERGER|~[FoZe90]. 
Le th\'eor\`eme pour une classe $R({\bf m})$ quelconque est d\^u \`a 
Han~[Han91]. Ce dernier a eu aussi le m\'erite de donner la bonne
d\'efinition de ``den" dans le cas g\'en\'eral (d\'efinition qui a \'et\'e rappel\'ee
plus haut) et, de fa\c con plus essentielle, de construire une nouvelle
transformation bijective $\Phi_3$ de $R({\bf m})$ sur elle-m\^eme
satisfaisant : 
$$
(\des,\maj)(w)=(\exc,\den)\bigl(\Phi_3(w)\bigr) 
$$
identiquement. C'est la construction de cette transformation que nous
nous proposons de d\'ecrire dans la section suivante.


\section 7. La transformation fondamentale de Han|Soient $x$, $y$, $a$, $b$
quatre lettres appartenant \`a l'intervalle $[n]=\{1,2,\ldots ,n\}$. On dit que
les lettres $a$ et $b$ sont {\it voisines} par rapport
\`a $x$ et $y$,  si elles appartiennent au m\^eme intervalle cyclique
$\]y,x\]$, ou \`a son compl\'ementaire ; dans le cas contraire, on dit qu'elles
sont {\it en face}.

On ne s'impose plus des {\it r\`egles de commutation},
sur l'ensemble des bilettres, mais des {\it r\`egles} (de grammaire). On
forme ce que les informaticiens appellent un {\it syst\`eme semi-Thue}
sur l'ensemble $X\times X$, o\`u $X$ est suppos\'e \^etre ici l'ensemble des
entiers~${\bboard N}$, en posant :
$$
\left(\matrix{x&y\cr
a&b\cr}\right )\Rightarrow \cases{\left(\matrix{y&x\cr
a&b\cr}\right ),&si $a$ et $b$ sont voisines ;\cr
\noalign{\vskip 5pt }
\left(\matrix{y&x\cr
b&a\cr}\right ),&si $a$ et $b$ sont en face.\cr}
$$
Par exemple, pour $x=6$ et $y=4$, les lettres 4 et 8 sont voisines, puisque
$\]y,x\]=\]4,6\]=\{5,6\}$ et que 4 et 8 appartiennent tous deux au
compl\'ementaire de cet ensemble. Au contraire, 4 et 6 sont en face. On a
donc
$$
\left(\matrix{6&4\cr
4&8\cr}\right )\Rightarrow \left(\matrix{4&6\cr
4&8\cr}\right )\qquad{\rm et}\qquad
\left(\matrix{6&4\cr
6&4\cr}\right )\Rightarrow \left(\matrix{4&6\cr
4&6\cr}\right ).
$$
Ces r\`egles peuvent \^etre prolong\'ees \`a l'ensemble des {\it bimots} : on
a ${\bf w}\Rightarrow {\bf w'}$, si ${\bf w=ulu'}$ et ${\bf w'=uru'}$, pour
certains bimots ${\bf u}$, ${\bf u'}$, {\bf l}, {\bf r} et
${\bf l}\Rightarrow {\bf r}$. La fermeture ``$\equiv$" sym\'etrique,
r\'eflexive et transitive de cette relation d\'efinit un mono\"ide quotient
$H(X)=(X\times X)^*/{\equiv}$.
Pour ce mono\"ide, on reprend la m\^eme terminologie que pour le
mono\"ide sur $(X\times X)^*$ d\'efini par des relations de commutation :
flots, circuits, \dots\ Quand on applique les r\`egles pr\'ec\'edentes ${\bf
l}\Rightarrow {\bf r}$ \`a un bimot ${\bf w}
=\bigl({w'\atop w}\bigr)$, la nature des r\`egles veut que le bimot obtenu,
disons ${\bf v}
=\bigl({v'\atop v}\bigr)$ est tel que $v'$ (resp. $v$) est un r\'earrangement
de $w'$ (resp. $w$). Par ailleurs, par application de ces m\^emes r\`egles,
on peut toujours amener le mot du haut \`a \^etre un mot croissant. 
 La difficult\'e vient du fait que
dans une classe, il peut y avoir plusieurs bimots $\bigl({v'\atop v}\bigr)$,
dont le mot du haut $v'$ est croissant. 

Dans une premi\`ere \'etape, on \'etend la d\'efinition de ``exc" et ``den" aux
bimots 
$$
{\bf w}=\Bigl (\matrix{  v\cr w\cr}\Bigr )
=\Bigl (\matrix{v_1\,v_2\,\ldots\,v_m\cr
w_1\,w_2\,\ldots\,v_m\cr}\Bigr )
$$
o\`u $v$ est un r\'earrangement (quelconque) de $w$, en posant :
$$
\eqalign{\exc{\bf w}&=\left |\{i:1\le i\le m,\ w_i>v_i\}\right |;\cr
\den{\bf w}&=\sum _{1\le k\le m}
\left | \{i\le k-1 :  w_i\in \]w_k,v_k\]\right\} |.\cr}
$$
La construction de \pc HAN| repose sur les deux propri\'et\'es suivantes :

\th Propri\'et\'e 1|Les statistiques $\exc$ et $\den$ sont invariantes dans
chaque classe du mono\"ide de Han. Autrement dit, si ${\bf w}\equiv {\bf w'}$,
alors $(\exc,\den)({\bf w})=(\exc,\den)({\bf w'})$.
\finth

\th Propri\'et\'e 2|Si un bimot est un produit de juxtaposition de circuits
domin\'es 
$$\displaylines{
{\bf w}=\left ({v^1\atop w^1}\right)
\left ({v^2\atop w^2}\right)\ldots
\left ({v^r\atop w^r}\right)\cr
\noalign{\hbox{tels que}}
\pre({ w}^1)\le \pre({w}^2)\le  \cdots \le \pre({ w}^r),\cr
\noalign{\hbox{alors}}
(\des,\maj)({\bf w})=(\exc,\den)({\bf w}).\cr
}
$$
\finth

\goodbreak
La construction de la transformation de Han va alors consister, partant d'un mot
$w$, \`a lui associer un bimot {\bf w} tel que $(\exc,\den)(w)=(\exc,\den)({\bf
w})$. Par d\'efinition m\^eme de ces statistiques, il suffit de prendre
${\bf w}=\bigl({\overline w\atop w}\bigr)$, o\`u $\overline w$ est le
r\'earrangement croissant de~$w$.  Il suffit, ensuite, de trouver dans la classe
d'\'equivalence de {\bf w} un bimot $\widetilde {\bf w}$ qui soit un
produit croissant (au sens de la propri\'et\'e~2) de bimots domin\'es :
$$
\widetilde {\bf w}=\left ({v^1\atop w^1}\right)
\left ({v^2\atop w^2}\right)\ldots
\left ({v^r\atop w^r}\right),
$$
et de montrer que le passage de {\bf w} \`a $\widetilde {\bf w}$ est bien
{\it bijectif}.  La bijection cherch\'ee est alors donn\'ee par
$
w\longmapsto \widetilde w= w^1w^2\ldots w^r
$.
Cette construction est illustr\'ee dans l'exemple suivant.

$$\eqalignno{
\left ({\overline w\atop w}\right )&=
\left(\vcenter{\halign{&\hfil$\;#\;$\hfil\cr
 1&1& 1&2& 2&2&2& 4& 5& 5&6&6&6&7\cr
3&1&2&1& 2& 4& 6& 2&6& 5&6&1& 7&5\cr
}}\right )\cr
&\hskip61pt \vbox{\halign{&\hfil$\;#\;$\hfil\cr
&&&&&&&&&&6&5&6&\cr
&&&&&&&&&&6&5&1&\cr
&&&&&&&&&&&6&5&6\cr
&&&&&&&&&&&5&1&7\cr
}}\cr
&\hskip22pt
\vcenter{\halign{&\hfil$\;#\;$\hfil\cr
1&1&1&2&2&2&3&4&5&6&6&6\cr
3&1&2&1&2&4&6&2&6&6&5&1\cr
}}\left(\vcenter{\halign{&\hfil$\;#\;$\hfil\cr
5&7\cr
7&5\cr}}\right)\cr
&\hskip22pt
\vcenter{\halign{&\hfil$\;#\;$\hfil\cr
\cdot&\cdot&\cdot&\cdot
&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot
&\cdot&\cdot&\cdot\cr
\cdot&\cdot&\cdot&\cdot
&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot
&\cdot&\cdot&\cdot\cr
\cdot&\cdot&\cdot&\cdot
&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot
&\cdot&\cdot&\cdot\cr
}}\cr
\widetilde{\bf w }&=
\left(\vcenter{\halign{&\hfil$\;#\;$\hfil\cr
1&1&2&3\cr
3&1&1&2\cr 
}}\right )
\left(\vcenter{\halign{&\hfil$\;#\;$\hfil\cr
4&2&2&6\cr
6&4&2&2\cr 
}}\right )
\left(\vcenter{\halign{&\hfil$\;#\;$\hfil\cr
6\cr
6\cr 
}}\right )
\left(\vcenter{\halign{&\hfil$\;#\;$\hfil\cr
5&1&6\cr
6&5&1\cr 
}}\right )
\left(\vcenter{\halign{&\hfil$\;#\;$\hfil\cr
5&7\cr
7&5\cr 
}}\right )\cr
&\hskip22pt
*\hskip51pt* \hskip4pt *\hskip67pt * \hskip 4pt *\hskip 29pt *\hskip
25pt {\rm exc}\,\widetilde {\bf w}=6=\exc w\cr
&\hskip24pt
0\;\;0\;\;0\;\;1\hskip22pt 4\;\;4\;\;0\;\;3\hskip22pt 0\hskip22pt
7\;\;5\;\;9\hskip22pt 9\;\;4\hskip 12pt {\rm den}\,\widetilde {\bf
w}=46=\den w\cr &\hskip22pt
\bullet\hskip51pt\bullet \hskip4pt \bullet\hskip67pt \bullet \hskip 4pt
\bullet\hskip 29pt \bullet\hskip 25pt {\rm des}\,\widetilde w=6\cr
&\hskip24pt
1\hskip53pt 5 \hskip6pt 6\hskip67pt 1\hskip-1pt 0 \hskip 3pt
1\hskip-1pt 1\hskip 29pt 1\hskip-1pt 3\hskip 22pt {\rm maj}\,\widetilde
w=46\cr }
$$

\vfill\eject

\vglue0pt
\vfill
\eightpoint 
\centerline{BIBLIOGRAPHIE} 
\penalty 10000 \vskip .5cm


\divers Ca62|{\pc CARTIER|} (Pierre)|Fluctuations dans les suites de
variables al\'eatoires ind\'e\-pen\-dantes,
{\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$|

\divers Ca71|{\pc CARTIER|} (Pierre)|La s\'erie g\'en\'eratrice exponentielle :
applications probabi\-listes et alg\'ebriques, Publications de l'I.R.M.A.
Strasbourg, 68 pages, {\oldstyle 1971}/{\oldstyle 1972}|

 \divers Ca80|{\pc CARTIER|}
(Pierre)|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|{\pc CARTIER|} (Pierre)|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 Ca91|{\pc CARTIER|} (Pierre)|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$|



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

\article Den90|{\pc DENERT|} (M.)|The genus zeta function of hereditary
orders in central simple algebras over global fields|Math.
Comp.|54|1990|449-465|


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

\divers Du86|{\pc DUBOC|} (C.)|Commutations dans les mono\"\i des libres : un
cadre th\'eorique pour l'\'etude du parall\'elisme, th\`ese, Facult\'e des
Sciences de l'Universit\'e de Rouen, {\oldstyle 1986}|

\divers DuKr90|{\pc DUCHAMP|} (D.) and {\pc KROB|} (D.)|Free partially
commutative structures, \`a para\^\i tre dans {\sl J. of Algebra}|

\divers Fo92|{\pc FOATA|} (Dominique)|Les distributions
Euler-Mahoniennes sur les mots, \`a para\^\i tre dans {\sl Discrete Math}|

\article FoZe90|{\pc FOATA| (Dominique) and  \pc ZEILBERGER|}
(Doron)|Denert's Permutation Statistic Is Indeed Euler-Mahonian|Studies
in Appl. Math.|83|1990|31--59|

 \divers Han91|{\pc HAN| (Guo-Niu)}|Calcul
Denertien, th\`ese doctorat Strasbourg\pointir {\sl Publ. I.R.M.A.
Strasbourg}, 476/TS-29, {\oldstyle 1991}|


\divers Maz87|{\pc MAZURKIEWICZ|} (A.)|Trace Theory, {\sl Petri Nets,
Applications and Relationship to other Models of Concurrency} [W.
Brauer, ed. ], p.~279--324\pointir Berlin,
Springer-Verlag, $\oldstyle 1987$ ({\sl Lecture Notes in Computer
Science, {\bf 255}})|

\divers Ra79|{\pc RAWLINGS| (Don)}|Permutation and Multipermutation
Statistics, Ph. D. thesis, Univ. Calif. San Diego\pointir {\sl Publ. I.R.M.A.
Strasbourg}, 49/P-23, {\oldstyle 1979}|



\tenpoint
\nobreak
\vskip 1cm
\rightline{\vbox{\hbox{Dominique {\petcap Foata,}}
                 \hbox{{\eightrm I.R.M.A.} et d\'epartement de math\'ematique,}
                 \hbox{{\eightrm C.N.R.S.} et Universit\'e Louis-Pasteur,}
                 \hbox{7, rue Ren\'e-Descartes,}
                 \hbox{F-67084 Strasbourg Cedex.}
                 \hbox{email : {\eightrm foata@math.u-strasbg.fr}}}\qquad} 
               

\eject
\bye










\section 5. Nombres Eul\'eriens|Il s'agit de nombres rencontr\'es dans de
nombreux domaines des math\'ematiques. Not\'es
$A_{n,k}$, ils sont d\'efinis par la 
relation de r\'ecurrence :
$$
\displaylines{
A_{n,k}=(k+1)A_{n-1,k}+(n-k)A_{n-1,k-1}\qquad
(1\le k\le n-1)\,;\cr
A_{n,0}=1\quad(n\ge 0)\,;
\qquad A_{n,k}=0 \quad(k\ge n).\cr 
}
$$
Les premi\`eres valeurs sont donn\'ees dans le tableau
suivant :
$$
\vbox{\halign{\vrule\ \hfil#\quad\vrule
&\strut\quad\hfil$#$\hfil
&\quad\hfil$#$\hfil
&\quad\hfil$#$\hfil
&\quad\hfil$#$\hfil
&\quad\hfil$#$\hfil
&\quad\hfil$#$\hfil
&\quad\hfil$#$\hfil\quad\vrule\cr
\noalign{\hrule}
k={}&0&1&2&3&4&5&6\cr
\noalign{\hrule}
n=1&1&&&&&&\cr
2&1&1&&&&&\cr
3&1&4&1&&&&\cr
4&1&11&11&1&&&\cr
5&1&26&66&26&1&&\cr
6&1&57&302&302&57&1&\cr
7&1&120&1191&2416&1191&120&1\cr
\noalign{\hrule}
}}
$$
On observe que la somme de tous les coefficients de la
ligne de rang~$n$ est \'egale \`a $n!$ et la question
naturelle qui se pose est de savoir si l'on peut trouver une
statistique simple ``stat" sur le groupe ${\goth S}_n$ 
des permutations
telle que le nombre de permutations~$w$
satisfaisant \`a ${\rm stat}\,w=k$ est pr\'ecis\'ement
\'egal \`a~$A_{n,k}$. Une telle statistique sera
appel\'ee statistique {\it eul\'erienne}. Le polyn\^ome
$$
A_n(t)=\sum_k A_{n,k}t^k\qquad(0\le k\le n-1)
$$
est appel\'e {\it polyn\^ome eul\'erien}.

Le fait que ``des" est une statistique eul\'erienne sur ${\goth S}_n$ est
pratiquement \'evident \`a l'examen m\^eme de la relation de r\'ecurrence
des $A_{n,k}$. On peut, en effet, engendrer les \'el\'ements de ${\goth
S}_n$ \'ecrits comme des mots $a_1a_2\ldots a_n$ \`a
partir des \'el\'ements $v=b_1b_2\ldots b_{n-1}$ de
${\goth S}_{n-1}$ en ins\'erant~$n$ avant ou apr\`es $v$,
ou entre les lettres de~$v$. Il y a donc~$n$ insertions
possibles.

Si $n$ est ins\'er\'e au d\'ebut du mot ou entre deux
lettres $b_ib_{i+1}$ telles que $b_i<b_{i+1}$, le mot
r\'esultant a une descente de plus. Dans le cas contraire,
le nombre de descentes reste invariant. Pour obtenir donc
l'ensemble $S_{n,k}$ de toutes les permutations
d'ordre~$n$ ayant~$k$ descentes, il suffit 

\decale(i)|ou bien de consid\'erer
l'ensemble de toutes les permutations
appartenant \`a $S_{n-1,k-1}$ et y ins\'erer~$n$ dans les
$(n-1)-(k-1)$ positions qui cr\'eent une nouvelle
descente ; on obtient ainsi $(n-k)A_{n_1,k-1}$
permutations d'ordre~$n$ ;

\decale (ii)|ou bien de consid\'erer l'ensemble
$S_{n-1,k}$ et d'ins\'erer dans chaque permutation
appartenant \`a cet ensemble l'entier~$n$ dans les
$(k+1)$ positions ne cr\'eant pas de nouvelles descentes
; on obtient, de cette fa\c con, $(k+1)A_{n-1,k}$
permutations d'ordre~$n$ ayant $k$~descentes.\cqfd

Comme d'apr\`es la section pr\'ec\'edente ``exc" et ``des" ont m\^eme
distribution sur toute classe de r\'earrangements, donc en particulier sur le
groupe sym\'etrique, on a le r\'esultat suivant.

 \th Proposition|Pour tout
$n\ge 1$ on a : 
$$ A_n(t)=\sum_{0\le k\le n-1}A_{n,k}\,t^k
=\sum_w t^{\des w}=\sum_w t^{\exc w}\qquad
(w\in {\goth S}_n).
$$
\finth

Il existe de nombreuses relations sur les polyn\^omes eul\'eriens. Leur
fonction g\'en\'eratrice est donn\'ee par exemple, par :
 $$
\sum_{n\ge 0} A_n(t){u^n\over n!}
={(1-t)\over \exp(u(t-1))-t}.
$$

A ce niveau, on peut construire un $q$-analogue, soit de la relation de
r\'ecurrence des $A(n,k)$, soit de la fonction g\'en\'eratrice elle-m\^eme.
On obtient des $q$-analogues diff\'erents, qui tous deux ont re\c cu des
interpr\'etations combinatoires. Nous nous int\'eresserons au
$q$-analogue de la relation de r\'ecurrence. Pour tout entier $m\ge 0$,
posons $[m]_q=1+q+q^2+\cdots+q^{m-1}$. La relation de r\'ecurrence
$$
\displaylines{
A_{n,k}(q)=[k+1]_q A_{n-1,k}(q)
+q^k[n-k]_qA_{n-1,k-1}(q),\,;\cr
A_{n,0}(q)=1\quad(n\ge 0)\,;
\qquad A_{n,k}(q)=0 \quad(k\ge n).\cr 
}
$$
d\'efinit une suite de polyn\^omes en~$q$ \`a coefficients
entiers, dont les premi\`eres valeurs sont donn\'ees dans le Tableau~3.

\midinsert

\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\preambuleItv[#1]{%
     \tv\hfil\kern#1$##$\kern#1\tv&&
      \tvi\hfil\kern#1$##$\kern#1\tv\cr}



\def\vspace[#1]{\noalign{\vskip#1}}



\centerline{
\eightpoint
\tableau\preambuleItv[5pt]
\th
\matrix{\enspace  k=\cr   n= \hfill  &\cr}\!\! & 0 & 1&  2&  3&  4\cr \th
1&1&0&0&0&0\cr\th
2&1&q&0&0&0\cr \th
3&1& 2q+2q^2& q^3 &0&0\cr \th
4&1& 3q+5q^2+3q^3 & 3q^3+5q^4+3q^5& q^6& 0\cr\th
5&1
& \matrix{ \vspace[5pt] \hfill 4q+9q^2 \cr +9q^3+4q^4 \cr  \vspace[5pt] }
& \matrix{\hfill 6q^3+16q^4 \cr +22q^5+16q^6+6q^7\cr} 
& \matrix{\hfill 4q^6+9q^7 \cr  +9q^8+4q^9 \cr}
&q^{10}\cr\th
\endtableau
}
\bigskip
\centerline{Tableau 3}
\endinsert

Un couple de statistiques $(f,g)$, \`a valeurs enti\`eres, d\'efinies sur
${\goth S}_n$ telles que
$$
\sum _{\sigma \in {\goth S}_n} t^{f(\sigma )} q^{g(\sigma )}
=\sum _{0\le k\le n-1} t^k A_{n,k}(q),
$$
est appel\'ee statistique {\it euler-mahonienne}. Une telle statistique est
fournie par le couple $(\des,\maj)$ (``nombre de descentes," ``indice
majeur"). En fait, la d\'emonstration ci-dessus qui permet de montrer que
``des" est eul\'erienne permet de d\'emontrer \'egalement que
$(\des,\maj)$ est euler-mahonien.


\section 6. La conjecture de Denert|En 1990 \pc DENERT|~[Den90] s'est
propos\'ee de calculer la fonction zeta d'un $R$-ordre h\'er\'editaire dans
des alg\`ebres centrales simples. Pour ce faire, elle a \'et\'e amen\'ee \`a
introduire une nouvelle statistique sur les mots, plus tard appel\'ee ``den,"
qui \'etait mahonienne, en ce sens que la fonction g\'en\'eratrice de ``den"
sur une classe de r\'earrangements $R(1^{a_1}2^{a_2}\ldots n^{a_n})$ \'etait
donn\'ee par 
$$
\sum _w q^{\den w}=\left [{a_1+a_2+\ldots +a_n\atop
a_1,a_2,\ldots,a_n}\right ]_q ,
$$
o\`u le second membre de cette formule d\'esigne le $q$-coefficient
multinomial. De plus, lorsqu'on se restreint au groupe sym\'etrique
${\goth S}_n$, elle a \'et\'e amen\'ee \`a conjecturer que le couple
$(\exc,\den)$ \'etait euler-mahonien.

Sa d\'efinition de ``den" (revue par \pc HAN|~[Han92]) est 
mieux
comprise, si on introduit l'{\it intervalle cyclique}
$$
\]x,y \] = \cases{
]x,y]    &si $x\leq y$,\cr
[1,y]+\mathopen]x,n] &si $x>y$; \cr   }
$$
Soit alors $w=x_1x_2\ldots x_m$ un mot, soit 
$\overline w=x'_1x'_2\ldots x'_m$ son r\'earrangement croissant.
 On pose alors
$$
\den w=\sum _{1\le k\le m}
\left | \{i\le k-1 :  x_i\in \]x_k,x'_k\]\right\} |.
$$
Pour une permutation $\sigma =\sigma (1)\sigma (2)\ldots \sigma (n)$, la
statistique $\den\sigma $ est simplement
$$
\den\sigma =\sum _{1\le k\le m}
\left | \{i\le k-1 : \sigma (i)\in \]\sigma (k),k\]\right\} |.
$$
G\'eom\'etriquement, le coefficient de rang~$k$ dans la sommation
ci-dessus est le nombre de points du graphe de~$\sigma $ contenus dans le
rectangle $ABCD$, lorsque $\sigma (k)\le k$, et dans les rectangles
$ABCD$ et $EFGH$, lorsque $\sigma (k)>k$, comme indiqu\'e dans la
Figure~4.


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

\midinsert

\newbox\boxdenert

\setbox\boxdenert=\vbox{\vskip
25mm\offinterlineskip 
\centerput(25,-5){$k\!\!-\!\!1$}
\centerput(30,-5){$k$}
\centerput(-5,10){$\sigma (k)$}
\centerput(0,10){\vrule height .4pt depth 0pt width 4pt }
\centerput(-7,15){$\sigma (k){+}1$}
\centerput(30,9){$\bullet$}
\centerput(2,12){$A$}
\centerput(23,12){$B$}
\centerput(2,27){$D$}
\centerput(23,27){$C$}
\segment(0,15)\dir(1,0)\long{30}
\segment(25,0)\dir(0,1)\long{30}
\segment(30,0)\dir(0,1)\long{30}
\segment(0,30)\dir(1,0)\long{30}
\segment(0,0)\dir(1,0)\long{50}
\segment(0,0)\dir(1,1)\long{50}
\segment(0,0)\dir(0,1)\long{50}
\segment(50,0)\dir(0,1)\long{50}
\segment(0,50)\dir(1,0)\long{50}
\centerput(25,-10){$\sigma (k)\le k$}
}

\newbox\boxdenerta

\setbox\boxdenerta=\vbox{\vskip
25mm\offinterlineskip 
\centerput(25,-5){$k\!\!-\!\!1$}
\centerput(30,-5){$k$}
\centerput(-5,40){$\sigma (k)$}
\centerput(0,40){\vrule height .4pt depth 0pt width 4pt }
\centerput(-7,45){$\sigma (k){+}1$}
\centerput(-3,50){$n$}
\centerput(30,39){$\bullet$}
\centerput(4,1){$A$}
\centerput(23,1){$B$}
\centerput(2,27){$D$}
\centerput(23,27){$C$}
\centerput(2,42){$E$}
\centerput(23,42){$F$}
\centerput(2,51){$H$}
\centerput(23,51){$G$}
\segment(0,45)\dir(1,0)\long{30}
\segment(25,0)\dir(0,1)\long{50}
\segment(30,0)\dir(0,1)\long{50}
\segment(0,30)\dir(1,0)\long{30}
\segment(0,0)\dir(1,0)\long{50}
\segment(0,0)\dir(1,1)\long{50}
\segment(0,0)\dir(0,1)\long{50}
\segment(50,0)\dir(0,1)\long{50}
\segment(0,50)\dir(1,0)\long{50}
\centerput(25,-10){$\sigma (k)> k$}
}

\vskip2.8cm
\centerline{\hbox{\box\boxdenert\hskip6.5cm\box\boxdenerta\hskip5cm}}
\vskip 1.5cm

\endinsert



Le th\'eor\`eme suivant fut conjectur\'e par \pc DENERT| dans une forme
diff\'erente, mais \'equivalente.

\th Th\'eor\`eme|Le couple de statistiques $(\exc,\den)$ a m\^eme
distribution que $(\des,\maj)$ sur toute classe de r\'earrangements $R(u)$
de mots.

En particulier, la distribution de $(\exc,\den)$ sur le groupe sym\'etrique
est euler-mahonienne.
\finth

La seconde partie du th\'eor\`eme concernant le groupe sym\'etrique a
\'et\'e prouv\'ee par \pc FOATA| et \pc ZEILBERGER|~[FoZe90]. Dans sa
forme g\'en\'erale, le th\'eor\`eme est d\^u \`a \pc HAN|~[Han92]. Sa
d\'emonstration repose sur une construction tr\`es habile d'un nouveau
mono\"ide soumis \`a des r\`egles de commutation plus g\'en\'erales que
celles utilis\'ees par \pc CARTIER|-\pc FOATA|. La construction de \pc HAN|
fait l'objet de la derni\`ere partie de cet article.

\section 7. La transformation fondamentale de Han|Soient $x$, $y$, $a$, $b$
quatre lettres appartenant \`a l'intervalle $[n]=\{1,2,\ldots ,n\}$. On dit que
les lettres $a$ et $b$ sont {\it voisines} par rapport
\`a $x$ et $y$,  si elles appartiennent au m\^eme intervalle cyclique
$\]y,x\]$, ou \`a son compl\'ementaire ; dans le cas contraire, on dit qu'elles
sont {\it en face}.

On ne s'impose plus des {\it r\`egles de commutation},
sur l'ensemble des bilettres, mais des {\it r\`egles} (de grammaire). On
forme ce que les informaticiens appellent un {\it syst\`eme semi-Thue}
sur l'ensemble $X\times X$, o\`u $X$ est suppos\'e \^etre ici l'ensemble des
entiers~${\bboard N}$, en posant :
$$
\left(\matrix{x&y\cr
a&b\cr}\right )\Rightarrow \cases{\left(\matrix{y&x\cr
a&b\cr}\right ),&si $a$ et $b$ sont voisines ;\cr
\noalign{\vskip 5pt }
\left(\matrix{y&x\cr
b&a\cr}\right ),&si $a$ et $b$ sont en face.\cr}
$$
Par exemple, pour $x=6$ et $y=4$, les lettres 4 et 8 sont voisines, puisque
$\]y,x\]=\]4,6\]=\{5,6\}$ et que 4 et 8 appartiennent tous deux au
compl\'ementaire de cet ensemble. Au contraire, 4 et 6 sont en face. On a
donc
$$
\left(\matrix{6&4\cr
4&8\cr}\right )\Rightarrow \left(\matrix{4&6\cr
4&8\cr}\right )\qquad{\rm et}\qquad
\left(\matrix{6&4\cr
6&4\cr}\right )\Rightarrow \left(\matrix{4&6\cr
4&6\cr}\right ).
$$
Ces r\`egles peuvent \^etre prolong\'ees \`a l'ensemble des {\it bimots} : on
a ${\bf w}\Rightarrow {\bf w'}$, si ${\bf w=ulu'}$ et ${\bf w'=uru'}$, pour
certains bimots ${\bf u}$, ${\bf u'}$, {\bf l}, {\bf r} et
${\bf l}\Rightarrow {\bf r}$. La fermeture ``$\equiv$" sym\'etrique,
r\'eflexive et transitive de cette relation d\'efinit un mono\"ide quotient
$H(X)=(X\times X)^*/{\equiv}$.
Pour ce mono\"ide, on reprend la m\^eme terminologie que pour le
mono\"ide sur $(X\times X)^*$ d\'efini par des relations de commutation :
flots, circuits, \dots\ Quand on applique les r\`egles pr\'ec\'edentes ${\bf
l}\Rightarrow {\bf r}$ \`a un bimot ${\bf w}
=\bigl({w'\atop w}\bigr)$, la nature des r\`egles veut que le bimot obtenu,
disons ${\bf v}
=\bigl({v'\atop v}\bigr)$ est tel que $v'$ (resp. $v$) est un r\'earrangement
de $w'$ (resp. $w$). Par ailleurs, par application de ces m\^emes r\`egles,
on peut toujours amener le mot du haut \`a \^etre un mot croissant. 
 La difficult\'e vient du fait que
dans une classe, il peut y avoir plusieurs bimots 
$\bigl({v'\atop v}\bigr)$,
dont le mot du haut $v'$ est croissant. 



\bye




$$\eqalignno{
\left ({\overline w\atop w}\right )&=
\left(\vcenter{\halign{&\hfil$\;#\;$\hfil\cr
 1&1& 1&2& 2&2&2& 4& 5& 5&6&6&6&7\cr
3&1&2&1& 2& 4& 6& 2&6& 5&6&1& 7&5\cr
}}\right )\cr
\noalign{\vskip 5pt }
&\hskip22pt \vbox{\halign{&\hfil$\;#\;$\hfil\cr
0&0&2&1&0&4&5&2&7&0&0&9&\omit\hfil1\kern-1pt 2\hfil&4\cr
&&&&&&*&&*&&*&&*&\cdot&\omit\hskip10pt$=4$\cr
*&*&*&*&*&*&*&*&*&*&*&*&\cdot&&\omit\hskip10pt$=12$\cr
*&&*&&*&*&*&*&*&*&*&\cdot&&&\omit\hskip10pt$=9$\cr
&&&&&&&&&&\cdot&&&&\omit\hskip10pt$=0$\cr
&&&&&&&&&\cdot&&&&&\omit\hskip10pt$=0$\cr
*&*&*&*&*&*&&*&\cdot&&&&&&\omit\hskip10pt$=7$\cr
*&&&&&*&&\cdot&&&&&&&\omit\hskip10pt$=2$\cr
*&*&*&*&*&&\cdot&&&&&&&&\omit\hskip10pt$=5$\cr
&*&*&*&*&\cdot&&&&&&&&&\omit\hskip10pt$=4$\cr
&&&&\cdot&&&&&&&&&&\omit\hskip10pt$=0$\cr
&&*&\cdot&&&&&&&&&&&\omit\hskip10pt$=1$\cr
*&*&\cdot&&&&&&&&&&&&\omit\hskip10pt$=2$\cr
&\cdot&&&&&&&&&&&&&\omit\hskip10pt$=0$\cr
\cdot&&&&&&&&&&&&&&\omit\hskip10pt$=0$\cr
\noalign{\vskip 5pt}
\multispan{15}\hfil${\rm den}\, w=46$\cr
\noalign{\vskip 5pt }
\multispan{15}\hfil Figure 5\qquad\qquad\hfil\cr
}}\cr}
$$

