\ifx\pdfoutput\jamaisdefined\else
\input supp-pdf.tex \pdfoutput=1 \pdfcompresslevel=9
\def\HanFig#1{\convertMPtoPDF{#1}{1}{1}}
\fi

\def\leaderfill{\leaders\hbox to .5em{\hss.\hss}\hfill}

%\def\index#1{#1}
%\openout1=index01
%\def\index#1{#1\write1{#1 \the\pageno}}
%\def\Index#1{\write1{#1 \the\pageno}}

%\def\bye{\par\vfill\supereject\closeout1\end}

%\input tex8bits


\catcode'32=9
\magnification=1200

\voffset=.7cm
%\voffset=1cm
\hoffset=.16cm

\font\tenpc=cmcsc10
\font\eightpc=cmcsc10 at 8pt

% 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=msbm7 at 8pt
\font\sevengoth=eufm7
\font\sevenbboard=msbm7
\font\sixgoth=eufm5 at 6pt
\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\c caise 

\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

% fin de dactylographie francaise

\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=20.9cm 
\newdimen\lmargeext \lmargeext=1cm
%\hsize=12cm
%\vsize=19.15cm
\hsize=11.67cm
\vsize=18.90cm 
\parskip 0pt
\parindent=12pt

\def\margehaute{\vbox to \hmargehaute{\vss}}%
\def\margebasse{\vss}

\footline={}

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

\titrecourant={\iftrue\botmark\fi}  

\def\newsectionmark{}

\def\shortsectionmark #1{\mark{\noexpand\eightrm\uppercase{#1}\noexpand\else\noexpand\eightrm
\uppercase{#1}} 
\def\newsectionmark {\noexpand\eightrm\uppercase{#1}}}



\def\corpsdepage{\hbox to \lpage{\hss\pagetexte\hskip\lmargeext}}
\def\pagetexte{\vbox{\makeheadline\kern.4cm\pagebody\makefootline}}
\headline={\ifpagetitre\titleheadline \else
  \ifodd\pageno\rightheadline \else\leftheadline\fi\fi}
\def\leftheadline{\eightpoint\rlap{\tenbf\folio}\hfil
{\eightrm\the\auteurcourant}\hfil}
\def\rightheadline{\eightpoint\hfil
{\eightrm\the\titrecourant}\hfil\llap{\tenbf\folio}}
\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 \penalty -200
       \mark{\newsectionmark\noexpand\else \uppercase{#1}}
         {\bf #1}\shortsectionmark{#1}\unskip\pointir
            }


\def\sectiona #1|{\par\vskip .4cm \penalty -200
       \mark{\newsectionmark\noexpand\else \uppercase{#1}}
\centerline{\bf #1}\shortsectionmark{#1}\par\nobreak\vskip
5pt}

\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{}i\`eme|}}
\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\`es une fraction

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

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

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

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

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

\def\decale#1|{\par\noindent\hskip 28pt\llap{#1}\kern 5pt}
\def\decaledecale#1|{\par\noindent\hskip 34pt\llap{#1}\kern 5pt}

% pour les titres en deux lignes et les sections sans point-tiret :
\def\titrea#1|#2|{\message{#1 #2}
  \par\vskip.5cm plus .1cm minus .1cm\penalty -1000
  \centerline{\bf #1}
  \centerline{\bf #2}
  \vskip 5pt
  \penalty 10000 }

\def\ssectiona#1|{\par\vskip .2cm
  {\it #1}
  \par\nobreak\vskip 2pt }

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

\def\displaylinesno#1{\displ@y\halign{
\hbox to\displaywidth{$\@lign\hfil\displaystyle##\hfil$}&
\llap{$##$}\crcr#1\crcr}}

\def\ldisplaylinesno#1{\displ@y\halign{ 
\hbox to\displaywidth{$\@lign\hfil\displaystyle##\hfil$}&
\kern-\displaywidth\rlap{$##$}\tabskip\displaywidth\crcr#1\crcr}}

\def\Eqalign#1{\null\,\vcenter{\openup\jot\m@th\ialign{
\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
&&\quad\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
\crcr#1\crcr}}\,}


% matrice justifi\'ee \`a droite : \hfil coef dans chaque ligne

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

\def\pmatrixd#1{\left(\matrixd{#1}\right)}

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

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


\def\system#1{\left\{\null\,\vcenter{\openup1\jot\m@th
\ialign{\strut$##$     &\hfil$##$&$##$\hfil&&
       \enskip$##$\enskip&\hfil$##$&$##$\hfil\crcr
        #1\crcr}}\right.}

\def\lfq{\leavevmode\raise.3ex\hbox{$\scriptscriptstyle
\langle\!\langle$}\thinspace}
\def\rfq{\leavevmode\thinspace\raise.3ex\hbox{$\scriptscriptstyle
\rangle\!\rangle$}}


\catcode`\@=12

%  guillements fran\c cais  

\def\og{\leavevmode\raise 1pt\hbox{$\scriptscriptstyle\langle\!\langle\,$}}
\def\fg{\ignorespaces\leavevmode\raise 1pt\hbox{$\,\scriptscriptstyle\rangle\!\rangle$}}




\def\decale#1|{\par\noindent\hskip 28pt\llap{#1}\kern
5pt } 
\def\decaledecale#1|{\par\noindent\hskip 34pt\llap{#1}\kern
5pt }

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

\def\Mo{{\rm Mo}}
\def\Ab{{\rm Ab}}
\def\Pr{{\rm P}}
\def\Qr{{\rm Q}}
\def\Rr{{\rm R}}
\def\Esp{{\rm E}}
\def\pr{{\rm pr}}
\def\card{\mathop{\rm card}\nolimits}
\def\Log{\mathop{\rm Log}}
\def\Var{\mathop{\rm Var}}
\def\Cov{\mathop{\rm Cov}}
\def\Fr{{\rm F}}
\def\Gr{{\rm G}}
\def\Hr{{\rm H}}
\def\sh{\mathop{\rm sh}}
\def\tg{\mathop{\rm tg}}
\def\Arctg{\mathop{\rm Arctg}}
\let\bb=\bboard
\def\convloi{\,{\buildrel \cal L \over \longrightarrow}\,}
\def\convproba{\,{\buildrel p \over \longrightarrow}\,}
\def\convps{\,{\buildrel p.s. \over \longrightarrow}\,}
\def\Esp{{\bboard E}}
\def\sep{\,|\,}
\def\cond{\,|\,}

\def\phiavec_#1{\varphi_{\hbox{\lower 3pt\hbox{$\scriptstyle #1$}}}}

\def\notenmarge#1{\vadjust{\hskip
-2.66cm\smash{\vtop{\eightpoint \hfuzz 15pt
\noindent \hsize=1.66cm
#1}}}}



\ifnum\day<0 \advance\day by 160 \fi

\def\fdate{\number\day\space
   \ifcase\month\or janvier\or f\'evrier\or 
mars\or avril\or mai\or 
   juin\or juillet\or ao\^ut\or septembre\or 
octobre\or novembre\or
   d\'ecembre\fi\space\number\year}


%ญญญญญญญญญญญญญญญญญญญญญญญ
%\input LabelFig
\def\illustration #1 by #2 (#3) scaled #4{\dimen1=#2
\divide\dimen1 by 1000
\multiply\dimen1 by #4
\vtop to \dimen1{\dimen1=#1
\divide\dimen1 by 1000
\multiply\dimen1 by #4
\hsize=\dimen1\vss
\noindent\special{illustration #3 scaled #4}}}

\def\Grille{\setbox13=\vbox to 5mm{\hrule width 110mm\vfill}
\setbox13=\vbox{\offinterlineskip
   \copy13\copy13\copy13\copy13\copy13\copy13\copy13\copy13
   \copy13\copy13\copy13\copy13\box13\hrule width 110mm}
\setbox14=\hbox to 5mm{\vrule height 65mm\hfill}
\setbox14=\hbox{\copy14\copy14\copy14\copy14\copy14\copy14
   \copy14\copy14\copy14\copy14\copy14\copy14\copy14\copy14
   \copy14\copy14\copy14\copy14\copy14\copy14\copy14\copy14\box14}
\ht14=0pt\dp14=0pt\wd14=0pt
\setbox13=\vbox to 0pt{\vss\box13\offinterlineskip\box14}
\wd13=0pt\box13}

\def\grille{\noalign{\nointerlineskip\Grille\nointerlineskip}}

%‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹

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

%‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹

\def\diagram#1{\def\normalbaselines{\baselineskip=0pt\lineskip=5pt}
\matrix{#1}}

\def\hfl#1#2#3{\smash{\mathop{\hbox to#3{\rightarrowfill}}\limits
^{\scriptstyle#1}_{\scriptstyle#2}}}

\def\gfl#1#2#3{\smash{\mathop{\hbox to#3{\leftarrowfill}}\limits
^{\scriptstyle#1}_{\scriptstyle#2}}}

\def\vfl#1#2#3{\llap{$\scriptstyle #1$}
\left\downarrow\vbox to#3{}\right.\rlap{$\scriptstyle #2$}}

%‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹‹


 \message{`lline' & `vector' macros from LaTeX}
 \catcode`@=11
\def\{{\relax\ifmmode\lbrace\else$\lbrace$\fi}
\def\}{\relax\ifmmode\rbrace\else$\rbrace$\fi}
\def\newcount{\alloc@0\count\countdef\insc@unt}
\def\newdimen{\alloc@1\dimen\dimendef\insc@unt}
\def\newwrite{\alloc@7\write\chardef\sixt@@n}

\newwrite\@unused
\newcount\@tempcnta
\newcount\@tempcntb
\newdimen\@tempdima
\newdimen\@tempdimb
\newbox\@tempboxa

\def\@spaces{\space\space\space\space}
\def\@whilenoop#1{}
\def\@whiledim#1\do #2{\ifdim #1\relax#2\@iwhiledim{#1\relax#2}\fi}
\def\@iwhiledim#1{\ifdim #1\let\@nextwhile=\@iwhiledim
        \else\let\@nextwhile=\@whilenoop\fi\@nextwhile{#1}}
\def\@badlinearg{\@latexerr{Bad \string\line\space or \string\vector
   \space argument}}
\def\@latexerr#1#2{\begingroup
\edef\@tempc{#2}\expandafter\errhelp\expandafter{\@tempc}%
%% error help message pieces.
\def\@eha{Your command was ignored.
^^JType \space I <command> <return> \space to replace it
  with another command,^^Jor \space <return> \space to continue without it.}
\def\@ehb{You've lost some text. \space \@ehc}
\def\@ehc{Try typing \space <return>
  \space to proceed.^^JIf that doesn't work, type \space X <return> \space to
  quit.}
\def\@ehd{You're in trouble here.  \space\@ehc}

\typeout{LaTeX error. \space See LaTeX manual for explanation.^^J
 \space\@spaces\@spaces\@spaces Type \space H <return> \space for
 immediate help.}\errmessage{#1}\endgroup}
\def\typeout#1{{\let\protect\string\immediate\write\@unused{#1}}}

% line & circle fonts
\font\tenln    = line10
\font\tenlnw   = linew10
%\font\tencirc  = circle10
%\font\tencircw = circlew10


\newdimen\@wholewidth
\newdimen\@halfwidth
\newdimen\unitlength 

\unitlength =1pt

%\newbox\@picbox
%\newdimen\@picht

\def\thinlines{\let\@linefnt\tenln \let\@circlefnt\tencirc
  \@wholewidth\fontdimen8\tenln \@halfwidth .5\@wholewidth}
\def\thicklines{\let\@linefnt\tenlnw \let\@circlefnt\tencircw
  \@wholewidth\fontdimen8\tenlnw \@halfwidth .5\@wholewidth}

\def\linethickness#1{\@wholewidth #1\relax \@halfwidth .5\@wholewidth}



\newif\if@negarg

\def\lline(#1,#2)#3{\@xarg #1\relax \@yarg #2\relax
\@linelen=#3\unitlength
\ifnum\@xarg =0 \@vline
  \else \ifnum\@yarg =0 \@hline \else \@sline\fi
\fi}

\def\@sline{\ifnum\@xarg< 0 \@negargtrue \@xarg -\@xarg \@yyarg -\@yarg
  \else \@negargfalse \@yyarg \@yarg \fi
\ifnum \@yyarg >0 \@tempcnta\@yyarg \else \@tempcnta -\@yyarg \fi
\ifnum\@tempcnta>6 \@badlinearg\@tempcnta0 \fi
\setbox\@linechar\hbox{\@linefnt\@getlinechar(\@xarg,\@yyarg)}%
\ifnum \@yarg >0 \let\@upordown\raise \@clnht\z@
   \else\let\@upordown\lower \@clnht \ht\@linechar\fi
\@clnwd=\wd\@linechar
\if@negarg \hskip -\wd\@linechar \def\@tempa{\hskip -2\wd\@linechar}\else
     \let\@tempa\relax \fi
\@whiledim \@clnwd <\@linelen \do
  {\@upordown\@clnht\copy\@linechar
   \@tempa
   \advance\@clnht \ht\@linechar
   \advance\@clnwd \wd\@linechar}%
\advance\@clnht -\ht\@linechar
\advance\@clnwd -\wd\@linechar
\@tempdima\@linelen\advance\@tempdima -\@clnwd
\@tempdimb\@tempdima\advance\@tempdimb -\wd\@linechar
\if@negarg \hskip -\@tempdimb \else \hskip \@tempdimb \fi
\multiply\@tempdima \@m
\@tempcnta \@tempdima \@tempdima \wd\@linechar \divide\@tempcnta \@tempdima
\@tempdima \ht\@linechar \multiply\@tempdima \@tempcnta
\divide\@tempdima \@m
\advance\@clnht \@tempdima
\ifdim \@linelen <\wd\@linechar
   \hskip \wd\@linechar
  \else\@upordown\@clnht\copy\@linechar\fi}

%\def\@hline{\ifnum \@xarg <0 \hskip -\@linelen \fi
%\vrule \@height \@halfwidth \@depth \@halfwidth \@width
%\@linelen \ifnum \@xarg <0 \hskip -\@linelen \fi}


\def\@hline{\ifnum \@xarg <0 \hskip -\@linelen \fi
\vrule height \@halfwidth depth \@halfwidth width \@linelen
\ifnum \@xarg <0 \hskip -\@linelen \fi}

\def\@getlinechar(#1,#2){\@tempcnta#1\relax\multiply\@tempcnta 8
\advance\@tempcnta -9 \ifnum #2>0 \advance\@tempcnta #2\relax\else
\advance\@tempcnta -#2\relax\advance\@tempcnta 64 \fi
\char\@tempcnta}

\def\vector(#1,#2)#3{\@xarg #1\relax \@yarg #2\relax
\@linelen=#3\unitlength
\ifnum\@xarg =0 \@vvector
  \else \ifnum\@yarg =0 \@hvector \else \@svector\fi
\fi}

\def\@hvector{\@hline\hbox to 0pt{\@linefnt
\ifnum \@xarg <0 \@getlarrow(1,0)\hss\else
    \hss\@getrarrow(1,0)\fi}}

\def\@vvector{\ifnum \@yarg <0 \@downvector \else \@upvector \fi}

\def\@svector{\@sline
\@tempcnta\@yarg \ifnum\@tempcnta <0 \@tempcnta=-\@tempcnta\fi
\ifnum\@tempcnta <5
  \hskip -\wd\@linechar
  \@upordown\@clnht \hbox{\@linefnt  \if@negarg
  \@getlarrow(\@xarg,\@yyarg) \else \@getrarrow(\@xarg,\@yyarg) \fi}%
\else\@badlinearg\fi}

\def\@getlarrow(#1,#2){\ifnum #2 =\z@ \@tempcnta='33\else
\@tempcnta=#1\relax\multiply\@tempcnta \sixt@@n \advance\@tempcnta
-9 \@tempcntb=#2\relax\multiply\@tempcntb \tw@
\ifnum \@tempcntb >0 \advance\@tempcnta \@tempcntb\relax
\else\advance\@tempcnta -\@tempcntb\advance\@tempcnta 64
\fi\fi\char\@tempcnta}

\def\@getrarrow(#1,#2){\@tempcntb=#2\relax
\ifnum\@tempcntb < 0 \@tempcntb=-\@tempcntb\relax\fi
\ifcase \@tempcntb\relax \@tempcnta='55 \or
\ifnum #1<3 \@tempcnta=#1\relax\multiply\@tempcnta
24 \advance\@tempcnta -6 \else \ifnum #1=3 \@tempcnta=49
\else\@tempcnta=58 \fi\fi\or
\ifnum #1<3 \@tempcnta=#1\relax\multiply\@tempcnta
24 \advance\@tempcnta -3 \else \@tempcnta=51\fi\or
\@tempcnta=#1\relax\multiply\@tempcnta
\sixt@@n \advance\@tempcnta -\tw@ \else
\@tempcnta=#1\relax\multiply\@tempcnta
\sixt@@n \advance\@tempcnta 7 \fi\ifnum #2<0 \advance\@tempcnta 64 \fi
\char\@tempcnta}



\def\@vline{\ifnum \@yarg <0 \@downline \else \@upline\fi}


\def\@upline{\hbox to \z@{\hskip -\@halfwidth \vrule
  width \@wholewidth height \@linelen depth \z@\hss}}

\def\@downline{\hbox to \z@{\hskip -\@halfwidth \vrule
  width \@wholewidth height \z@ depth \@linelen \hss}}

\def\@upvector{\@upline\setbox\@tempboxa\hbox{\@linefnt\char'66}\raise
     \@linelen \hbox to\z@{\lower \ht\@tempboxa\box\@tempboxa\hss}}

\def\@downvector{\@downline\lower \@linelen
      \hbox to \z@{\@linefnt\char'77\hss}}

%INITIALIZATION
\thinlines

\newcount\@xarg
\newcount\@yarg
\newcount\@yyarg
\newcount\@multicnt
\newdimen\@xdim
\newdimen\@ydim
\newbox\@linechar
\newdimen\@linelen
\newdimen\@clnwd
\newdimen\@clnht
\newdimen\@dashdim
\newbox\@dashbox
\newcount\@dashcnt
 \catcode`@=12


% macros supplementaires (J.D.)

\newbox\tbox
\newbox\tboxa

%\def\picbox(#1,#2,#3)#4{\setbox\tbox=\hbox{#4}%
%     \ht\tbox=#1 \wd\tbox=#2 \dp\tbox=#3 \box\tbox}

\def\leftzer#1{\setbox\tbox=\hbox to 0pt{#1\hss}%
     \ht\tbox=0pt \dp\tbox=0pt \box\tbox}

\def\rightzer#1{\setbox\tbox=\hbox to 0pt{\hss #1}%
     \ht\tbox=0pt \dp\tbox=0pt \box\tbox}

\def\centerzer#1{\setbox\tbox=\hbox to 0pt{\hss #1\hss}%
     \ht\tbox=0pt \dp\tbox=0pt \box\tbox}

% sytaxe: \image(hauteur totale reservee, distance
%    verticale de l'origine par rapport au bas de
%    la place reservee){materiel a inserer}
% L'origine est toujours centre horizontalement
%
\def\image(#1,#2)#3{\vbox to #1{\offinterlineskip
    \vss #3 \vskip #2}}

% \leftput place le materiel avec son point de reference
%    en #1,#2 unites \unitlength
% De meme pour \centerput et \rightput

\def\leftput(#1,#2)#3{\setbox\tboxa=\hbox{%
    \kern #1\unitlength
    \raise #2\unitlength\hbox{\leftzer{#3}}}%
    \ht\tboxa=0pt \wd\tboxa=0pt \dp\tboxa=0pt\box\tboxa}

\def\rightput(#1,#2)#3{\setbox\tboxa=\hbox{%
    \kern #1\unitlength
    \raise #2\unitlength\hbox{\rightzer{#3}}}%
    \ht\tboxa=0pt \wd\tboxa=0pt \dp\tboxa=0pt\box\tboxa}

\def\centerput(#1,#2)#3{\setbox\tboxa=\hbox{%
    \kern #1\unitlength
    \raise #2\unitlength\hbox{\centerzer{#3}}}%
    \ht\tboxa=0pt \wd\tboxa=0pt \dp\tboxa=0pt\box\tboxa}

\unitlength=1mm

\let\cput=\centerput

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

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

% ps, need after input
\ifx\pdfoutput\jamaisdefined
\input epsf
\def\HanFig#1{\epsfbox{#1}}
\fi

{\nopagenumbers
\parindent=0pt
\pageno=0

\font\bighelvetica=cmss17 at 30 pt %Helvetica at 25 pt
\font\midhelvetica=cmss17 at 25pt%Helvetica at 20 pt
\font\midmidhelvetica=cmss12 at 20pt %Helvetica at 15 pt
\font\smallhelvetica=cmss12  %Helvetica at 10 pt

\noindent


\null
\vfill
{\bighelvetica 


\bigskip
\centerline{Commutation and Rearrangements}
}

\bigskip




\vskip 2cm
{\midmidhelvetica 
An electronic reedition of the monograph

}
\bigskip\bigskip
{\midhelvetica
\centerline{Probl\`emes combinatoires de}

\smallskip\smallskip
\centerline{commutation et r\'earrangements}

\bigskip
\centerline{by  P. Cartier, D. Foata}
\vfill
\centerline{with three new appendices by}

\bigskip
\centerline{D. Foata, B. Lass}
\smallskip
\centerline{and Ch. Krattenthaler}
\vfill
\centerline{2006}

\eject

}

}
{
\pagetitretrue

\nopagenumbers
\def\leftheadline{\hfil}
\auteurcourant={}\titrecourant={}
\null\vfill\eject  

}

{
\pagetitretrue


\nopagenumbers
\def\leftheadline{\hfil}
\auteurcourant={}\titrecourant={}
\centerline{\bf Foreword}

\bigskip
The monograph ``Probl\`emes combinatoires de commutation et r\'ear\-ran\-ge\-ments"
was originally published as no.~85 in the Springer-Verlag Lecture Notes in Mathematics
Series, back in 1969. The algebraic and combinatorial techniques developed there have
since been used in various branches of mathematics and also computer science. 
The notion of partially commutative monoid, that was first introduced for extending
the MacMahon Master Theorem to the noncommutative case, has been used in other
contexts. In particular, it has provided an appropriate mathematical model for the study
of computer parallelism. The fundamental result deals with an inversion formula,
that has been expressed in different algebraic structures, originally the algebra of a
partially commutative monoid.

It was then appropriate, with this electronic reedition of the monograph, to have
three appendices which could illustrate how that fundamental inversion formula was
implemented in other environments, explicitly and also implicitly. 

In the first appendix (``Inversions de M\"obius") it is shown how to go from the M\"obius
inversion formula for a partially commutative monoid to the M\"obius formula for a
locally finite partially ordered set, and conversely.
 
In the second appendix Bodo Lass shows that by means of a simple specialization of the
variables the fundamental inversion formula provides a noncommutative version of the
celebrated chromatic polynomial identity for graphs:
$(-1)^{|V|}\chi_G(-1)=a(G)$.

The third appendix, written by Christian Krattenthaler, presents Viennot's theory of
heaps of pieces, a theory that has been very fruitful in the combinatorial theory of
orthogonal polynomials and in the calculation of multivariable generating functions
for polyominoes. The equivalence of the theory of heaps and
the theory of partially commutative
monoids is explicitly established.





\vfill





\eject  

}


{


\pagetitretrue

\vglue 1.5cm
\centerline{{\bf COMMUTATION AND REARRANGEMENTS}}

{\parindent=0pt

\bigskip\bigskip
P. Cartier, D. Foata: 

Probl\`emes combinatoires de commutation et
r\'ear\-ran\-ge\-ments,  54 pages.

\bigskip
D. Foata: 

\line{Inversions de M\"obius, 5 pages\leaderfill p.~55}

\bigskip
B. Lass: 

\line{Le polyn\^ome chromatique, 2 pages\leaderfill p.~61}

\bigskip
Ch. Krattenthaler: 

\line{The theory of heaps and the Cartier-Foata monoid, 
11 pages\leaderfill p.~63}
}
\vfill\eject














\nopagenumbers
\pagetitretrue
\parindent=0pt
\pageno=0

\font\bighelvetica=cmss17 at 30 pt %Helvetica at 25 pt
\font\midhelvetica=cmss17 at 25pt%Helvetica at 20 pt
\font\midmidhelvetica=cmss12 at 20pt %Helvetica at 15 pt
\font\smallhelvetica=cmss12  %Helvetica at 10 pt

\noindent
{\bighelvetica
Lecture Notes in

\medskip
Mathematics}

\bigskip
{\smallhelvetica
A collection of informal reports and seminars

Edited by A. Dold, Heidelberg and B. Eckmann, Z\"urich

\bigskip
Series: Institut de Math\'ematique, Universit\'e de Strasbourg

Adviser: P. A. Meyer

}
\bigskip\bigskip


\vfill
{\midhelvetica 85

\medskip
\line{\hrulefill}
\bigskip
P. Cartier $\bullet$ D. Foata

}

\smallskip
{\smallhelvetica Universit\'e de Strasbourg}

\bigskip


\vskip 2cm
{\midhelvetica Probl\`emes combinatoires de

\smallskip\smallskip
commutation et r\'earrangements}

\medskip
\line{\hrulefill}
\vfill
\vfill
{\midmidhelvetica Springer-Verlag

\smallskip
Berlin $\bullet$ Heidelberg $\bullet$ New York 1969} 

\eject

}




{
\pagetitretrue
\null\footnote{}{The present volume is a 2005
\TeX-reproduction of the original text that was originally
published in the Springer-Verlag Lecture Notes in Mathematics
Series  in 1969.}

\nopagenumbers
\def\leftheadline{\hfil}
\auteurcourant={}\titrecourant={}
\null\vfill\eject  

}

{

%\overfullrule=0pt
\pagetitretrue
\titrecourant={\eightrm TABLE DES MATI\`ERES}
\auteurcourant={\eightrm TABLE DES MATI\`ERES}
\vglue 1.5cm
\centerline{{\bf TABLE DES MATI\`ERES}}

\pageno=-3
\def\flead{\leaders\hbox to 4pt{\hss.}\hfill}

\long\def\somr #1|#2|#3|{\hbox{\kern
23pt \vbox{\hsize=10.15cm
\parindent=-23pt
\strut{\pc CHAPITRE|} {#1}.\quad
{\bf #2}\flead\null}\hskip 1pt \hbox to 20pt{\hfill #3}}
\smallskip\goodbreak}

\long\def\somrr #1|#2|#3|{\hbox{\kern
23pt \vbox{\hsize=10.15cm
%\parindent=-23pt
\strut {#1}.\quad
{#2}\flead\null}\hskip 1pt \hbox to 20pt{\hfill #3}}}


\vskip .5cm

{\parindent=0pt

\vskip 8pt minus 2pt
\hbox{\kern
23pt \vbox{\hsize=10.15cm
\parindent=-23pt
\strut {\bf Introduction}\flead\null}\hskip 1pt \hbox to
20pt{\hfill 1}}

\bigskip
\somr {\pc PREMIER|}|Mono\"\i des d\'efinis par des relations
de commutation|5|

\somrr 1|Rappels sur les mono\"\i des libres|5|

\somrr 2|Construction de $L(Z;C)$|6|

\somrr 3|Structure de $L(Z;C)$|7|

\somrr 4|Un exemple|9|

\bigskip
\somr 2|Fonction de M\"obius d'un mono\"\i de|11|

\somrr 1|D\'ecompositions|11|

\somrr 2|Formule d'inversion de M\"obius|12|

\somrr 3|Fonction de M\"obius du mono\"\i de $L(Z;C)$|13|

\somrr 4|Cas particuliers|13|

\bigskip
\somr 3|Circuits dans un graphe|15|

\somrr 1|D\'efinitions|15|

\somrr 2|Structure des flots|16|

\somrr 3|Structure des circuits|17|

\somrr 4|Cycles|18|

\somrr 5|Relation avec les chemins|19|

\somrr 6|D\'ecomposition descendante d'un circuit|21|

\bigskip
\somr 4|R\'earrangements de suites|24|

\somrr 1|Mono\"\i de des r\'earrangements|24|

\somrr 2|D\'ecomposition d'un r\'earrangement en cycles|25|

\somrr 3|Mono\"\i de d'intercalement|26|

\somrr 4|D\'ecomposition descendante d'un mot|29|

\somrr 5|Une m\'ethode de r\'earrangement|30|

\bigskip
\somr 5|Sur le \og Master Theorem\fg\ de MacMahon|33|

\somrr 1|Une g\'en\'eralisation non commutative du 
\og Master Theorem\fg|33|

\somrr 2|Une autre g\'en\'eralisation du th\'eor\`eme de MacMahon|35|

\bigskip\vfill\eject
\somr 6|Relations entre coefficients binomiaux|37|

\somrr 1|Description du graphe|37|

\somrr 2|\'Etude des circuits pairs|37|

\somrr 3|\'Etude des circuits impairs|38|

\somrr 4|Autres identit\'es|39|

\somrr 5|Utilisation du \og Master Theorem\fg\ de
MacMahon|40|

\hbox{\kern
23pt \vbox{\hsize=10.15cm
\strut {Formulaire}\flead\null}\hskip 1pt \hbox to
20pt{\hfill 43}}

\bigskip
\somr 7|Applications probabilistes|45|

\somrr 1|Identit\'e de Spitzer|45|

\somrr 2|Propri\'et\'es du permanent|47|

\somrr 3|Fonctions caract\'eristiques de certaines variables
al\'eatoires|49|

\bigskip

\hbox{\kern
23pt \vbox{\hsize=10.15cm
\parindent=-23pt
\strut {\bf Bibliographie}\flead\null}\hskip 1pt \hbox to
20pt{\hfill 52}}

\bigskip
\hbox{\kern
23pt \vbox{\hsize=10.15cm
\parindent=-23pt
\strut {\bf Index des principales notations}\flead\null}\hskip
1pt
\hbox to 20pt{\hfill 53}}
}}

\vfill\eject


\pageno=1
\pagetitretrue
\auteurcourant={INTRODUCTION}

\vglue 2cm

\vskip 2mm
\centerline{{\bf INTRODUCTION}} 


\vskip 6mm plus 2mm
Dans sa th\`ese [1], l'un d'entre nous a \'etudi\'e les probl\`emes
combinatoires li\'es aux r\'earrangements de suites finies et \`a
la d\'ecomposition en cycles de \og permutations avec
r\'ep\'etitions\fg. Nous reprenons ici ces questions par des
m\'ethodes nouvelles : la nouveaut\'e principale est l'introduction
du mono\"\i de des circuits sur un un graphe et, comme cas
particulier, celle des mono\"\i des de r\'earrangements. Nous
pouvons ainsi donner des d\'emonstrations assez intuitives de
plusieurs th\'eor\`emes de factorisation ; on obtient deux
bijections distinctes de l'ensemble des mots sur l'ensemble des
r\'earrangements, dont la composition redonne un th\'eor\`eme de
r\'earrangement, sans recourir aux construc\-tions \'elabor\'ees
dans~[1]. Nous examinerons maintenant les
principaux th\`emes de ce travail.

\sectiona A. Fonction de M\"obius|
Le but des chapitres I et II est d'\'etablir l'identit\'e g\'en\'erale
$$
\Bigl(\sum_{i_1,\ldots,i_r}
(-1)^r \;T_{i_1}\cdots T_{i_r}\Bigr)^{-1}
=\sum_{j_1,\ldots, j_s}
T_{j_1}\cdots T_{j_s},\leqno(1)
$$
dont la signification est la suivante : on consid\`ere des s\'eries
formelles \`a coefficients entiers en des ind\'etermin\'ees~$T_i$
auxquelles on impose {\it certaines} relations de
commutation
$T_iT_j=T_jT_i$ (\'eventuellement aucune ou toutes). Le membre
de gauche comporte une sommation sur tous les mon\^omes
distincts form\'es de lettres distinctes commutant deux \`a deux
et celui de droite comporte une sommation sur tous les
mon\^omes distincts (si plusieurs mon\^omes se trouvent \^etre
\'egaux en vertu des relations de commutation impos\'ees, on ne
prend que l'un d'entre eux dans la sommation). En sp\'ecialisant
au cas o\`u les ind\'etermin\'ees ne commutent jamais ou au
contraire commutent toujours, on retrouve les identit\'es connues
$$
\leqalignno{
\Bigl(1-\sum_{i=1}^nT_i\Bigr)^{-1}
&=\sum_{r=0}^\infty
\sum_{i_1,\ldots, i_r}
T_{i_1}\cdots T_{i_r};&(2)\cr
\Bigl((1-T_1)\cdots (1-T_n)\Bigr)^{-1}&=
\sum_{\alpha_1,\ldots, \alpha_n}
T_1^{\alpha_1}\cdots T_n^{\alpha_n}.&(3)\cr}
$$

L'\'etablissement de (1) se fait en deux \'etapes. Consid\'erons un
mono\"\i de~$M$ dans lequel tout \'el\'ement n'a qu'un nombre
fini de d\'ecompositions en produit (d'un nombre quelconque de
facteurs). On peut alors former des s\'eries formelles
$\sum_{x\in M} a_x\cdot x$ \`a coefficients entiers par
exemple. Nous montrons qu'il existe une fonction~$\mu_M$
(fonction de M\"obius de~$M$) telle que
$$
\Bigl(\sum_{x\in M}\mu_M(x)\cdot x\Bigr)^{-1}=\sum_{x\in
M} x ;\leqno(4)
$$
cette relation \'equivaut \`a
\quad $\sum\limits_{yz=x}\mu_M(y)=0$ pour
$x\not=1$ et $\mu_M(1)=1$. Lorsque~$M$ est l'ensemble
des entiers strictement positifs, avec la multiplication pour
op\'eration, la fonction~$\mu_M$ est la fonction de M\"obius
usuelle ([2], p.~234) et la relation~(4) \'equivaut \`a l'identit\'e
connue
$$
\Bigl(\sum_{n=1}^\infty\mu(n)\cdot
n^{-s}\Bigr)^{-1}=\sum_{n=1}^\infty n^{-s}.\leqno(5)
$$

Il reste \`a expliciter la fonction~$\mu_M$ pour certains
mono\"\i des. Pour cela, nous \'etudions au chapitre~I les
mono\"\i des engendr\'es par des g\'en\'erateurs~$T_i$ soumis \`a
certaines relations de commutation. Le r\'esultat principal est
le th\'eor\`eme~1.2 qui r\'esout le probl\`eme des mots pour de tels
mono\"\i des, en indiquant une famille r\'eduite et un
algorithme pour la r\'eduction \`a la forme r\'eduite.

\sectiona B. Flots et cycles sur un graphe|
Le chapitre 3 est consacr\'e \`a une g\'en\'eralisation non
commutative de l'homologie. Nous consid\'erons un graphe
orient\'e~$G$ (vari\'et\'e combinatoire orient\'ee de dimension~1) ;
les simplexes de dimension~0 sont appel\'es sommets et ceux de
dimension~1 ar\^etes. On suppose pour simplifier qu'il n'y a
qu'un nombre fini de sommets et d'ar\^etes. Pour $i=0,1$, on
note~$C_i$ le groupe commutatif libre engendr\'e par les
simplexes de dimension~$i$, appel\'e classiquement groupe des
$i$-cha\^\i nes ; l'op\'erateur bord $\partial : C_1\rightarrow C_0$
est carac\-t\'eris\'e par $\partial(a)=t-s$ pour toute ar\^ete~$a$
joignant le sommet~$s$ au sommet~$t$. Le premier groupe
d'homologie~$H_1$ du graphe~$G$ est le noyau de~$\partial$.

Pour tout sommet $s$, soit $\widehat C(s)$ le groupe libre
engendr\'e par les ar\^etes d'origine~$s$ ; notons aussi
$\widehat C_1$ le produit de tous ces groupes $\widehat
C(s)$. Il existe un homomorphisme canonique surjectif
$\pi:\widehat C_1\rightarrow C_1$, dont le noyau est le
groupe des commutateurs de~$\widehat C_1$. Le groupe
$\widehat H_1=\pi^{-1}(H_1)$ m\'erite le nom de premier
groupe d'homologie non commutatif de~$G$.

En fait, nous ne nous int\'eressons qu'au sous-mono\"\i de~$F$
de~$\widehat C_1$ engendr\'e par les ar\^etes, dont les \'el\'ements
sont appel\'es flots. Les \'el\'ements de $F\cap\nobreak \widehat
H_1$ sont appel\'es circuits. Les r\'esultats essentiels sont deux
th\'eor\`emes de d\'ecomposition d'un circuit. Le th\'eor\`eme~3.5
affirme que le mono\"\i de des circuits est du type envisag\'e
au chapitre~I : les g\'en\'erateurs sont des cycles \og
g\'eom\'etriques\fg\ et deux cycles commutent si et seulement
s'ils n'ont aucun sommet en commun. Ce r\'esultat pr\'ecise et
g\'en\'eralise les th\'eor\`emes usuels de d\'ecomposition d'un \og
cycle alg\'ebrique\fg\ en \og cycles g\'eom\'etriques\fg. La
proposition~3.10 fournit une d\'ecomposition d'un circuit en
lacets. La m\'ethode de d\'emonstration s'explique facilement dans
le langage imag\'e des labyrinthes. On dispose d'un labyrinthe,
dont tous les couloirs sont \`a sens unique ; de plus, pour
chaque carrefour, on a \'etabli un ordre de pr\'es\'eance entre les
couloirs partant de ce carrefour (par exemple de la gauche
vers la droite \`a partir d'un d'entre eux) ; enfin, on suppose
remplie la condition bien connue d'Euler : il y a autant de
couloirs aboutissant \`a un carrefour que de couloirs qui en
partent. Partant d'un carrefour d\'etermin\'e, on voyage selon la
r\`egle dite de Tarry : \`a chaque carrefour, choisir pour en
ressortir le premier des couloirs non encore parcourus. On
retourne certainement au point de d\'epart par cette r\`egle,
apr\`es avoir explor\'e tout ou partie du labyrinthe ; si tout n'est
pas explor\'e, on peut visiter le reste en recommen\c cant par une
m\'ethode analogue.

\sectiona C. Applications|
Au chapitre~IV, nous appliquons les r\'esultats pr\'e\-c\'e\-dents
au cas d'un graphe~$G$ ayant la propri\'et\'e suivante : quels que
soient les sommets~$s$ et~$t$, il existe une ar\^ete et une
seule joignant~$s$ \`a~$t$. On suppose l'ensemble~$X$ des
sommets totalement ordonn\'e.

Un mot form\'e de $n$ lettres distinctes dans $X$ est sp\'ecifi\'e
par la donn\'ee de l'ensemble de ces lettres et de la permutation
qui am\`ene ces lettres de l'ordre croissant \`a l'ordre dans le
mot. La d\'ecomposition d'une permutation en cycles fournit
donc une d\'ecomposition d'un mot form\'e de lettres distinctes
en mots cycliques. Nous g\'en\'eralisons ceci \`a tous les mots gr\^ace
\`a la d\'ecomposition en cycles des r\'earrangements (qui sont des
circuits dans~$G)$. En interpr\'etant convenablement le produit
des circuits, nous retrouvons le mono\"\i de d'intercalement
d\'ej\`a introduit dans~[1] ; nous obtenons tr\`es facilement les
r\'esultats le concernant.

MacMahon a fait grand usage du r\'esultat suivant qu'il a
baptis\'e \og Master Theorem\fg\ [3, page~97] :

\medskip
{\sl Soient $X_1$, \dots, $X_n$ des ind\'etermin\'ees
commutatives, $b_{ij}$ des nombres r\'eels~et
$$Y_i=\sum\limits_{j=1}^n b_{ij}X_j.$$ Pour toute suite
de~$n$ entiers positifs $\alpha_1$, \dots~, $\alpha_n$, le
coefficient du mon\^ome $X_1^{\alpha_1}\cdots
X_n^{\alpha_n}$ dans le polyn\^ome $Y_1^{\alpha_1}\cdots
Y_n^{\alpha_n}$ est \'egal au coefficient du m\^eme mon\^ome
dans le d\'eveloppement en s\'erie formelle de l'inverse du
d\'eterminant
$$
\left|\matrix{1-b_{1,1}X_1&{}-b_{1,2}X_2
&\ldots&{}-b_{1,n}X_n\cr
{}-b_{2,1}X_1&1-b_{2,2}X_2
&\ldots&{}-b_{2,n}X_n\cr
\vdots&\vdots&\ddots&\vdots\cr
{}-b_{n,1}X_1&{}-b_{n,2}X_2
&\ldots&1-b_{n,n}X_n\cr}\right|.
$$
}

La d\'emonstration de MacMahon est valable dans tout anneau
commutatif. Nous montrons au chapitre~V que le r\'esultat reste
valable dans un anneau quelconque, pourvu que $b_{ij}$
commute \`a~$b_{i'j'}$, pour $i\not=i'$ (th\'eor\`eme~5.1). En
fait, sous cette forme, le th\'eor\`eme de MacMahon \'equivaut \`a la
d\'etermination de la fonction de M\"obius du mono\"\i de des
circuits sur le graphe~$G$. Par les m\^emes m\'ethodes, nous
obtenons dans la proposition~5.2 une autre g\'en\'eralisation du
\og Master Theorem\fg, d\'ej\`a \'etablie par d'autres moyens
dans~[1].

Un autre r\'esultat de MacMahon est le suivant [3, page 186] :
{\sl pour toute permutation~$\sigma$ de $\{1,2,\ldots,n\}$,
soit $\nu(\sigma)$ le nombre des entiers~$i$ tels que $1\le
i\le n-1$ et $\sigma(i)>i$ et soit $\xi(\sigma)$ le nombre
des entiers~$i$ tels que $1\le i\le n-1$ et
$\sigma(i+1)>\sigma(i)$. Pour tout entier $m\ge 0$, il y a
autant de permutations~$\sigma$ avec $\nu(\sigma)=m$ que
de permutations~$\sigma$ avec $\xi(\sigma)=m$.} En fait, on
peut exhiber une bijection~$\Phi$ de l'ensemble des
permutations sur lui-m\^eme telle que $\xi=\nu\circ\Phi$. Nous
construisons au chapitre~IV une telle bijection dans le cas des
\og permutations avec r\'ep\'etitions\fg\ (ou r\'earrangements) ;
cette bijection a d\'ej\`a \'et\'e introduite dans~[1], mais nous
obtenons ici tr\`es facilement ses propri\'et\'es.

Le chapitre VI est consacr\'e \`a certaines identit\'es entre
coefficients bino\-miaux. Nous employons une m\'ethode
uniforme qui consiste \`a compter de deux mani\`eres diff\'erentes
certains circuits dans un graphe \`a trois sommets. Dans le cas
des circuits de longueur paire, nous retrouvons les identit\'es de
Dixon, Fjeldstad ou Foata [1, chapitre~10]. Dans le cas des
circuits de longueur impaire, nous obtenons toute une s\'erie de
nouvelles identit\'es.

Au chapitre VII, nous appliquons enfin les r\'esultats
combinatoires pr\'e\-c\'e\-dents \`a la d\'etermination des fonctions
caract\'eristiques de certaines variables al\'eatoires. Nous
obtenons une identit\'e tout \`a fait analogue \`a celle de
Spitzer~[5] ; ces r\'esultats g\'en\'eralisent ceux du chapitre~9
de~[1].

C'est un fait connu que l'on explique facilement \`a un ami une
m\'ethode combinatoire sur un exemple explicite et qu'une
r\'edaction suivant les canons math\'ematiques usuels est souvent
lourde et obscure. Nous n'esp\'erons pas que ce travail \'echappe \`a
la r\`egle commune, mais nous souhaitons l'avoir rendu un peu
plus attrayant par la discussion d'exemples. La fonction de
M\"obius a \'et\'e g\'en\'eralis\'ee dans une autre direction par
Rota~[4] ; ses r\'esultats ne recoupent pratiquement pas les
n\^otres. D. E. Knuth, du California Institute of Technology, nous
a appris par lettre qu'il a obtenu les m\^emes identit\'es entre
coefficients binomiaux que nous, par une m\'ethode \`a peu pr\`es
identique. Enfin, nous remercions Sch\"utzenberger et Verdier
pour les nombreuses suggestions qu'ils nous ont faites et qui
sont \`a l'origine de plusieurs des questions \'etudi\'ees ici.

\bigskip\bigskip
\rightline{\vbox{\halign{\hfil #\hfil\cr
Strasbourg, le 15 juin 1968\cr
\noalign{\medskip}
P. CARTIER, D. FOATA\cr}}\qquad}

\vfill\eject

\pagetitretrue

\auteurcourant={{\eightrm 
CHAPITRE PREMIER : RELATIONS
DE COMMUTATION}}

\vglue 2cm
\centerline{{\eightrm CHAPITRE PREMIER}}
\vskip 2mm
\centerline{{\bf MONO\"IDES D\'EFINIS}}
\smallskip
\centerline{\bf PAR DES RELATIONS
DE COMMUTATION}

\vskip 6mm plus 2mm
\sectiona 1. Rappels sur les mono\"\i des libres|
Soit $Z$ un ensemble non vide, dont les \'el\'ements
seront appel\'es {\it lettres}. Un {\it mot} est une suite finie
$w=z_1\cdots z_m$ de lettres ; l'entier $m\ge 1$ est appel\'e
la {\it longueur} du mot~$w$. On convient qu'il existe aussi
un mot vide, not\'e~1, de longueur~0 et qui n'a aucune lettre.
Si $w=z_1\cdots z_m$ et $w'=z'_1\cdots z'_n$ sont deux mots
non vides, leur {\it produit} $w''=ww'=w\cdot w'$ est obtenu
par juxtaposition de~$w$ et~$w'$, c'est-\`a-dire que l'on a
$w''=z''_1\cdots z''_{m+n}$ avec $z''_i=z_i$ pour $1\le i\le
m$ et $z''_i=z'_{i-m}$ pour $m+1\le i\le m+n$. On convient
que $w\cdot 1=1\cdot w=w$ pour tout mot~$w$. Pour cette
op\'eration, l'ensemble des mots est un mono\"\i
de,\footnote{$(^1)$}{Un mono\"\i de est un ensemble muni
d'une multiplication associative, avec \'el\'ement unit\'e. Si~$M$
est un mono\"\i de, un sous-mono\"\i de est une partie
de~$M$ stable par multiplication et contenant l'\'el\'ement unit\'e
de~$M$.} not\'e $\Mo(Z)$ et appel\'e
{\it mono\"\i de libre} construit sur~$Z$.

On note $\Ab(Z)$ l'ensemble des fonctions \`a valeurs enti\`eres
positives~$f$ sur~$Z$, telles que l'ensemble $\{z\in Z\mid
f(z)\not=0\}$ soit fini. La somme $f+g$ de deux \'el\'ements~$f$
et~$g$ de $\Ab(Z)$ est la fonction d\'efinie par
$(f+g)(z)=f(z)+g(z)$ pour tout $z\in Z$. Pour cette addition,
$\Ab(Z)$ est un mono\"\i de commutatif appel\'e le {\it
mono\"\i de commutatif libre construit
sur}~$Z$.

Pour tout $z\in Z$, on d\'efinit un \'el\'ement $\epsilon_z$ de
$\Ab(Z)$ par $\epsilon_z(z)=1$ et $\epsilon_z(z')=0$
pour~$z'$ distinct de~$z$. Pour tout mot $w=z_1\cdots z_m$,
on note $\epsilon(w)$ l'\'el\'ement $\epsilon_{z_1}+\cdots+
\epsilon_{z_m}$ de $\Ab(Z)$. L'application~$\epsilon$ est
homomorphisme \footnote{$(^2)$}{Soient $M$ et $M'$ deux 
mono\"\i des, dont on note 1 les \'el\'ements unit\'es. Un
homomorphisme de~$M$ sur~$M'$ est une application~$f$
de~$M$ dans~$M'$ telle que $f(xy)=f(x)f(y)$ et $f(1)=1$.}
de $\Mo(Z)$ sur $\Ab(Z)$. On dit qu'un mot $w'=z'_1\cdots
z'_n$ est un r\'earrangement de $w=z_1\cdots z_m$ si l'on a
$\epsilon(w)=\epsilon(w')$ ; il revient au m\^eme de dire que
toute lettre~$z$ intervient un m\^eme nombre de fois dans~$w$
et dans~$w'$, ou encore qu'on a $m=n$ et qu'il existe une
permutation~$\sigma$ de $\{1,2,\cdots,m\}$ avec
$z'_i=z_{\sigma(i)}$ pour $1\le i\le m$.

\vskip0pt plus 30pt
\sectiona 2. Construction de $L(Z;C)$|
Soient $Z$ un ensemble et $C$ une partie de $Z\times Z$ ;
on suppose que, pour $(z,z')$ dans~$C$, on a 
$z\not=z'$ et
$(z',z)\in C$. On dit que deux mots~$w$ et~$w'$~sont 
$C$-{\it adja\-cents} s'il existe deux mots~$u$ et~$v$ et
un couple $(z,z')$ dans~$C$ avec 
$w=uzz'v$ et $w'=uz'zv$ ; on
dit que les mots~$w$ et~$w'$ sont~$C$-{\it \'equivalents}
s'ils sont \'egaux ou s'il existe une suite de mots $w_0$,
$w_1$, \dots~, $w_p$ telle que $w_0=w$, $w_p=w'$ et
$w_{i-1}$ et~$w_i$ soient $C$-adjacents pour $1\le i\le
p$. On d\'efinit ainsi une relation d'\'equivalence~$R_C$ dans
$\Mo(Z)$, compatible avec la multiplication ; le mono\"\i de
quotient $\Mo(Z)/R_C$ sera not\'e $L(Z;C)$, son \'el\'ement neutre
sera not\'e~1 et la classe de $C$-\'equivalence d'une lettre~$z$
sera not\'ee $[z]$. L'application $z\mapsto [z]$ est injective
et $L(Z;C)$ est engendr\'e par l'ensemble des \'el\'ements de la
forme~$[z]$. On dira que deux lettres~$z$ et~$z'$ {\it
commutent} si l'on a $[z]\cdot [z']=[z']\cdot [z]$ dans
$L(Z;C)$ ; l'ensemble~$C$ se compose alors des couples de
lettres distinctes qui commutent.

Soient $M$ un mono\"\i de, $(x_i)_{i\in I}$ une famille
d'\'el\'ements de~$M$ et~$C$ une partie de $I\times I$ telle que
$(i,j)\in C$ entra\^\i ne $i\not =j$ et $(j,i)\in C$. On dit
que~$M$ est {\it engendr\'e par l'ensemble des $x_i$ $(i\in
I)$ soumis aux relations de commutation $x_ix_j=x_jx_i$
pour $(i,j)\in C$} s'il existe un isomorphisme $\varphi:
L(I;C)\rightarrow M$ tel que $\varphi[i]=x_i$ pour tout $i\in
I$.

\th Lemme 1.1|Soient $M$ un mono\"\i de et~$f$ une application
de~$Z$ dans~$M$ ; on suppose que pour $(z,z')$ dans~$C$,
les \'el\'ements $f(z)$ et $f(z')$ de~$M$ commutent. Il existe
alors un homomorphisme~$\overline f$ de $L(Z;C)$ dans~$M$
et un seul, tel que $f(z)=\overline f([z])$ pour toute
lettre~$z$.
\finth

Si $w=z_1\cdots z_m$ et $w'=z'_1\cdots z'_m$ sont deux
mots~$C$-\'equivalents, on a $f(z_1)\cdots
f(z_m)=f(z'_1)\cdots f(z'_m)$ : cela r\'esulte de l'hypoth\`ese
sur~$f$ lorsque~$w$ et~$w'$ sont $C$-adjacents et le cas
g\'en\'eral se d\'eduit de l\`a de proche en proche. Il existe donc une
application~$\overline f$ de $L(Z;C)$ dans~$M$ d\'efinie par
$\overline f([z_1]\cdots [z_m])=f(z_1)\cdots f(z_m)$
et~$\overline f$ r\'epond \`a la question pos\'ee.\cqfd

\medskip
Comme $\Ab(Z)$ est commutatif, le lemme 1.1 assure
l'existence d'un homomorphisme~$\pi$ de $L(Z;C)$ dans
$\Ab(Z)$ tel que $\pi([z])=\epsilon_z$ pour toute lettre~$z$
; si l'on note~$\lambda$ l'homomorphisme de~$\Mo(Z)$ dans
$L(Z;C)$ d\'efini par $\lambda (z_1\cdots z_m)=[z_1]\cdots
[z_m]$, on a $\epsilon =\pi\circ \lambda$, d'o\`u le
diagramme commutatif

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

$$\vbox{\offinterlineskip
\medskip
\centerput(-2,0){$\Mo(Z)$}
\fleche(5,0)\dir(1,0)\long{20}
\centerput(32,0){$\Ab(Z)$}
\centerput(15,2){$\epsilon$}
\centerput(-2,-6){$\lambda$}
\fleche(0,-2)\dir(0,-1)\long{7}
\fleche(7,-11)\dir(2,1)\long{18}
\centerput(15,-10){$\pi$}
\centerput(0,-14){$L(Z;C)$}\vskip 1.5cm
}\hskip3cm
$$

Le lemme 1.1 d\'emontre aussi l'existence d'une
application~$\iota$ de $L(Z;C)$ dans lui-m\^eme caract\'eris\'ee
par les formules
$$
\iota(1)=1,\quad \iota([z])=[z], \quad \iota(uv)=\iota(v)\iota(u)
\leqno(1)
$$
pour toute lettre~$z$ et $u$, $v$ dans $L(Z;C)$. On a 
$\iota([z_1]\cdots [z_m])=[z_m]\cdots [z_1]$, d'o\`u
$$
\iota(\iota(u))=u\quad\hbox{pour tout $u$ dans }L(Z;C).
\leqno(2)
$$
On dit que $\iota$ est l'{\it involution} dans $L(Z;C)$.

\goodbreak
\sectiona 3. Structure de $L(Z;C)$|
On dit qu'une partie $F$ de $Z$ est {\it commutative} si elle
est finie, non vide et si deux de ses \'el\'ements commutent
toujours ; on pose dans ce cas $[F]=\prod\limits_{z\in F} [z]$.
On pose aussi $[\emptyset]=1$. On dit qu'une lettre~$z$ est
{\it li\'ee} \`a une partie~$F$ de~$Z$ si l'on a $z\in F$ ou s'il
existe une lettre dans~$F$ qui ne commute pas \`a~$z$. Si~$F$
et~$F'$ sont deux parties de~$Z$, on dit que~$F$ est {\it
contigu\"e} \`a~$F'$ si toute lettre de~$F'$ est li\'ee \`a~$F$ ;
on appelle $V$-{\it suite} toute suite $(F_1,\ldots, F_r)$ de
parties commutatives de~$Z$, telle que~$F_i$ soit contigu\"e
\`a~$F_{i+1}$ pour $1\le i\le r-1$ et l'on convient d'une
$V$-suite vide not\'ee~$o$.

\th Th\'eor\`eme 1.2|Tout \'el\'ement $u$ de $L(Z;C)$ admet une
$V$-d\'ecompo\-si\-tion, c'est-\`a-dire une $V$-suite
$(F_1,\ldots, F_r)$ telle que $u=[F_1]\cdots [F_r]$ ; celle-ci
est unique.
\finth

\rema {\rm (A)} Existence d'une $V$-d\'ecomposition :|Pour
toute
$V$-suite $s=(F_1,\ldots, F_r)$, on pose
$p(s)=[F_1]\cdots [F_r]$ avec la convention $p(o)=1$. De
plus, pour toute $V$-suite $s=(F_1,\ldots, F_r)$ et toute
lettre~$z$, nous d\'efinirons une suite $s\cdot z$ de parties
de~$Z$ par les r\`egles suivantes :

\decale(1)|Si $z$ est li\'ee \`a $F_r$, on pose $s\cdot
z=(F_1,\ldots, F_r,\{z\})$ (cas particulier $o\cdot z=\{z\}$).

\decale(2)|Si $z$ n'est pas li\'ee \`a $F_r$, notons $j$ le plus
petit des entiers compris entre~1 et~$r$ et tels que~$z$ ne
soit li\'ee \`a aucune des parties~$F_k$ pour $j\le k\le r$. On
pose alors $s\cdot z=(F_1',\ldots, F_r')$ avec $F'_i=F_i$ pour
$i\not =j$ et $F'_j=F_j\cup \{z\}$.

Si une lettre $z$ est li\'ee \`a une partie $F$ de $Z$, elle est
li\'ee \`a toute partie de~$Z$ contenant~$F$ ; si, au contraire,
$z$ n'est pas li\'ee \`a une partie commutative~$F$, alors
$F\cdot\{z\}$ est commutative. Ces remarques prouvent que
$s\cdot z$ est une $V$-suite pour toute $V$-suite~$s$. De
plus, on a la relation
$$
p(s\cdot z)=p(s)\cdot [z] ;\leqno(3)
$$
cette relation est \'evidente dans le cas (1). Dans le cas (2), la
lettre~$z$ n'est pas li\'ee \`a $F_j$, $F_{j+1}$, \dots~, $F_r$,
donc~$[z]$ commute \`a $[F_{j+1}]\cdots [F_r]$ et l'on a
$[F_j]\cdot [z]=[F_j\cup \{z\}]$ car $z\not \in F_j$ ; on en
d\'eduit $[F_j]\cdot [F_{j+1}]\cdots [F_r]\cdot [z]= [F_j\cup
\{z\}]\cdot [F_{j+1}]\cdots [F_r]$, d'o\`u encore~(3).

Soit alors $u=[z_1]\cdots [z_m]$ un \'el\'ement de $L(Z;C)$ ;
on pose
$$s=(\cdots((o\cdot z_1)\cdot z_2)\cdot\,\ldots\,\cdot z_m).$$
De $p(o)=1$ et de la formule~(3), on d\'eduit par r\'ecurrence
sur~$m$ la relation $p(s)=u$, c'est-\`a-dire que~$s$ est une
$V$-d\'ecomposition de~$u$.

\medskip
\rema {\rm (B)} Unicit\'e d'une $V$-d\'ecomposition :|
Soient $s=(F_1,\ldots, F_r)$ une $V$-suite non vide et $z_1$,
$z_2$ deux lettres dis\-tinctes qui commutent. Soit $n\in
\{1,2\}$ ; lorsque~$z_n$ n'est pas li\'ee \`a~$F_r$, on
notera~$j_n$ le plus petit des entiers compris entre~1 et~$r$
et tels que~$z_n$ ne soit li\'ee \`a aucune des parties~$F_k$
pour $j_n\le k\le r$. Par application des r\`egles (1) et (2) qui
d\'efinissent $s\cdot z$, on obient facilement le tableau suivant.

$$
\vbox{\offinterlineskip\halign{\vrule 
\hfil\thinspace #\thinspace\hfil\vrule
&\vrule height10pt depth 6pt width 0pt\hfil\thinspace
#\thinspace\hfil\vrule &\thinspace
#\thinspace\hfil\vrule\cr
\noalign{\hrule}
$z_1$ li\'ee \`a $F_r$&$z_2$ li\'ee \`a $F_r$&\kern 1.8cm$(s\cdot
z_1)\cdot z_2$\cr
\noalign{\hrule}
oui&oui&\kern 1.8cm $(F_1,\ldots, F_r,\{z_1,z_2\})$\cr
\noalign{\hrule}
oui&non&\kern 1.8cm $(F_1,\ldots, F_{j_2}\cup \{z_2\},\ldots,
F_r,\{z_1\})$\cr
\noalign{\hrule}
non&oui&\kern1.8cm $(F_1,\ldots, F_{j_1}\cup \{z_1\},\ldots,
F_r, \{z_2\})$\cr
\noalign{\hrule}
 non&non&$\cases{j_1=j_2&$(F_1,\ldots,
F_{j_1}\cup
\{z_1,z_2\}, \ldots, F_r)$\cr
j_1\not=j_2&$(F_1',\ldots, F_r')$ avec $F'_i=F_i$\cr}$\cr
&&\kern 4.4cm pour $i\not \in \{j_1,j_2\}$\cr 
&&\kern1.8cm $F'_{j_n}=F_{j_n}\cup\{z_n\}$ pour $z\in
\{1,2\}$.\cr
\noalign{\hrule}
}}$$

Comme $z_2$ n'est pas li\'ee \`a $\{z_1\}$, on a par ailleurs
$(o\cdot z_1)\cdot z_2=\{z_1,z_2\}$. Il r\'esulte alors du
tableau pr\'ec\'edent que l'on a dans tous les cas pr\'ec\'edents la
relation
$$
(s\cdot z_1)\cdot z_2=(s\cdot z_2)\cdot z_1
\quad\hbox{pour toute $V$-suite }s.\leqno(4)
$$

Soient $w=z_1\cdots z_m$ et $w'=z_1'\cdots z_m'$ deux mots.
Si~$w$ et~$w'$ sont $C$-adjacents,  la formule~(4) entra\^\i ne
$(\cdots(o\cdot z_1)\cdot\,\ldots\,\cdot z_m)
=(\cdots(o\cdot z_1')\cdot\,\ldots\,\cdot z_m')$
et la m\^eme conclusion subsiste \'evidemment si~$w$ et~$w'$
sont seulement suppos\'es $C$-\'equivalents. Il existe donc une
application~$q$ de $L(Z;C)$ dans l'ensemble des $V$-suites
d\'efinie par
$$
q([z_1]\cdots [z_m])=(\cdots((o\cdot z_1)\cdot z_2)\cdot\,
\ldots \,\cdot z_m).\leqno(5)
$$

Soit $u$ un \'el\'ement de $L(Z;C)$. Nous allons montrer que
toute $V$-d\'ecomposition $s=(F_1,\ldots, F_r)$ de~$u$ est
\'egale \`a~$q(u)$. Nous raisonnerons par r\'ecurrence sur~$r$,
le cas $r=0$ \'etant trivial (il correspond \`a $u=1$ et
$q(u)=s=o$). Si l'on pose $v=[F_1]\cdots [F_{r-1}]$ et
$F_r=\{z_1,\ldots, z_m\}$, on a $q(v)=(F_1, \ldots, F_{r-1})$
par hypoth\`ese de r\'ecurrence et $u=v\cdot [z_1]\cdots
[z_m]$, d'o\`u $q(u)=(F_1,\ldots, F_{r-1})\cdot z_1\cdot\,
\ldots\,\cdot z_m$ ; comme~$z_1$ est li\'ee \`a $F_{r-1}$ et
que $z_{j+1}$ n'est pas li\'ee \`a $\{z_1,\ldots, z_j\}$ pour $1\le
j\le m-1$, une application r\'ep\'et\'ee des r\`egles (1) et (2) donne
$q(u)=(F_1,\ldots, F_r)$.\cqfd

\th Corollaire 1.3|La multiplication dans le mono\"\i de $L(Z;C)$
est simplifiable.
\finth

Soient $z$ une lettre, $t$ un \'el\'ement de $L(Z;C)$ et
$(H_1,\ldots, H_s)$ la $V$-d\'ecomposition de~$t$. Supposons
qu'il existe un \'el\'ement~$u$ de $L(Z;C)$, de
$V$-d\'ecomposition $(F_1,\ldots, F_r)$, tel que $t=u\cdot
[z]$ ; nous dirons qu'on est dans le cas~(1) ou dans le cas~(2)
selon que~$z$ est li\'ee \`a~$F_r$ ou non. Dans le cas~(1), on~a
$r=s-1$ et $H_s=\{z\}$. Dans le cas~(2), soit~$j$ le plus
petit des entiers compris entre~1 et~$r$ tels que~$z$ ne soit
pas li\'ee \`a~$F_k$ pour $j\le k\le r$ ; on a alors $s=r$ et si
$j<r$, on a $H_s=F_r$ et comme~$z$ n'est pas li\'ee \`a~$F_r$,
on a $z\not \in H_s$ ; si, au contraire, on a $j=r$, on a
$z\not\in F_r$ et $H_s=F_r\cup \{z\}$ ; quel que soit~$j$,
on a donc $H_s\not=\{z\}$.

\goodbreak
On peut donc conclure que l'on est dans le cas~(1) ou~(2) selon
que $H_s$ est \'egal \`a~$\{z\}$ ou non. Dans le cas~(1), on a
$u=[H_1]\cdots [H_{s-1}]$ ; dans le cas~(2), $j$ est le plus
grand des entiers~$\ell$ compris entre~1 et~$r$ tels que
$z\in H_\ell$ et l'on a $u=[H_1]\cdots [H_{j-1}][H_j\setminus
\{z\}][H_{j+1}]\cdots [H_r]$. Il existe donc au plus un
\'el\'ement~$u$ de $L(Z;C)$ tel que $t=u\cdot [z]$.

Soient alors $u$, $u'$ et $v$ des \'el\'ements de $L(Z;C)$.
Comme $u\cdot [z]=u'\cdot [z]$ entra\^\i ne $u=u'$ pour toute
lettre~$z$, une r\'ecurrence sur la longueur de~$v$ montre que
$uv=u'v$ entra\^\i ne $u=u'$. Par ailleurs, de $vu=vu'$, on
d\'eduit $\iota (u)\iota(v)=\iota(vu)=\iota(vu')=\iota(u')\iota(v)$,
d'o\`u $\iota(u)=\iota(u')$ en simplifiant par~$\iota(v)$ ;
finalement, on a $u=u'$ d'apr\`es la formule~(2) du
n\omini~2.\cqfd

\th Corollaire 1.4|Soient $u$ un \'el\'ement de $L(Z;C)$ distinct
de~$1$, $(F_1,\ldots, F_r)$ sa $V$-d\'ecomposition et~$F$
une partie commutative de~$Z$. Pour qu'il existe~$v$ dans
$L(Z;C)$ avec $u=[F]\cdot v$, il faut et il suffit que l'on ait
$F\subset F_1$.
\finth


Lorsque $F$ est contenue dans $F_1$, on a $u=[F]\cdot v$
avec $v=[F_1\setminus F]\cdot [F_2].\cdots .[F_r]$.
Posons $\Phi(1)=\emptyset$ ; pour tout \'el\'ement $v\not =1$
de $L(Z;C)$, notons $\Phi(v)$ le premier \'el\'ement de sa
$V$-d\'ecomposition. D'apr\`es la partie~(A) de la d\'emonstration
du th\'eor\`eme~1.2, on a $\Phi(v\cdot [z])\supset\Phi(v)$ pour
tout $v$ dans $L(Z;C)$ et toute lettre~$z$ ; par r\'ecurrence
sur la longueur de~$v'$, on en d\'eduit $\Phi(vv')\supset
\Phi(v)$ pour $v$, $v'$ dans $L(Z;C)$. Enfin, on a
$\Phi([F])=F$ pour toute partie commutative~$F$. S'il
existe~$v$ dans $L(Z;C)$ avec $u=[F]\cdot v$, on a donc
$F=\Phi([F])\subset \Phi(u)=F_1$.\cqfd

\sectiona 4. Un exemple|
Pour simplifier l'\'ecriture, on \'ecrira une suite $(w_1,\ldots,
w_p)$ de mots sous la forme
$w_1\mid w_2\mid\cdots\mid w_p$. Par exemple, l'\'ecriture
$a\,b\,c\mid d\,d\,c\,a\mid b\,b\mid c$ d\'esigne la suite des
mots $w_1=abc$, $w_2=ddca$, $w_3=bb$, $w_4=c$ ; on dit
que la suite pr\'ec\'edente est une d\'ecomposition du mot
$w_1w_2w_3w_4=abcddcabbc$.

Supposons l'ensemble $Z$ totalement ordonn\'e. A toute partie
commutative~$F$ on associera le mot form\'e en rangeant les
\'el\'ements de~$F$ par ordre croissant. Si $(F_1,\ldots, F_r)$
est la $V$-d\'ecomposition d'un \'el\'ement de $L(Z;C)$, on
l'\'ecrira sous la forme $w_1\mid w_2\mid \cdots\mid w_r$
o\`u~$w_j$ est le mot associ\'e \`a~$F_j$.

On est donc amen\'e \`a consid\'erer des mots coup\'es en
compartiments par des barres $\mid$. Une lettre a le droit de
se d\'eplacer vers la gauche de deux mani\`eres diff\'erentes :

(a) \`a l'int\'erieur de son compartiment, elle peut sauter toutes
les lettres qui lui sont strictement sup\'erieures dans l'ordre
de~$Z$ ;

(b) elle peut sauter dans le compartiment imm\'ediatement \`a sa
gauche si elle est distincte des lettres dudit compartiment et
commute avec elles.

Une $V$-suite correspond ainsi \`a un mot compartiment\'e dans
lequel aucune lettre n'a le droit de se d\'eplacer. Pour
d\'eterminer la $V$-d\'ecomposition d'un \'el\'ement $u=[z_1]\cdots
[z_m]$, on d\'etermine successivement les $V$-d\'ecompositions
des \'el\'ements $u_j=[z_1]\cdots [z_j]$ pour $1\le j\le m$.
Ayant la $V$-d\'ecomposition de~$u_j$, on ajoute
$z_{j+1}$ \`a droite ; si $z_{j+1}$ est \'egale \`a une lettre du
dernier compartiment, ou ne commute pas avec toutes les
lettres dudit compartiment, on cr\'ee un nouveau compartiment
\`a droite pour elle. Sinon, on la d\'eplace le plus loin possible
vers la gauche.

Pour un exemple, consid\'erons un ensemble $Z$ \`a cinq
\'el\'ements $a,b,c,d,e$, ordonn\'e par $a<b<c<d<e$ ; l'ensemble
$C\subset Z\times Z$ se compose des cases non barr\'ees dans le
tableau suivant.

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

$$\vbox{\offinterlineskip
\medskip
\centerput(2.5,1){$a$}
\centerput(7.5,1){$b$}
\centerput(12.5,1){$c$}
\centerput(17.5,1){$d$}
\centerput(22.5,1){$e$}
%
\segment(0,0)\dir(1,0)\long{25}
\segment(0,-5)\dir(1,0)\long{25}
\segment(0,-10)\dir(1,0)\long{25}
\segment(0,-15)\dir(1,0)\long{25}
\segment(0,-20)\dir(1,0)\long{25}
\segment(0,-25)\dir(1,0)\long{25}
%
\segment(0,0)\dir(0,-1)\long{25}
\segment(5,0)\dir(0,-1)\long{25}
\segment(10,0)\dir(0,-1)\long{25}
\segment(15,0)\dir(0,-1)\long{25}
\segment(20,0)\dir(0,-1)\long{25}
\segment(25,0)\dir(0,-1)\long{25}
%
\centerput(-2,-3){$a$}
\centerput(-2,-8){$b$}
\centerput(-2,-13){$c$}
\centerput(-2,-18){$d$}
\centerput(-2,-23){$e$}
%
\segment(0,0)\dir(1,-1)\long{25}
\segment(5,0)\dir(1,-1)\long{5}
\segment(0,-5)\dir(1,-1)\long{5}
\segment(5,-15)\dir(1,-1)\long{10}
\segment(0,-15)\dir(1,-1)\long{5}
\segment(15,-5)\dir(1,-1)\long{10}
\segment(15,0)\dir(1,-1)\long{5}
%
\segment(5,0)\dir(-1,-1)\long{5}
\segment(10,0)\dir(-1,-1)\long{10}
\segment(10,-5)\dir(-1,-1)\long{5}
\segment(5,0)\dir(-1,-1)\long{5}
\segment(20,0)\dir(-1,-1)\long{5}
\segment(20,-5)\dir(-1,-1)\long{15}
\segment(5,-15)\dir(-1,-1)\long{5}
\segment(15,-10)\dir(-1,-1)\long{10}
\segment(25,-10)\dir(-1,-1)\long{15}
\segment(25,-20)\dir(-1,-1)\long{5}
\vskip3cm
}\hskip2.2cm
$$

\noindent
On consid\`ere l'\'el\'ement
$u=\lambda(a\,b\,c\,c\,d\,a\,b\,c\,b\,c\,e\,d)$ de
$L(Z;C)$ ; on a alors $u_1=\lambda (a)$, $u_2=\lambda (ab)$,
\dots\ et si $v_j$ est la $V$-d\'ecomposition de~$u_j$, on a
le tableau suivant :
$$
\vbox{\halign{$#$\hfil\qquad&$#$\hfil\cr
\eqalign{v_1&=a\cr
v_2&=a\mid b\cr
v_3&=a\,c\mid b\cr
v_4&=a\,c\mid b\,c\cr
v_5&=a\,c\mid b\,c\mid d\cr
v_6&=a\,c\mid b\,c\mid d\mid a\cr}%
&\eqalign{v_7&=a\,c\mid b\,c\mid d\mid a\mid b\cr
v_8&=a\,c\mid b\,c\mid c\,d\mid a\mid b\cr
v_9&=a\,c\mid b\,c\mid c\,d\mid a\mid b\mid b\cr
v_{10}&=a\,c\mid b\,c\mid c\,d\mid a\,c\mid b\mid b\cr
v_{11}&=a\,c\mid b\,c\mid c\,d\mid a\,c\mid b\,e\mid b\cr
v_{12}&=a\,c\mid b\,c\mid c\,d\mid a\,c\mid b\,e\mid
b\mid d.\cr}\cr}}
$$
Finalement, la $V$-d\'ecomposition de~$u$ est
$a\,c\mid b\,c\mid c\,d\mid a\,c\mid b\,e\mid
b\mid d$.

\vfill\eject 

\pagetitretrue

\auteurcourant={{\eightrm 
CHAPITRE II : FONCTION DE M\"OBIUS D'UN MONO\"IDE}}

\vglue 2cm
\centerline{{\eightrm CHAPITRE II}}
\vskip 2mm
\centerline{{\bf FONCTION DE M\"OBIUS D'UN MONO\"IDE}}

\vskip 6mm plus 2mm
\sectiona 1. D\'ecompositions|On note $M$ un mono\"\i de, 1 son
\'el\'ement unit\'e et $M^*$ l'ensemble des \'el\'ements distincts de~1
dans~$M$. On appelle {\it d\'ecomposition} d'un \'el\'ement~$x$
de~$M$ toute suite finie $s=(x_1,\ldots, x_q)$ d'\'el\'ements
de~$M^*$ telle que $x=x_1\cdots x_q$ ; l'entier~$q\ge 1$
s'appelle le {\it degr\'e} de la d\'ecomposition~$s$. On admet par
convention une d\'ecomposition vide de~1, de degr\'e~0. {\it Dans
ce n\omini\ et le suivant, on suppose que tout \'el\'ement de~$M$
n'admet qu'un nombre fini de
d\'ecompositions}. \footnote{$(^3)$}{Cette hypoth\`ese \'equivaut \`a
la conjonction des ceux conditions:

(a) Pour tout $x\in M$, il n'existe qu'un nombre fini de
couples $(y,z)$ avec $x=yz$.

(b) Pour tout $x\in M$, il existe un entier $q\ge 1$ tel qu'il
n'y ait aucune d\'ecomposition de longueur strictement
sup\'erieure \`a~$q$ de~$x$.

L'exemple d'un groupe \`a deux \'el\'ements montre que la seconde
condition n'est pas cons\'equence de la premi\`ere.}

\th Lemme 2.1|L'\'el\'ement $1$ n'admet que la d\'ecomposition
vide.
\finth

Il n'existe aucune d\'ecomposition de degr\'e~1 de~1. Supposons
qu'il existe un entier $q\ge 2$ et des \'el\'ements $x_1$, \dots~,
$x_q$ de~$M^*$ tels que $1=x_1\cdots x_q$ ; si l'on pose
$a=x_1$ et $b=x_2\cdots x_q$, on a $a\not =1$ et $ab=1$,
d'o\`u $b\not =1$. Pour tout entier $m\ge 1$, on a alors
$1=(ab)^m$ d'o\`u une d\'ecomposition de degr\'e~$2m$ de~1. Il
existe donc une infinit\'e de d\'ecompositions de~1,
contrairement aux hypoth\`eses faites.\cqfd

\medskip
Pour tout \'el\'ement $x$ de $M$, on note $d(x)$ le nombre des
d\'ecompositions de~$x$, puis $d_+(x)$ celui des
d\'ecompositions de degr\'e pair et $d_-(x)$ celui des
d\'ecompositions de degr\'e impair. On a \'evidemment les relations
$$
d(x)=d_+(x)+d_-(x),\quad d(1)=d_+(1)=1,\quad d_-(1)=0.
\leqno(1)
$$
La {\it fonction de M\"obius} du mono\"\i de $M$ est d\'efinie par 
$\mu_M(x)=d_+(x)-d_-(x)$ ; en particulier, on a
$\mu_M(1)=1$.

\vfill\eject
\sectiona 2. Formule d'inversion de M\"obius|On note~$A$
l'ensemble des fonctions \`a valeurs enti\`eres sur~$M$.
\footnote{$(^4)$}{On pourrait plus g\'en\'eralement consid\'erer
des fonctions sur~$M$ \`a valeurs dans un anneau
commutatif~$K$ avec \'el\'ement unit\'e. On obtient ainsi l'alg\`ebre
large du mono\"\i de~$M$ \`a coefficients dans l'anneau~$K$ (\cf.
Bourbaki, Alg. II, 2\emini~\'edition, \S\kern2pt 7, n\omini~10).}
Nous munirons~$A$ de la structure d'anneau dont les
op\'erations sont donn\'ees par
les r\`egles
$$\leqalignno{(f+g)(x)&=f(x)+g(x);&(2)\cr
(fg)(x)&=\sum_{x_1x_2=x}f(x_1)\cdot g(x_2).&(3)\cr}
$$
L'\'el\'ement unit\'e de l'anneau $A$ est la fonction~$\epsilon$
d\'efinie par $\epsilon(1)=1$ et $\epsilon(x)=0$ pour $x\not
=1$. Dans~(3), la somme est \'etendue \`a tous les couples
$(x_1,x_2)$ tels que $x_1x_2=x$, \`a savoir les couples
$(x,1)$, $(1,x)$ et les d\'ecompositions de degr\'e~2 de~$x$.
D'apr\`es le lemme~2.1, on a donc
$$
(fg)(1)=f(1)g(1)\quad{\rm pour}\ f,g\ {\rm dans}\ A.\leqno(4)
$$

\th Lemme 2.2|Soit $\zeta$ la fonction constante \'egale
\`a~$1$ sur~$M$. On a les relations
$$
\leqalignno{\noalign{\vskip-2pt}
\zeta\,d_+=d_+\,\zeta=d,\quad&\quad
\zeta\,d_-=d_-\,\zeta=d-\epsilon,&(5)\cr
\zeta\,\mu_M=&\;\mu_M\,\zeta=\epsilon.&(6)\cr}
$$
\finth

Comme on a $\zeta(1)=d(1)=d_+(1)=\epsilon(1)=1$ et
$d_-(1)=0$, la formule~(4) montre que les fonctions
$\zeta d_+$, $d_+\zeta$ et~$d$ prennent la valeur~1 en~1
et que $\zeta d_-$, $d_-\zeta$ et $d-\epsilon$ s'annulent
en~1. Soit~$x$ dans~$M^*$ ; on a
$$(d_+\,\zeta)(x)=\sum_{yz=x}d_+(y)=d_+(x)
+\sum_{z\not=1,\,yz=x}d_+(y).\leqno(7)
$$
La premi\`ere somme dans (7) repr\'esente le nombre des suites
$(y_1,\ldots, y_q,y,z)$ avec~$q$ pair, $y_1$, \dots~,
$y_q$, $z$ dans~$M^*$, $y=y_1\cdots y_q$ et $x=yz$ ; c'est
aussi le nombre des d\'ecompositions $(y_1,\ldots, y_q,z)$ de
degr\'e impair de~$x$, d'o\`u
$(d_+\,\zeta)(x)=d_+(x)+d_-(x)=d(x)$. On \'etablit de mani\`ere
analogue les relations
$(\zeta\,d_+)(x)=(\zeta\,d_-)(x)=(d_-\,\zeta)(x)=d(x)$ pour
$x\in M^*$. On a donc prouv\'e les formules~(5) et l'on en
d\'eduit imm\'ediatement~(6) par diff\'erence.\cqfd

\th Lemme 2.3 {\rm (Formule d'inversion de
M\"obius)}|Soient~$f$ et~$g$ deux fonctions \`a valeurs
enti\`eres \footnote{$(^5)$}{\rm La m\^eme conclusion reste
valable pour des fonctions $f$ et $g$ sur~$M$ \`a valeurs dans
un groupe commutatif.} sur~$M$. Les relations suivantes sont
\'equivalentes :
$$
\leqalignno{\sum_{x_1x_2=x}g(x_2)&=f(x)\quad
{\sl pour\ tout}\ x\in M;&(8)\cr
\sum_{x_1x_2=x}\mu_M(x_1)f(x_2)&=g(x)\quad
{\sl pour\ tout}\ x\in M.&(9)\cr}
$$
\finth


La relation (8) s'\'ecrit $\zeta\,g=f$ et (9) s'\'ecrit $\mu_Mf=g$ ;
elles sont donc \'equivalentes puisque
$\zeta\mu_M=\mu_M\zeta=\epsilon$ et $\epsilon f=f$,
$\epsilon g=g$.\cqfd

\goodbreak
\sectiona 3. Fonction de M\"obius du mono\"\i de $L(Z;C)$|
Nous allons d'abord montrer que, dans le mono\"\i de $L(Z;C)$
d\'efini au chapitre~1.2, tout \'el\'ement n'a qu'un nombre fini de
d\'ecompositions ; nous utiliserons pour cela
l'homomorphisme~$\pi$ de $L(Z;C)$ dans $\Ab(Z)$.
Soient~$f$ dans $\Ab(Z)$ et $z_1$, \dots~, $z_p$ les
\'el\'ements~$z$ de~$Z$ tels que $f(z)\not=0$ ; on pose
$m_i=f(z_i)$ pour $1\le i\le p$ et $m=m_1+\cdots+m_p$.
Les \'el\'ements~$u$ de $L(Z;C)$ tels que $\pi(u)=f$ sont de la
forme $[t_1]\cdots [t_m]$ avec $t_1$, \dots~, $t_m$
dans~$Z$, la lettre~$z_i$ apparaissant~$m_i$ fois dans le
mot $t_1\cdots t_m$ pour $1\le i\le p$ ; par suite
$\pi^{-1}(f)$ est fini pour tout $f\in L(Z;C)$. Soient
alors~$u$ dans $L(Z;C)$ et $f=\pi(u)$ ; pour toute
d\'ecomposition $(u_1,\ldots, u_q)$ de~$u$ dans $L(Z;C)$, la
suite $(\pi(u_1),\ldots ,\pi(u_q))$ est une d\'ecomposition
de~$f$ dans $\Ab(Z)$ ; comme~$f$ n'a qu'un nombre fini de
d\'ecompositions dans $\Ab(Z)$ et que pour $f_1$,
\dots~,~$f_q$ donn\'ees, il n'y a qu'un nombre fini de solutions
du syst\`eme $\pi(u_1)=f_1$, \dots~, $\pi(u_q)=f_q$,
l'\'el\'ement~$u$ n'a qu'un nombre fini de d\'ecompositions dans
$L(Z;C)$.

\medskip
Dans toute la suite, nous notons $|F|$ le nombre d'\'el\'ements
d'un ensemble fini~$F$.

\th Th\'eor\`eme 2.4|La fonction de M\"obius du mono\"\i de $L(Z;C)$
est la fonction~$\mu$ donn\'ee par $\mu([F])=(-1)^{|F|}$ pour
toute partie commutative~$F$ de~$Z$ et $\mu(u)=0$ dans les
autres cas.
\finth

Soit $\mu$ la fonction sur $L(Z;C)$ d\'efinie dans l'\'enonc\'e et
soit~$\zeta$ la fonction constante \'egale \`a~1 sur $L(Z;C)$.
Soient~$u$ un \'el\'ement de $L(Z;C)$ et $(F_1,\ldots, F_r)$ sa
$V$-d\'ecomposition ; d'apr\`es les corollaires~1.3 et~1.4, les
couples $(F,v)$ o\`u la partie commutative~$F$ de~$Z$ et~$v$
dans $L(Z;C)$ satisfont \`a $[F]\cdot v=u$ sont les couples
$(F,[F_1\setminus F]\cdot [F_2]\cdots [F_r])$ avec $F\subset
F_1$. On a donc
$(\mu\zeta)(u)=\smash{\sum\limits_{F\subset
F_1}(-1)^{|F|}}$ ; si $u=1$, on a $F_1=\emptyset$ et la
somme pr\'ec\'edente vaut~1 ; sinon, notons~$n$ le cardinal
de~$F_1$, d'o\`u $(\mu\zeta)(u)=\sum\limits_{r=0}^n
(-1)^r{n\choose r}=(1-1)^n=0$. On a donc prouv\'e
$\mu\zeta=\epsilon$ ; si~$\mu'$ est la fonction de M\"obius
de $L(Z;C)$, on a alors
$\mu'=\epsilon\mu'=(\mu\zeta)\mu'=\mu(\zeta\mu')
=\mu\epsilon=\mu$.\cqfd

\sectiona 4. Cas particuliers|

(a) Lorsque $C$ est vide, le mono\"\i de $L(Z;C)$ se r\'eduit \`a
$\Mo(Z)$, les parties commmutatives ont un \'el\'ement et l'on a
$\mu(z)=-1$ pour tout lettre~$z$, puis $\mu(1)=1$ et
$\mu(w)=0$ pour tout mot de longueur sup\'erieure ou \'egale
\`a~2. Supposons en particulier que~$z$ soit un ensemble fini
\`a~$n$ \'el\'ements $T_1,\ldots,T_n$ ; l'application
$f\mapsto \sum\limits_{w\in \Mo(Z)} f(w)\cdot w$ est un
isomorphisme de l'anneau~$A$ d\'efini au n\omini~2 (pour
$M=\Mo(Z)$) sur l'anneau des s\'eries formelles non
commutatives \`a coefficients entiers en $T_1,\ldots,T_n$.
A la fonction~$\zeta$ correspond la s\'erie
$\sum\limits_ ww=\sum\limits_{r=0}^\infty
\sum\limits_{i_1,\ldots,i_r=1}^n T_{i_1}\cdots T_{i_r}$ ; \`a
la fonction~$\mu$ correspond la s\'erie
$1-\smash{\sum\limits_{i=1}^nT_i}$, d'o\`u l'identit\'e 
$\sum\limits_w w=(1-T_1-\cdots -T_n)^{-1}$.

\goodbreak
(b) Supposons maintenant que $C$ se compose de tous les
couples d'\'el\'ements distincts de~$Z$. L'application~$\pi$ est
un isomorphisme de $L(Z;C)$ sur $\Ab(Z)$, qui nous permettra
d'identifier ces deux mono\"\i des. Toute partie finie non
vide~$F$ de~$Z$ est commutative et $[F]$ est la fonction
\'egale \`a~1 sur~$F$ et \`a~0 sur $Z\setminus F$. Le
th\'eor\`eme~2.4 d\'etermine donc la fonction de M\"obius sur
$\Ab(Z)$ ; lorsque~$Z$ est l'ensemble des nombres premiers,
l'application $f\mapsto\prod\limits_{p\in Z} p^{f(p)}$ est
un isomorphisme de $\Ab(Z)$ sur le mono\"\i de multiplicatif des
entiers $n\ge 1$ et l'on retrouve les r\'esultats connus sur la
fonction de M\"obius proprement dite.

Particularisons encore en supposant que $Z$ a $n$ \'el\'ements
$T_1,\ldots, T_n$. L'anneau~$A$ d\'efini au n\omini~2 pour
$M=\Ab(Z)$ est isomorphe \`a l'anneau ${\bboard Z}[[T_1,\ldots,
T_n]]$ des s\'eries formelles commutatives \`a coefficients
entiers en $T_1,\ldots, T_n$, la fonction~$f$ correspondant \`a
la s\'erie 
$$\displaylines{\noalign{\vskip-8pt}
\sum_{\alpha_1,\ldots,\alpha_n\ge 0}
f(\alpha_1,\ldots,\alpha_n)T_1^{\alpha_1}\cdots
T_n^{\alpha_n}.\cr
\noalign{\hbox{La fonction~$\zeta$ correspond \`a}}
\sum_{\alpha_1,\ldots,\alpha_n\ge0}
T_1^{\alpha_1}\cdots T_n^{\alpha_n}\cr
\noalign{\vskip-5pt}
\noalign{\hbox{et~$\mu$ \`a}}
\noalign{\vskip-5pt}
\sum\limits_{F\subset\{1,\ldots,n\}}(-1)^{|F|}
\prod_{j\in F}T_j=\prod_{i=1}^n (1-T_i).\cr}
$$

Supposant toujours $Z$ fini, on peut appliquer la formule
d'inversion de M\"obius \`a deux fonctions~$f$ et~$g$ nulles
sur les \'el\'ements de $\Ab(Z)$ qui ne sont pas de la forme~$[F]$
avec $F\subset Z$. On retrouve le r\'esultat connu : si~$f$
et~$g$ sont deux fonctions d\'efinies sur l'ensemble des parties
d'un ensemble fini~$Z$, les relations $\sum\limits_{F'\subset
F}f(F')=g(F)$ et 
$\sum\limits_{F'\subset F}(-1)^{-|F'|}g(F\setminus F')=f(F)$
sont \'equivalentes ({\it principe d'inclusion et d'exclusion}).

\vfill\eject

\pagetitretrue

\auteurcourant={{\eightrm CHAPITRE III :
CIRCUITS DANS UN GRAPHE}}

\vglue 2cm
\centerline{{\eightrm CHAPITRE 3}}
\vskip 2mm
\centerline{{\bf CIRCUITS DANS UN GRAPHE}}

\vskip 6mm plus 2mm
\sectiona 1. D\'efinitions|
Un {\it graphe orient\'e} $G$ est un quadruplet
$(S,A,\sigma,\beta)$ o\`u~$S$ et~$A$ sont deux ensembles et
$\sigma$, $\beta$ deux applications de~$A$ dans~$S$. Les
\'el\'ements de~$S$ sont appel\'es les {\it sommets} et ceux de~$A$
les {\it ar\^etes} du graphe~$G$ ; si~$a$ est une ar\^ete, le
sommet $\sigma(a)$ est appel\'e sa {\it source} et le sommet
$\beta(a)$ son {\it but} ; on dit aussi que l'ar\^ete~$a$ joint le
sommet~$s$ au sommet~$t$ si l'on a $\sigma(a)=s$ et
$\beta(a)=t$.

Un {\it flot} dans $G$ est une famille $(f_{s,i})_
{s\in S,\,1\le i\le h(s)}$ ayant les propri\'et\'es suivantes :

\decale (a)|$h$ est une fonction sur~$S$ \`a valeurs enti\`eres
positives ;

\decale (b)|l'ensemble $\Phi$ des sommets $s$ tels que
$h(s)\not=0$ est fini ;

\decale (c)|pour tout $s\in \Phi$ et tout entier $i$ avec $1\le
i\le h(s)$, l'\'el\'ement $f_{s,i}$ est une ar\^ete de source~$s$.

\medskip
Soient $f=(f_{s,i})_{s\in S,\,1\le i\le h(s)}$ et
$f'=(f'_{s,i})_{s\in S,\,1\le i\le h'(s)}$ deux flots ; leur
produit~$ff'$ est le flot $f''=(f''_{s,i})_
{s\in S,\,1\le i\le h"(s)}$ d\'efini par
$$
\leqalignno{h''(s)&=h(s)+h'(s) ;&(1)\cr
f''_{s,i}&=\cases{f_{s,i}&pour $1\le i\le h(s)$ ;\cr
f'_{s,i-h(s)}&pour $h(s)+1\le i\le h(s)+h'(s)$.\cr}&(2)}
$$
L'ensemble des flots est un mono\"\i de, ayant pour unit\'e le flot
correspondant \`a $h=0$.

Soit $f=(f_{s,i})_
{s\in S,\,1\le i\le h(s)}$ un flot. L'entier $\sum\limits_{s\in
S}h(s)$ s'appelle la {\it longueur} du flot. De plus, la {\it
matrice d'incidence} $N(f)=(n_{s,t})_{s,t\in S}$ est d\'efinie
ainsi : si~$s$ et~$t$ sont deux sommets, l'entier $n_{s,t}$ est
le nombre d'entiers~$i$ tels que $1\le i\le h(s)$ et
$\beta(f_{s,i})=t$ (autrement dit, le nombre d'ar\^etes du flot
joignant~$s$ \`a~$t$). On a \'evidemment
$$\leqalignno{
\sum_{t\in S}n_{s,t}&=h(s);&(3)\cr
\noalign{\hbox{si l'on a aussi}}
\sum_{s\in S}n_{s,t}&=h(t)\quad\hbox{(pour tout $t\in
S$)},&(4)}
$$
on dit que $f$ est un {\it circuit}. La formule
$N(ff')=N(f)+N(f')$ montre que si~$f$ et~$f'$ sont des flots et
si deux des trois flots $f$, $f'$, $ff'$ sont des circuits, le
troisi\`eme est aussi un circuit. En particulier, les circuits
forment un sous-mono\"\i de du mono\"\i de des flots.

\rem Remarque $3.1$|Pour tout sommet $s$, soit $T_s$ le 
mono\"\i de libre construit sur l'ensemble des ar\^etes de
source~$s$. Soit le mono\"\i de produit $\prod\limits_{s\in
S}T_s$. Le mono\"\i de des flots est par d\'efinition le
sous-mono\"\i de de~$T$ form\'e des familles $(t_s)_{s\in S}$
telles que l'ensemble $\{s\mid t_s\not=1\}$ soit fini. Comme la
multiplication est simplifiable dans un mono\"\i de libre, elle
l'est dans le mono\"\i de des flots et {\it a fortiori} dans le
sous-mono\"\i de des circuits. Ce dernier cas est aussi une
cons\'equence du th\'eor\`eme~3.3 et du corollaire~1.3.

\sectiona 2. Structure des flots|
Soient $a$ une ar\^ete et $\overline s$ sa source ; le flot $b(a)$
est par d\'efinition le flot $(f_{s,i})_
{s\in S,\,1\le i\le h(s)}$ tel que $h(\overline s)=1$, $h(s)=0$
pour $s\not=\overline s$ et $f_{\overline s,i}=a$. Il est
imm\'ediat que $b(a)$ et $b(a')$ commutent si les ar\^etes~$a$
et~$a'$ ont des sources distinctes. De plus, un flot quelconque
$f=(f_{s,i})_{s\in S,\,1\le i\le h(s)}$ peut se mettre sous forme
de produit \footnote{$(^6)$}{Pour tout sommet~$s$, posons
$u(s)=\prod\limits_{i=1}^{h(s)} b(f_{s,i})$. Les flots $u(s)$
commutent deux \`a deux et il existe une partie {\it finie}~$S'$
de~$S$ telle que $u(s)=1$ pour tout $s\in S\setminus S'$. Le
produit $\prod\limits_{s\in S}u(s)$ est donc d\'efini sans
ambigu\"\i t\'e.}
$$
f=\prod_{s\in S}\; \prod_{i=1}^{h(s)} b(f_{s,i}).\leqno(5)
$$
On dit qu'un flot $f=(f_{s,i})_
{s\in S,\,1\le i\le h(s)}$ est {\it simple} si~$h$ ne prend que
les valeurs~0 et~1 ; il revient au m\^eme de dire que~$f$ est de
la forme $\prod\limits_{s\in \Phi}b(a_s)$ o\`u~$\Phi$ est un
ensemble fini de sommets et o\`u l'ar\^ete~$a_s$ est de source~$s$
pour tout $s\in \Phi$ ; l'ensemble~$\Phi$ s'appelle le
{\it support} du flot simple~$f$.

\th Lemme 3.2|Soit $f$ un flot. Il existe une suite
$(f_1,\ldots, f_m)$ de flots simples et une seule, telle que 
$f=f_1\cdots f_m$ et que le support de~$f_i$ contienne celui
de~$f_{i+1}$ pour $1\le i\le m-1$.
\finth

Repr\'esentons $f$ sous la forme (5) et notons $m$ le plus grand
des entiers $h(s)$. Pour $1\le i\le m$, soit $\Phi_i$ l'ensemble
des sommets~$s$ tels que $h(s)\ge i$ et soit~$f_i$ le flot
simple $\smash{\prod\limits_{s\in\Phi_i}b(f_{s,i})}$. Il est
imm\'ediat que $(f_1,\ldots, f_m)$ est la suite cherch\'ee.\cqfd

\proclaim Th\'eor\`eme 3.3. Le mono\"\i de des flots sur le
graphe~$G$ est engendr\'e par l'ensemble des flots $b(a)$
$($pour $a\in A)$, soumis aux relations de commutation
$b(a)\cdot b(a')=b(a')\cdot b(a)$ pour tous les couples
d'ar\^etes~$a$ et~$a'$ ayant des sources distinctes.

\goodbreak
Soit $C$ l'ensemble des couples d'ar\^etes $(a,a')$ telles que
$\sigma(a)\not=\sigma(a')$. Lorsque $(a,a')$ appartient \`a~$C$,
on a $b(a)\cdot b(a')=b(a')\cdot b(a)$, donc l'application~$b$
se prolonge en un homomorphisme~$b'$ de $L(A;C)$ dans le
mono\"\i de des flots. Avec les notations de~1.3, les parties
commutatives de~$A$ sont de la forme $F=\{a_s\mid s\in
\Phi\}$ o\`u~$\Phi$ est un ensemble fini de sommets et~$a_s$
une ar\^ete de source~$s$ pour tout $s\in\Phi$ ; de plus, on a 
$b'[F]=\prod_{s\in \Phi} b(a_s)$. Enfin, si~$F$ et~$F'$
sont deux parties commutatives de~$A$, la partie~$F$ est
conti\-gu\"e \`a~$F'$ si et seulement si le support de $b'[F]$
contient celui de~$b'[F']$. Par suite, l'homomorphisme~$b'$
transforme la $V$-d\'ecomposition d'un \'el\'ement~$u$ de $L(A;C)$
en la d\'ecomposition du lemme~3.2 du flot $b'(u)$. Le
th\'eor\`eme~1.2 sur les $V$-d\'ecompositions entra\^\i ne donc
que~$b'$ est bijectif.\cqfd


\sectiona 3. Structure des circuits|
Soient $\Phi$ un ensemble fini non vide de sommets, $u$ une
permutation de~$\Phi$ et pour tout $s\in \Phi$, soit~$a_s$
une ar\^ete joignant~$s$ \`a~$u(s)$ ; notons~{\bf a} la famille
$(a_s)_{s\in \Phi}$ ; on posera $c(\Phi,u,{\bf a})
=\prod_{s\in \Phi} b(a_s)$. Par abus de notation,
nous \'ecrirons parfois $c(\Phi,u,a_s)$ au lieu de 
$c(\Phi,u,{\bf a})$. Du fait que~$u$ est une permutation
de~$\Phi$, on obtient l\`a un {\it circuit} simple ; de plus,
tout circuit simple s'obtient ainsi d'une mani\`ere et d'une
seule. On dira que le circuit simple $c(\Phi,u,{\bf a})$ est
{\it contigu} au circuit simple $c(\Phi',u',{\bf a}')$ si, pour
tout sommet $s'\in \Phi'$, il existe un entier $m\ge 1$ avec
$u'^m(s')\in \Phi$.

\th Proposition 3.4|Soit $f$ un circuit. Il existe une suite
$(f_1,\ldots, f_m)$ de circuits simples et une seule, telle que 
$f=f_1\cdots f_m$ et que~$f_i$ soit contigu \`a~$f_{i+1}$
pour
$1\le i\le m-1$.
\finth

(A) {\it Existence de la d\'ecomposition :}

Nous raisonnerons par r\'ecurrence sur la longueur $\ell$
de~$f$, le cas $\ell=0$ \'etant trivial. Supposons donc $\ell
\ge 1$ et l'existence d'une d\'ecomposition prouv\'ee pour les
circuits de longueur inf\'erieure \`a~$\ell$.

Posons $f=(f_{s,i})_
{s\in S,\,1\le i\le h(s)}$ et notons~$\Sigma$ l'ensemble
des sommets~$s$ tels que $h(s)\not=0$. Si une
ar\^ete~$f_{s,i}$  joint~$s$ \`a~$t$, on a $n_{s,t}\ge 1$ ;
comme~$f$ est un circuit, on a $h(t)=\sum_{s'}n_{s',t}$
d'o\`u $h(t)\ge 1$ et finalement $t\in\Sigma$. Il existe
donc une application~$v$ de~$\Sigma$ dans lui-m\^eme
telle que l'ar\^ete~$f_{s,1}$ joigne~$s$ \`a~$v(s)$.

La suite des ensembles finis $\Sigma, v(\Sigma),
v^2(\Sigma), \ldots$ est d\'ecroissante ; il existe donc un
entier $m_0\ge 0$ et une partie non vide~$\Phi$
de~$\Sigma$ tels que $v^m(\Sigma)=\Phi$ pour $m\ge
m_0$. De plus,~$v$ induit une permutation~$u$
de~$\Phi$ et par suite $f_1=\prod_
{s\in \Phi}b(f_{s,1})$ est un circuit simple. Il existe un
circuit~$f'$ tel que $f=f_1f'$ et comme~$f'$ est de
longueur strictement inf\'erieure \`a~$\ell$, il existe par
l'hypoth\`ese de r\'ecurrence des circuits simples
$f_2,\ldots, f_m$ tels que $f'=f_2\cdots f_m$ et que~$f_i$
soit contigu \`a~$f_{i+1}$ pour $2\le i\le m-1$. Il reste donc
\`a prouver que~$f_1$ est contigu \`a~$f_2$.

Posons $f_2=c(\Phi',u',{\bf a}')$ ; comme
$f=f_1f_2\cdots f_m$, il est clair que l'on a
$a'_s=f_{s,1}$, d'o\`u $u'(s)=v(s)$ pour $s\in \Phi'\cap
\Phi^c$. \footnote{$(^7)$}{Si $U$ est une partie de $S$,
on note $U^c$ son compl\'ementaire dans~$S$.} Pour
tout~$s$ dans $\Phi'\cap \Phi^c$, il existe un entier
$m\ge 1$ tel que les sommets $s, v(s), \ldots,
v^{m-1}(s)$ appartiennent \`a $\Phi'\cap \Phi^c$ et que
$v^m(s)$ appartienne \`a~$\Phi$ : cela r\'esulte aussit\^ot
de la construction de~$\Phi$. On a alors
$v^{i+1}(s)=u'(v^i(s))$ pour $i\in \{0,1,\ldots, m-1\}$,
d'o\`u $u'^m(s)=v^m(s)\in \Phi$. On a donc prouv\'e
que~$f_1$ est contigu \`a~$f_2$.

\medskip
(B) {\it Unicit\'e de la d\'ecomposition} :

En raisonnant par r\'ecurrence sur la longueur de $f$, on
se ram\`ene \`a prouver l'assertion suivante : {\it soient
$g_1,\ldots, g_n$ des circuits simples tels que
$f=g_1\cdots g_n$ et que $g_j$ soit contigu
\`a~$g_{j+1}$ pour $1\le j\le n-1$. On a alors
$g_1=f_1$} (noter que la multiplication est simplifiable
dans le mono\"\i de des circuits d'apr\`es la remarque~3.1).

Sous les hypoth\`eses pr\'ec\'edentes, posons
$g_j=c(\Phi_j,u_j,a_{s,j})$ et
$\Psi_j=\Phi_j\cap(\Phi_1\cup\cdots\cup\Phi_{j-1})^c$
pour $1\le j\le n$. La relation $f=g_1\cdots g_n$
entra\^\i ne $\Sigma=\Phi_1\cup \cdots \cup \Phi_n
=\Psi_1\cup \cdots \cup \Psi_n$ et $f_{s,1}=a_{s,j}$,
d'o\`u $v(s)=u_j(s)$, pour $1\le j\le n$ et $s\in \Psi_j$.
Soit $s\in \Phi_j$ (avec $2\le j\le n$) ;
comme~$g_{j-1}$ est contigu \`a~$g_j$, il existe un
entier $m\ge 0$ tel que $(u_j)^m(s)\in \Phi_{j-1}$ ; si
l'on note~$\mu$ le plus petit des entiers positifs~$m$
tels que $(u_j)^m(s)$ appartienne \`a
$\Phi_1\cup\cdots\cup \Phi_{j-1}$, on a
$(u_j)^\mu(s)=v^\mu(s)$, d'o\`u $v^\mu(s)\in
\Phi_1\cup\cdots\cup\Phi_{j-1}$, on a
$(u_j)^\mu(s)=v^\mu(s)$, d'o\`u $v^\mu(s)\in 
\Phi_1\cup\cdots\cup\Phi_{j-1}$. Ce r\'esultat entra\^\i ne
que, pour tout $s\in \Sigma$, il existe un entier
$m(s)\ge 0$ avec $v^{m(s)}(s)\in \Phi_1$. Or, on a
$v(\Phi_1)=\Phi_1$ car~$v$ co\"\i ncide sur~$\Phi_1$
avec la permutation~$u_1$ de~$\Phi_1$ ; pour tout
entier $m\ge 0$, on a donc $\Phi_1=v^m(\Phi_1)\subset
v^m(\Sigma)$, d'o\`u $\Phi_1\subset
\Phi=\bigcap\limits_{m\ge 0}v^m(\Sigma)$. Par ailleurs
$\Sigma$ est fini et pour $m\ge \sup m(s)$, on a
$v^m(s)\in \Phi_1$ pour tout $s\in \Sigma$, d'o\`u $\Phi
\subset \Phi_1$.

On a donc prouv\'e $\Phi=\Phi_1$ ; comme on a aussi
$f_{s,1}=a_{s,1}$ pour tout $s\in \Phi_1$, on a
$g_1=f_1$.\cqfd

\sectiona 4. Cycles|
On dit qu'un flot est un {\it cycle} s'il existe des
sommets distincts $s_1$, \dots~, $s_m$ et des
ar\^etes $a_1$, \dots~, $a_m$ tels que
$z=b(a_1)\cdots b(a_m)$ et que~$a_1$ joigne~$s_1$
\`a~$s_2$, $a_2$ joigne~$s_2$ \`a~$s_3$, \dots~,
$a_{m-1}$ joigne~$s_{m-1}$ \`a~$s_m$ et~$a_m$
joigne~$s_m$ \`a~$s_1$. Lorsqu'il y a au plus une ar\^ete
de source et de but donn\'es, on pourra repr\'esenter sans
ambigu\"\i t\'e le cycle pr\'ec\'edent par la notation
$[s_1\cdots s_m]$ o\`u n'interviennent que les sommets
des cycles.

On notera $Z$ l'ensemble des cycles et $D$ l'ensemble
des couples de cycles n'ayant aucun sommet en commun ;
il est imm\'ediat que l'on a
$$
zz'=z'z\quad{\rm pour}\quad (z,z')\in D.\leqno(6)
$$
De plus, les cycles ne sont autres que les circuits simples
de la forme $c(\Phi,u,{\bf a})$ o\`u~$u$ est une
permutation circulaire de~$\Phi$. La d\'ecomposition
usuelle d'une permutation en cycles montre alors que
tout circuit simple s'\'ecrit de mani\`ere unique sous la
forme $[T]=\prod_{z\in T}z$, o\`u~$T$ est une partie
finie non vide de~$Z$ telle que $(z,z')\in D$ pour $z,z'$
distincts dans~$T$. Si $[T']$ est un autre circuit
simple, il est imm\'ediat que~$[T]$ est contigu \`a~$[T']$
si et seulement si, pour tout $z'\in T'$, il existe $z\in
T$ avec $ (z,z')\not\in D$.

D'apr\`es la relation (6), il existe un homomorphisme
$\varphi$ de $L(Z;D)$ dans le mono\"\i de des circuits qui
applique tout cycle sur lui-m\^eme. Les remarques
pr\'ec\'edentes montrent que~$\varphi$ transforme
la $V$-d\'ecomposition d'un \'el\'ement~$u$ de $L(Z;D)$ en
la d\'ecomposition du circuit $\varphi(u)$ d\'ecrite dans la
proposition~3.4. Le th\'eor\`eme~1.2 sur les
$V$-d\'ecompositions et la proposition~3.4 entra\^\i nent
alors le th\'eor\`eme suivant.

\th Th\'eor\`eme 3.5|Le mono\"\i de des circuits sur le
graphe~$G$ est engendr\'e par l'ensemble des cycles
soumis aux relations de commutation $zz'=z'z$ pour
tous les couples de cycles~$z$ et~$z'$ n'ayant aucun
sommet en commun.
\finth

\vskip 0pt minus 5pt
\rem Remarque $3.6$|Le th\'eor\`eme pr\'ec\'edent permet de
d\'eterminer facilement la fonction de M\"obius~$\mu$ du
mono\"\i de des circuits. En effet, utilisant le
th\'eor\`eme~2.4, on voit d'abord que l'on a $\mu(z_1\cdots
z_r)=(-1)^r$ si $z_1$, \dots~,~$z_r$ sont des cycles
n'ayant deux \`a deux aucun sommet en commun et que
l'on a $\mu(f)=0$ si le circuit~$f$ n'est pas de la
forme pr\'ec\'edente. Or la signature d'une permutation
circulaire portant sur~$n$ \'el\'ements est \'egale \`a
$(-1)^{n+1}$. Utilisant la d\'ecompositon d'un circuit
simple en cycles, on obtient le r\'esultat d\'efinitif suivant.

(a) {\it Si le circuit $f$ est simple, de la forme
$f=c(\Phi,u,{\bf a})$, on a\hfil\break
$\mu(f)=\epsilon\cdot (-1)^{|\Phi|}$ o\`u~$\epsilon$ est
la signature de la permutation~$u$.}

(b) {\it Si le circuit $f$ n'est pas simple, on a
$\mu(f)=0$.}

\sectiona 5. Relation avec les chemins|
Nous allons d'abord rappeler les d\'efinitions usuelles. A
tout sommet~$s$ on fait par convention correspondre un
chemin~$e_s$ de longueur~0 et l'on pose
$\sigma(e_s)=\beta(e_s)=s$. Pour tout entier $m\ge 1$,
un {\it chemin} de longueur~$m$ est une suite
$c=(a_1,\ldots,a_m)$ d'ar\^etes telles que
$\beta(a_i)=\sigma(a_{i+1})$ pour $1\le i\le m-1$ ;
il existe alors des sommets $s_0$, $s_1$, \dots~, $s_m$
tels que~$a_i$ joigne~$s_{i-1}$ \`a~$s_i$ pour $1\le
i\le m$ ; on dit que $s_0$, $s_1$, \dots~, $s_m$ sont
les sommets de~$c$ et que~$s_0$ est la source
$\sigma(c)$ et~$s_m$ le but~$\beta(c)$ de~$c$. On dit
aussi que~$c$ joint~$s_0$ \`a~$s_m$.

Le {\it produit des chemins} est d\'efini de la mani\`ere
suivante : soient $s$, $t$ et~$u$ des sommets, $c$ un
chemin joignant~$s$ \`a~$t$ et~$c'$ un chemin
joignant~$t$ \`a~$u$. Si~$c$ est de longueur~0, on pose
$cc'=c'$ ; si~$c'$ est de longueur~0, on pose $cc'=c$ ;
si $c=(a_1,\ldots, a_m)$ et $c'=(a'_1,\ldots, a'_n)$ sont
de longueur non nulle, la suite 
$(a_1,\ldots, a_m,a'_1,\ldots, a'_n)$ est un chemin
not\'e~$cc'$. Dans tous les cas, $cc'$ joint~$s$ \`a~$u$ et
sa longueur est la somme des longueurs de~$c$ et~$c'$.
Les chemins de longueur~1 sont des ar\^etes et un chemin
$c=(a_1,\ldots, a_m)$ n'est autre que le produit
$a_1\cdots a_m$.

Soit $s$ un sommet. Un {\it lacet} de source $s$ est un
chemin joignant~$s$ \`a~$s$. Pour la multiplication
pr\'ec\'edemment d\'efinie, les lacets de source~$s$ forment
un mono\"\i de, d'\'el\'ement unit\'e~$e_s$. Soit~$c$ un
lacet de source~$s$, de sommets $s_0,s_1,\ldots, s_m$
(avec $s_0=s_m=s$) ; on dit que~$c$ est {\it
irr\'eductible} si l'on a $m\ge 1$ et $s_i\not=s$ pour
$1\le i\le m-1$. Tout lacet de source~$s$ s'\'ecrit de
mani\`ere unique sous la forme $c_1\cdots c_p$,
o\`u~$c_1$, \dots~, $c_p$ sont des lacets irr\'eductibles :
il suffit pour le voir de couper un lacet aux endroits o\`u
il repasse en~$s$.

\goodbreak
A tout chemin $c=a_1\cdots a_m$, nous ferons
correspondre le flot $b(c)=b(a_1)\cdots b(a_m)$. On voit
imm\'ediatement que $b(c)$ est un circuit si~$c$ est un
lacet et que l'on a $b(cc')=b(c)\cdot b(c')$ lorsque
le produit des chemins~$c$ et~$c'$ est d\'efini. De plus
$b(e_t)$ est le flot nul pour tout sommet~$t$.

\th Proposition 3.7|Soit $f=(f_{s,i})_{s\in S,1\le i\le
h(s)}$ un flot et~$t$ un sommet. On note ${\cal C}_t$
l'ensemble des chemins~$c$ de source~$t$ pour lesquels
le flot $b(c)$ divise~$f$ \`a
gauche. \footnote{$(^8)$}{Nous disons que $f'$ divise
$f$ \`a gauche s'il existe $f'$ avec $f=f'f''$.} Il existe un
chemin $\gamma=\alpha_1\cdots \alpha_\mu$ et un seul
tel que ${\cal C}_t$ se compose des chemins
$\gamma_m=\alpha_1\cdots \alpha_m$ pour
$m\in\{0,1,\ldots, \mu\}$.
\finth

Notons $\ell$ la longueur de $f$. Pour tout chemin $c$,
le flot $b(c)$ a m\^eme longueur que~$c$ ; il en r\'esulte
que tout chemin~$c$ tel que $b(c)$ divise~$f$ \`a
gauche est de longueur au plus \'egale \`a~$\ell$. De plus, on
a $e_t\in {\cal C}_t$ donc ${\cal C}_t$ n'est pas vide.
Il existe donc dans ${\cal C}_t$ un chemin de longueur
maximale. Si $\gamma=\alpha_1\cdots \alpha_\mu$ est
un tel chemin, nous poserons $\gamma_m=\alpha_1\cdots
\alpha_m$ pour $m\in \{0,1,\ldots, \mu\}$. Il est clair
que chacun des chemins~$\gamma_0$, $\gamma_1$,
\dots~, $\gamma_\mu$ appartient \`a~${\cal C}_t$ et la
proposition~3.7 r\'esulte alors du lemme suivant.

\th Lemme 3.8|Pour tout entier $m\ge 0$ il existe au
plus un chemin de longueur~$m$ dans~${\cal C}_t$.
\finth

Soient $c$ un chemin de longueur~$m$, $a_1$, \dots~,
$a_m$ ses ar\^etes et $s_0$, $s_1$, \dots~,~$s_m$ ses
sommets. Pour tout sommet~$s$, on note $k(s)$ le
nombre de fois que~$s$ appara\^\i t dans la suite
$s_0,s_1,\ldots, s_{m-1}$ et l'on range sous forme d'une
suite strictement croissante $(u(s,1),\ldots,u(s,k(s))$ les
entiers~$i$ tels que $1\le i\le m$ et $s_{i-1}=s$.
Soit~$i$ un entier compris entre~0 et $m-1$ ; il
existe un entier~$k_i$ et un seul tel que $1\le k_i\le
k(s_i)$ et $u(s_i,k_i)=i+1$ et $k_i$ repr\'esente le
nombre de fois que le sommet~$s_i$ appara\^\i t dans la
suite $s_0,s_1,\ldots, s_i$. On a
$$
\leqalignno{f&=\prod_{s\in S}\;\prod_{i=1}^{h(s)}
b(f_{s,i})&(7)\cr
b(c)&=\prod_{s\in S}\;\prod_{j=1}^{k(s)}
b(a_{u(s,j)})&(8)\cr}
$$
et par suite, le flot $b(c)$ divise \`a gauche le flot $f$ si
et seulement si l'on a $k(s)\le h(s)$ et
$a_{u(s,j)}=f_{s,j}$ pour $j\in \{1,\ldots, k(s)\}$, quel
que soit le sommet~$s$. Ces conditions \'equivalent \`a
$$
\leqalignno{
a_{i+1}&=f_{s_i,k_i}\qquad\ {\rm pour}\ 0\le i\le m-1
&(9)\cr
\noalign{\hbox{et entra\^\i nent}}
s_{i+1}&=\beta(f_{s_i,k_i})
\quad{\rm pour}\ 0\le i\le m-1.&(10)\cr}
$$

\goodbreak\noindent
Comme on a $s_0=t$ et $k_0=1$ et que $k_i$ ne
d\'epend que des sommets $s_0$, $s_1$, \dots~, $s_i$,
les formules r\'ecurrentes~(9) et~(10) montrent qu'il
existe au plus un chemin~$c$ de longueur~$m$
dans~${\cal C}_t$.\cqfd

\th Propositon 3.9|On conserve les notations de $3.7$ et
l'on suppose que~$f$ est un circuit et que $h(t)$ est non
nul. Le chemin~$\gamma$ est alors un lacet et il existe
dans ${\cal C}_t$ un lacet irr\'eductible et un seul.
\finth

Pour montrer que $\gamma$ est un lacet, nous
raisonnerons par l'absurde en montrant que, si un
chemin~$c$ de longueur~$m$ appartient \`a
${\cal C}_t$ et n'est pas un lacet, il existe dans
${\cal C}_t$ un chemin de longueur $m+1$.

Soient donc $a_1$, \dots~, $a_m$ les ar\^etes et $s_0$,
$s_1$, \dots~, $s_m$ les sommets de~$c$. Pour tout
sommet $s\not=s_m$, notons~$k(s)$ le nombre de fois
que~$s$ appara\^\i t dans la suite $s_0$,
$s_1$, \dots~, $s_{m-1}$ et posons
$u(s)=\prod\limits_{i=1}^{k(s)}b(f_{s,i})$. Par ailleurs,
notons~$k$ le nombre de fois que~$s_m$ appara\^\i t dans
la suite $s_0$,
$s_1$, \dots~, $s_{m-1}$ et rangeons sous forme d'une
suite strictement croissante $i_1$, \dots~, $i_k$ les
entiers~$i$ tels que $1\le i\le m-1$ et $s_i=s_m$. On
a alors
$$
b(c)=\prod_{s\not =s_m}u(s)\cdot
\prod_{r=1}^kb(f_{s_m,r})\leqno(11)
$$(le second terme dispara\^\i t si $k=0$ et l'on a
$s_0\not=s_m$).

Par ailleurs, notons $(n'_{s,s'})$ la matrice d'incidence
de~$b(c)$ et $(n_{s,s'})$ celle de~$f$. Comme~$b(c)$
divise~$f$, on a $n'_{s,s'}\le n_{s,s'}$ et comme~$f$
est un circuit, on a $\sum_{s\in S}n_{s,s'}=h(s')$. Or les
ar\^etes
$a_{i_1}$, $a_{i_2}$, \dots~, $a_{i_k}$, $a_m$ ont
pour but le sommet~$s_m$, d'o\`u $k+1\le \sum_{s\in
S}n'_{s,s_m}\le \sum_{s\in S}n_{s,s_m}=h(s_m)$. L'ar\^ete
$a_{m+1}=f_{s_m,k+1}$ est donc d\'efinie et la
formule~(11) prouve que le flot $b(c\cdot a_{m+1})=b(c)\cdot
b(a_{m+1})$ divise \`a gauche~$f$. Par cons\'equent, le
chemin $a_1\cdots a_ma_{m+1}$ de longueur $m+1$
appartient \`a~${\cal C}_t$.

On a donc prouv\'e que $\gamma$ est un lacet. Comme on
a $h(t)\ge 1$, l'ar\^ete~$f_{t,1}$ appartient \`a~${\cal
C}_t$, d'o\`u $\mu\ge 1$. Le lacet~$\gamma$ se
d\'ecompose de mani\`ere unique en un produit de lacets
irr\'eductibles $c_1\cdots c_p$ (avec $p\ge 1$). Soit~$c$
un lacet irr\'eductible de source~$t$. Pour que~$c$
appartienne \`a~${\cal C}_t$, il faut et il suffit qu'il
eixste un lacet~$c'$ de source~$t$ avec
$cc'=\gamma=c_1\cdots c_p$, ce qui \'equivaut \`a
$c=c_1$.\cqfd

\sectiona 6. D\'ecomposition descendante d'un circuit|{\it
On suppose dans ce n\omini\ que l'ensemble~$S$ des
sommets du graphe~$G$ est totalement ordonn\'e.} On
appelle {\it d\'ecomposition descendante} d'un circuit~$f$
toute suite $(c_1,\ldots, c_p)$ de lacets irr\'eductibles
qui poss\`ede les propri\'et\'es suivantes :

(a) on a $f=b(c_1)\cdots b(c_p)$ ;

(b) on a $\sigma(c_1)\ge \cdots \ge \sigma(c_p)$ ;

(c) pour $i\in \{1,\ldots, p\}$, la source $\sigma(c_i)$
est le plus grand sommet du lacet~$c_i$.

\noindent
Posons $f=(f_{s,i})_{s\in S,\,1\le i\le h(s)}$ ; la formule
$f=b(c_1)\cdots b(c_p)$ montre que l'on a $h(s)\not=0$
si et seulement si~$s$ est un sommet de l'un des lacets
$c_1$, \dots~, $c_p$ ; il r\'esulte alors de~(b) et~(c) que
l'on a $s\le \sigma(c_1)$ pour tout sommet~$s$ tel que
$h(s)\not=0$.

\th Proposition 3.10|Tout circuit $f$ poss\`ede une
d\'ecomposition descendante et une seule.
\finth

Nous noterons $\ell$ la longueur de $f$ et nous
supposerons $\ell\not=0$, le cas $\ell=0$ \'etant trivial.
Nous noterons~$N$ l'ensemble des sommets~$s$ tels que
$h(s)\not=0$ ; il est fini, donc poss\`ede un plus grand
\'el\'ements~$s_1$.

\medskip
(A) {\it Unicit\'e de la d\'ecomposition descendante :}

Raisonnant par r\'ecurrence sur $\ell$, il suffit d'\'etablir
l'assertion suivante : {\it si $(c_1,\ldots, c_p)$ et 
$(c'_1,\ldots, c'_{p'})$ sont des d\'ecompositions
descendantes de~$f$, on a $c_1=c'_1$.} Sous l'hypoth\`ese
faite, les lacets irr\'eductibles~$c_1$ et~$c'_1$ sont tels
que $b(c_1)$ et $b(c'_1)$ divisent \`a gauche~$f$ ; la
remarque pr\'ec\'edant la proposition~3.10 montre
que~$c_1$ et~$c'_1$ ont tous deux pour source le
sommet~$s_1$ ; on a donc $c_1=c'_1$ d'apr\`es la
proposition~3.9.

\medskip
(B) {\it Existence de la d\'ecomposition descendante :}

Comme on a $h(s_1)\not=0$, il existe un lacet
irr\'eductible~$c_1$ de source~$s_1$ et un circuit~$f'$
tels que $f=b(c_1)\cdot f'$. Comme~$f'$ est de longueur
strictement inf\'erieure \`a~$\ell$, on peut admettre par
hypoth\`ese de r\'ecurrence que~$f'$ poss\`ede une
d\'ecomposition descendante $(c_2,\ldots, c_p)$. On a
$f'=b(c_2)\cdots b(c_p)$, d'o\`u
$f=b(c_1)b(c_2)\cdots b(c_p)$. Les sommets de~$c_1$
appartenant \`a~$N$, la source $s_1=\sigma(c_1)$
de~$c_1$ est le plus grand des sommets de~$c_1$ ;
comme $\sigma(c_2)\in N$, on a $\sigma(c_1)=s_1\ge
\sigma(c_2)$ et par suite 
$(c_1,c_2,\ldots, c_p)$ est une d\'ecomposition
descendante de~$f$.\cqfd

\rem Exemple $3.11$|Nous consid\'erons le graphe~$G$ de
sommets $1,2,3,4,5,6$ avec l'ordre naturel sur les
sommets et dont les ar\^etes sont figur\'ees sur le dessin
ci-apr\`es ; on consid\`ere sur~$G$ le flot~$f$ repr\'esent\'e
aussi sur le m\^eme dessin. La d\'ecomposition descendante
de~$f$ est \'egale \`a $(c_1,\ldots, c_7)$ avec le tableau
suivant donnant les ar\^etes et les sommets de ces lacets
et le code de la figure.



\vfill\eject
$$\HanFig{ProbComb_fig.1}$$
\vfill\eject
\pagetitretrue

\auteurcourant={{\eightrm 
CHAPITRE IV : R\'EARRANGEMENTS DE SUITES}}

\vglue 2cm
\centerline{{\eightrm CHAPITRE IV}}
\vskip 2mm
\centerline{{\bf R\'EARRANGEMENTS DE SUITES}}

\vskip 6mm plus 2mm
{\it Dans tout ce chapitre, on note $X$ un ensemble ; \`a
partir du n\omini~3, on suppose que~$X$ est totalement
ordonn\'e. Dans les exemples, $X$ est l'ensemble des
entiers, avec l'ordre naturel.}

\sectiona 1. Mono\"\i de des r\'earrangements|
Les constructions de ce n\omini\ s'obtiennent en
appliquant les constructions g\'en\'erales du chapitre~III
au graphe $G=(S,A,\sigma,\beta)$ associ\'e de la mani\`ere
suivante \`a~$X$ : on a $S=X$, $A=X\times X$,
$\sigma(x,y)=x$ et $\beta(x,y)=y$ pour $x,y$
dans~$X$. De mani\`ere plus imag\'ee, $X$ est l'ensemble
des sommets du graphe~$G$ ; quels que soient les
sommets~$x$ et~$y$, il existe une ar\^ete unique
$a_{x,y}$ joignant~$x$ \`a~$y$.

\titrecourant={{\eightrm 1. MONO\"IDE DES
R\'EARRANGEMENTS}} 
Un {\it flot} est une application~$f$ de~$X$ dans
$\Mo(X)$ telle que l'ensemble $\{x\in X\mid
f(x)\not=1\}$ soit fini. Le produit de deux flots~$f$
et~$f'$ est d\'efini par $(ff')(x)=f(x)\cdot f'(x)$ pour
tout~$x$ dans~$X$. L'ensemble des flots, avec cette
multiplication, est un mono\"\i de not\'e $F(X)$. Si~$f$
est un flot et $x,y$ des \'el\'ements de~$X$, on note
$\theta_x(f)$ la longueur du mot~$f(x)$ et $n_{x,y}(f)$
le nombre de fois que la lettre~$y$ intervient dans le
mot~$f(x)$. On a alors les relations
$$
\leqalignno{\theta_x(f)&=\sum_{y\in X}n_{x,y}(f)&(1)\cr
\theta_x(ff')&=\theta_x(f)+\theta_x(f')&(2)\cr
n_{x,y}(ff')&=n_{x,y}(f)+n_{x,y}(f'),&(3)\cr}
$$
o\`u $f$ et $f'$ sont deux flots et $x,y$ deux \'el\'ements
de~$X$. Pour tout flot~$f$, l'application $x\mapsto
\theta_x(f)$ est un \'el\'ement de $\Ab(X)$ et $\theta$ est
un homomorphisme de $F(X)$ dans $\Ab(X)$.

Les circuits, que nous pr\'ef\'erons appeler ici {\it
r\'earrangements}, sont les flots~$f$ satisfaisant \`a la
relation
$$\leqalignno{
\kern2.8cm\theta_y(f)&=\sum_{x\in X} n_{x,y}(f)\quad
\hbox{(pour tout }y\in X);&(4)\cr
\noalign{\hbox{cette relation \'equivaut \`a la suivante}}
\theta(f)&=\sum_{x\in X}\epsilon(f(x)).&(5)\cr}
$$
Les r\'earrangements forment un sous-mono\"\i de $Q(X)$
de $F(X)$ ; on l'appelle {\it mono\"\i de des
r\'errangements}.

\goodbreak
Soient $w=x_1\cdots x_m$ et $w'=x'_1\cdots x'_{m}$
deux mots de m\^eme longueur ; on note $w\choose w'$ le
flot $\prod\limits_{i=1}^m b(a_{x'_i,x_i})$ o\`u $b(a)$
est le flot associ\'e \`a une ar\^ete~$a$. C'est un flot~$f$
ainsi d\'efini : pour tout $x\in X$, soient $i_1$, \dots~,
$i_p$ les entiers~$i$ tels que $1\le i\le m$ et
$x'_i=x$, rang\'es par ordre croissant ; on a alors
$f(x)=x_{i_1}\cdots x_{i_p}$. Cette d\'efinition entra\^\i ne
les propri\'et\'es suivantes :

\medskip
(a) Tout flot est de la forme $w\choose w'$ et l'on a
${w_1\choose w'_1}{w_2\choose w'_2}={w_1w_2\choose
w'_1w'_2}$.

(b) On a ${x_1\cdots x_m\choose x'_1\cdots x'_m}
={y_1\cdots y_n\choose y'_1\cdots y'_n}$ si et
seulement si l'on a $m=n$ et s'il existe une permutation
de $\{1,2,\ldots, m\}$ telle que $y_i=x_{\sigma(i)}$,
$y'_i=x'_{\sigma(i)}$ et tel que $i<j$, $x'_i=x'_j$
entra\^\i nent $\sigma(i)<\sigma(j)$.

(c) Soit $f={x_1\cdots x_m\choose x'_1\cdots x'_m}$ ;
pour $x,y$ dans~$X$, l'entier $n_{x,y}(f)$ est le nombre
des entiers~$i$ tels que $1\le i\le m$ et $x'_i=x$,
$x_i=y$. D'apr\`es~(1), $\theta_x(f)$ est donc le nombre
de fois que la lettre~$x$ intervient dans le mot
$x'_1\cdots x'_m$ ; autrement dit, on a la relation
$$
\theta\textstyle{w\choose w'}=\epsilon(w').\leqno(6)
$$

(d) Le mono\"\i de des flots $F(X)$ est engendr\'e par les
\'el\'ements $x\choose x'$ (pour $x,x'$ dans~$X$) soumis
aux relations de commutation ${x\choose x'}{y\choose
y'}={y\choose y'}{x\choose x'}$ pour $x'\not=y'$ (voir le
th\'eor\`eme 3.3).

(e) Le flot $w\choose w'$ est un r\'earrangement si et
seulement si le mot~$w'$ est un r\'earrangement du
mot~$w$ (ce qui justifie la terminologie adopt\'ee).

\medskip
Soient $\Omega$ un mono\"\i de commutatif, not\'e
additivement et~$c$ une application de $X\times X$
dans~$\Omega$. Pour tout flot~$f$, l'ensemble des
couples $(x,y)$ tels que $n_{x,y}(f)\not=0$ est fini ; on
peut donc poser
$$\leqalignno{
n_c(f)&=\sum_{x,y}n_{x,y}(f)\cdot c(x,y).&(7)\cr
\noalign{\hbox{Il\thinspace est\thinspace
imm\'ediat\thinspace que
$n_c$ est\thinspace un\thinspace homomorphisme
\thinspace de
$F(X)$ dans~$\Omega$ ;\thinspace de plus,\thinspace
on\thinspace a\hfill}}
n_c\textstyle{x_1\cdots x_m\choose x'_1\cdots x'_m}
&=\displaystyle\sum_{i=1}^m c(x'_i,x_i).&(8)\cr}
$$

\sectiona 2. D\'ecomposition d'un r\'earrangement en cycles|
La donn\'ee d'un circuit simple $f$ \'equivaut \`a celle d'une
partie finie~$F$ de~$X$ et d'une
permutation~$\sigma$ de~$F$ ; on a
$f=\prod\limits_{x\in F}b(a_{x,\sigma(x)})$.
Si~$x_1$, \dots~, $x_m$ sont les \'el\'ements de~$F$, on
peut encore \'ecrire
$f={\sigma(x_1)\cdots \sigma(x_m)
\choose \kern6pt x_1\kern4pt \cdots \kern 6pt x_m}$ et
la notation des r\'earrangements est donc en accord avec
la notation usuelle des permutations.

Pour tout mot $w=x_1\cdots x_m$, on pose
$$
\gamma\, w=x_2x_3\cdots x_mx_1 ;\leqno(9)
$$
les cycles sont alors les r\'earrangements de la forme
$[w]={\gamma\,w\choose w}$ o\`u~$w$ est un mot form\'e
de lettres distinctes et l'on a $[w]=[w']$ si et seulement
s'il existe un entier positif~$i$ avec $w'=\gamma^iw$.

\goodbreak
En traduisant le th\'eor\`eme 3.5, on obtient le r\'esultat
suivant qui g\'en\'eralise la d\'ecomposition bien connue
d'une permutation en produit de cycles.

\tha Proposition 4.1.|
\decale{\rm (a)}|Tout r\'earrangement est produit d'une
suite finie de cycles.

\decale{\rm (b)}|\'Etant donn\'ees deux d\'ecompositions d'un
m\^eme r\'earrangement en produit de suites finies de
cycles, on passe de la premi\`ere \`a la seconde par une
suite finie de transformations \'el\'ementaires consistant \`a
permuter dans un produit deux cycles cons\'ecutifs qui
n'ont aucune lettre en commun.
\fintha

La d\'emonstration de la proposition 3.4 fournit un
algorithme effectif pour la d\'ecomposition en cycles d'un
r\'earrangement $f={w\choose w'}$. On pose $f_1=f$ et
l'on forme une suite de lettres $y_1$, \dots~, $y_q$ de
la mani\`ere suivante :

(a) $y_1$ est la premi\`ere lettre de $w'$ ;

(b) lorsque $y_i$ est d\'ej\`a d\'efinie, on choisit pour
$y_{i+1}$ la lettre la plus \`a gauche de~$w$ parmi
celles qui se trouvent au-dessus d'une lettre de~$w'$
\'egale \`a~$y_i$ ; on entoure la colonne correspondante ;

(c) on arr\^ete la proc\'edure la premi\`ere fois qu'on obtient
une lettre~$y_q$ \'egale \`a l'une des lettres pr\'ec\'edentes,
par exemple $y_q=y_p$ avec $1\le p<q$. 

On pose alors $z_1=[y_py_{p+1}\cdots y_{q-1}]$ et l'on
supprime dans~$f_1$ les colonnes entour\'ees dont la
lettre inf\'erieure est $y_p$, $y_{p+1}$, \dots~,
ou~$y_{q-1}$. On obtient ainsi un
r\'earrangement~$f_2$ tel que $f_1=z_1f_2$ et l'on
recommence avec~$f_2$ la proc\'edure pr\'ec\'edente.

\rem Exemple $4.2$|On part du r\'earrangement
$f=\petitematrice{3&5&4&2&4&1&2&2&1&3\cr
1&1&2&2&2&3&3&4&4&5\cr}$. On a, en indiquant dans la
deuxi\`eme colonne la suite
$y_1\cdots \overline{y_p\cdots y_q}$

\medskip
\halign{\vrule height 18pt width 0pt$#$\hfil\quad
&$\longrightarrow\quad #$\hfil&\quad$#$\hfil\cr
f_1=\left(\petitematrice{\overline3\cr
\underline{\vrule depth 3.5pt width 0pt1}\cr}\right.
\kern-3pt\matrice{5&4&2&4\cr
1&2&2&2\cr}\petitematrice{\overline 1\cr 
\underline{\vrule depth 3.5pt width 0pt3}\cr}\kern-3pt
\left.\matrice{2&2&1&3\cr
3&4&4&5\cr}\right)&\overline {\vrule height 8pt width
0pt 1\ 3\ 1}&z_1=[1\ 3]\cr
f_2=\left(\petitematrice{\overline5\cr
\underline{\vrule depth 3.5pt width 0pt1}\cr}\right.
\petitematrice{\overline4\cr
\underline{\vrule depth 3.5pt width 0pt2}\cr}
\kern-3pt\matrice{2&4\cr
2&2\cr}\petitematrice{\overline 2\cr 
\underline{\vrule depth 3.5pt width 0pt3}\cr}
\petitematrice{\overline 2\cr 
\underline{\vrule depth 3.5pt width 0pt4}\cr}
\kern-3pt
\left.\matrice{1\cr
4\cr}
\petitematrice{\overline 3\cr 
\underline{\vrule depth 3.5pt width 0pt5}\cr}
\right)&1\ 5\ 3\ \overline {\vrule height 8pt width
0pt 2\ 4\ 2}&z_2=[2\ 4]\cr
f_3=\left(\petitematrice{\overline5\cr
\underline{\vrule depth 3.5pt width 0pt1}\cr}\right.
\petitematrice{\overline2\cr
\underline{\vrule depth 3.5pt width 0pt2}\cr}
\kern-3pt\matrice{4\cr
2\cr}\petitematrice{\overline 2\cr 
\underline{\vrule depth 3.5pt width 0pt3}\cr}
\kern-3pt
\left.\matrice{1\cr
4\cr}
\petitematrice{\overline 3\cr 
\underline{\vrule depth 3.5pt width 0pt5}\cr}
\right)&1\ 5\ 3\ \overline {\vrule height 8pt width
0pt 2\ 2}&z_3=[2]\cr
f_4=\left(\petitematrice{\overline5\cr
\underline{\vrule depth 3.5pt width 0pt1}\cr}
\petitematrice{\overline4\cr
\underline{\vrule depth 3.5pt width 0pt2}\cr}
\petitematrice{\overline2\cr
\underline{\vrule depth 3.5pt width 0pt3}\cr}
\petitematrice{\overline1\cr
\underline{\vrule depth 3.5pt width 0pt4}\cr}
\petitematrice{\overline3\cr
\underline{\vrule depth 3.5pt width 0pt5}\cr}
\right)&\overline {\vrule height 8pt width
0pt 1\ 5\ 3\ 2\ 4\ 1}&z_4=[1\ 5\ 3\ 2\ 4],\cr
}

\medskip
\noindent
d'o\`u la d\'ecomposition en cycles
$$f=[1\ 3]\cdot [2\ 4]\cdot [2]\cdot [1\ 5\ 3\ 2\ 4].$$

\def\intercal{\mathrel{\tau}}
\sectiona 3. Mono\"\i de d'intercalement|

\titrecourant={{\eightrm 3. MONO\"IDE D'INTERCALEMENT}}
On rappelle que l'ensemble $X$ est d\'esormais suppos\'e
totalement ordonn\'e. On dit qu'un mot $x_1\cdots x_m$
est {\it croissant} si l'on a $x_1\le x_2\le \cdots \le
x_m$. Soit~$w$ un mot ; parmi les r\'earrangements
de~$x$, il en est un seul qui soit croissant et qu'on
notera~$\overline w$. De mani\`ere plus explicite, soient
$s_1$, \dots~, $s_p$ les lettres intervenant dans~$w$,
rang\'ees par ordre croissant et soit $\alpha(i)$ la
multiplicit\'e de~$s_i$ dans~$w$ ; on a alors $\overline
w=\prod\limits_{i=1}^p s_i^{\alpha(i)}$. On posera
aussi $\Gamma(w)={w\choose \overline w}$ ; comme le
mot~$w$ est de longueur $\alpha(1)+\cdots+\alpha(p)$,
on peut le d\'ecomposer de mani\`ere unique sous la forme
$w=w_1\cdots w_p$ o\`u le mot~$w_i$ est de
longueur~$\alpha(i)$ ; dans ces conditions, le flot
$h=\Gamma(w)$ est d\'efini par $h(s_i)=w_i$ pour $1\le
i\le p$ et $h(x)=1$ pour $x\not\in \{s_1,\ldots,s_p\}$.

Par ailleurs, pour tout r\'earrangement $f$, on pose
$\Pi(f)=\prod_{x\in X} f(x)$ ; ce produit se calcule
ainsi : si~$F$ est une partie finie de~$X$ telle que
$f(x)=1$ pour $x\in X\setminus F$, rang\'ee sous forme
d'une suite croissante $x_1,\ldots,x_q$, on a
$\Pi(f)=f(x_1)\cdots f(x_q)$.

On a donc d\'efini deux applications
$$
\Gamma : \Mo(X)\rightarrow Q(X)\quad
{\rm et}\quad
\Pi:Q(X)\rightarrow \Mo(X).
$$

\th Proposition 4.3|Les applications $\Gamma$ et $\Pi$
sont des bijections r\'eci\-proques.
\finth

Les remarques pr\'ec\'edentes montrent que l'on a
$\Pi(\Gamma(w))=w$ pour tout mot~$w$. Montrons par
ailleurs qu'on a $\Gamma(\Pi(f))=f$ pour tout
r\'earran\-gement~$f$. Rangeons sous forme d'une suite
croissante $x_1,\ldots, x_q$ l'ensemble des $x\in X$ tels
que $f(x)\not=1$ et notons $\alpha(i)$ la longueur du
mot $w_i=f(x_i)$ ; enfin posons $w=w_1\cdots w_q$ et
$w'=x_1^{\alpha(1)}\cdots x_q^{\alpha(q)}$. Il est
imm\'ediat que l'on a $w=\Pi(f)$ et $f={w\choose w'}$ ;
comme~$f$ est un r\'earrangement, le mot croissant~$w'$
est un r\'earrangement du mot~$w$, d'o\`u $w'=\overline
w$ et $f={w\choose \overline w}=\Gamma(\Pi(f))$.\cqfd

\medskip
Comme $\Gamma$ et $\Pi$ sont des bijections
r\'eciproques, la formule $w\intercal
w'=\Pi(\Gamma(w)\cdot \Gamma(w'))$ d\'efinit un nouveau
produit dans $\Mo(X)$, distinct en g\'en\'eral du produit de
juxtaposition et appel\'e produit d'intercalement. Pour ce
produit, l'ensemble des mots est un nouveau mono\"\i de,
qu'on appellera {\it mono\"\i de d'intercalement} et
qu'on notera $Q'(X)$. Par construction, $\Pi$ est un
isomorphisme de mono\"\i de de $Q(X)$ sur $Q'(X)$
et~$\Gamma$ est l'isomorphisme r\'eciproque.

\th Proposition 4.4|Soient $w$ et $w'$ deux mots,
$s_1$, \dots~, $s_p$ les lettres intervenant dans~$w$
ou~$w'$ rang\'ees par ordre croissant, $\alpha(i)$
$($resp. $\alpha'(i))$ la multiplicit\'e de~$s_i$ dans~$w$
$($resp.~$w')$. D\'ecomposons~$w$ en $w_1\cdots w_p$
et~$w'$ en $w'_1\cdots w'_p$ de sorte que~$w_i$ soit
de longueur~$\alpha(i)$ et~$w'_i$ de
longueur~$\alpha'(i)$ pour $1\le i\le p$. On a alors
$w\intercal w'=w_1w'_1w_2w'_2\cdots w_pw'_p$.
\finth

Le r\'earrangement croissant de $w$ est
$s_1^{\alpha(1)}\cdots s_p^{\alpha(p)}$ et celui
de~$w'$ est $s_1^{\alpha'(1)}\cdots s_p^{\alpha'(p)}$.
Le mot $f=\Gamma(w)$ est donc d\'efini par $f(s_i)=w_i$
pour $1\le i\le p$ et $f(x)=1$ pour
$x\not\in\{s_1,\ldots,s_p\}$ ; de m\^eme, $f'=\Gamma(w')$
est d\'efini par $f'(s_i)=w'_i$ pour $1\le i\le p$ et
$f'(x)=1$ lorsque $x\not\in\{s_1,\ldots,s_p\}$. On a alors
$
w\intercal w'=\Pi(ff')=\prod\limits_{i=1}^p (ff')(s_i)
=\prod\limits_{i=1}^p w_iw'_i.\qed
$

\goodbreak
\rem Exemple $4.5$|Pour $w=1\;3\;5\;2\;1\;4\;3\;1\;2\;
1\;1\;3$ et $w'=1\;2\;3\;5\;4\;3\;2\;1\;1\;1$ on a les
valeurs suivantes de $\alpha(i)$ et $\alpha'(i)$ :
$$
\vbox{\offinterlineskip\halign{\vrule\quad
\hfil$#$\quad\vrule &\vrule height 10pt depth 5pt width
0pt\quad\hfil$#$
\hfil\quad\vrule\cr
\noalign{\hrule}
i&1\;2\;3\;4\;5\cr
\alpha(i)&5\;2\;3\;1\;1\cr
\alpha'(i)&4\;2\;2\;1\;1\cr
\noalign{\hrule}
}}$$
d'o\`u les partages 
$$\displaylines{\noalign{\vskip-5pt}
w=1\;3\;5\;2\;1\mid 4\;3\mid 1\;2\;1\mid 
1\mid 3\quad{\rm et}\quad w'=1\;2\;3\;5\mid 4\;3\mid 
2\;1\mid 1\mid 1\cr
\noalign{\hbox{et le produit d'intercalement}}
w\intercal w'= 1\;3\;5\;2\;1\;1\;2\;3\;5\mid
4\;3\;4\;3\mid 1\;2\;1\;2\;1\mid 1\;1\mid 3\;1.\cr}
$$

\rem Exemple $4.6$|Soit \`a calculer le produit
$w=w_1\intercal w_2\intercal w_3$ avec
$w_1=1\;3\;5\;1\;2\;4$, \quad
$w_2=1\;1\;1\;2$, \quad
$w_3=5\;4\;3\;2\;1$, ce qui donne les
r\'ear\-ran\-gements croissants
$\overline w_1=1\;1\;2\;3\;4\;5$, \quad
$\overline w_2=1\;1\;1\;2$, \quad
$\overline w_3=1\,2\;3\;4\;5$. On a alors
$$\displaylines{
\Gamma(w)=\Gamma(w_1)\Gamma(w_2)\Gamma(w_3)
=\petitematrice{1&3&5&1&2&4&1&1&1&2&5&4&3&2&1\cr
1&1&2&3&4&5&1&1&1&2&1&2&3&4&5\cr}\cr
\noalign{\hbox{et apr\`es permutation des colonnes, on a}}
\Gamma(w)=
\petitematrice{1&3&1&1&1&5&5&2&4&1&3&2&2&4&1\cr
1&1&1&1&1&1&2&2&2&3&3&4&4&5&5\cr}\cr}
$$
et finalement\quad
$w=1\;3\;1\;1\;1\;5\;5\;2\;4\;1\;3\;2\;2\;4\;1$.

\medskip
La bijection $\Gamma$ permet de transporter \`a $Q'(X)$
certaines fonctions d\'efinies sur $Q(X)$ au n\omini~1.
Tout d'abord, on a
$$
\theta(\Gamma(w))=\epsilon(w)\quad\hbox{pour tout mot }
w;\leqno(10)
$$
en effet, on a $\theta(\Gamma(w))=\theta{w\choose
\overline w}$ d'apr\`es (6) et comme~$\overline w$ est un
r\'earrangement de~$w$, on a $\epsilon(\overline
w)=\epsilon(w)$. On pose par ailleurs
$$
\nu_{x,y}(w)=n_{x,y}(\Gamma(w))\leqno(11)
$$
pour tout mot $w=x_1\cdots x_m$ ; si $\overline w=
\overline x_1\cdots \overline x_m$ est le r\'earrangement
croissant de~$w$, l'entier $\nu_{x,y}(w)$ est le nombre
d'entiers~$i$ tels que $1\le i\le m$ et $\overline
x_i=x$, $x_i=y$. Enfin, si~$c$ est une application de
$X\times X$ dans un mono\"\i de
commutatif~$\Omega$, on pose
$\nu_c(w)=n_c(\Gamma(w))$ pour tout mot~$w$ ; avec
les notations pr\'ec\'edentes, on a
$$
\nu_c(w)=\sum_{i=1}^m c(\overline x_i,x_i)
\leqno(12)
$$
d'apr\`es la formule (8).

\rem Remarque $4.7$|On pourrait d\'efinir directement le
produit d'interca\-lement $w\intercal w'$ de deux mots
par la proposition~4.4 ; il n'est pas difficile de montrer
directement que ce produit est associatif et admet pour
\'el\'ement neutre le mot~1. C'est la voie suivie dans~[1]
(voir page~103).

\sectiona 4. D\'ecomposition descendante d'un mot|
Soit $w=x_1\cdots x_m$ un mot. On appelle {\it lettre
finale} de~$w$ l'\'el\'ement $Fw=x_m$ de~$X$ ; on dit
que~$w$ est {\it domin\'e} si l'on a $w\not=1$ et
$x_i<x_m$ pour $1\le i<m$ et l'on dit que l'indice
$i\in \{1,2,\ldots,m\}$ est {\it saillant} si l'on a
$x_i\ge x_j$ pour $i\le j\le m$. On appelle {\it
d\'ecomposition descendante} de~$w$ toute suite
$(w_1,w_2,\ldots, w_p)$ de mots domin\'es telle que
$w=w_1w_2\cdots w_p$ et $Fw_1\ge Fw_2\ge \cdots\ge
Fw_p$.

\titrecourant={\eightrm 4. D\'ECOMPOSITION
DESCENDANTE D'UN MOT}
\th Proposition 4.8|Tout mot admet une d\'ecomposition
descendante et une seule.
\finth

Si $w$ est un mot et si $n_1$, \dots~, $n_p$ sont des
entiers positifs dont la somme est \'egale \`a la longueur
de~$w$, il existe une d\'ecomposition $w=w_1\cdots
w_p$ de~$w$ et une seule telle que~$w_i$ soit de
longueur~$n_i$ pour $1\le i\le p$. Comme le dernier
indice d'un mot est saillant, il suffit de prouver le
lemme suivant.

\th Lemme 4.9|Soient $w=x_1\cdots x_m$, $w_1$,
\dots~, $w_p$ des mots de longueur non nulle tels que
$w=w_1\cdots w_p$ ; on note~$\ell_k$ la longueur
de~$w_k$ et l'on pose $j_k=\sum\limits_{r=1}^k \ell_r$
pour $1\le k\le p$. Pour que $(w_1,\ldots, w_p)$ soit
une d\'ecomposition descendante de~$w$, il faut et il
suffit que les indices saillants de~$w$ soient $j_1$,
\dots~, $j_p$.
\finth

Supposons d'abord que $(w_1,\ldots, w_p)$ soit une
d\'ecomposition descendante de~$w$. Comme~$w_1$ est
domin\'e, aucun indice~$i$ tel que $1\le i<j_1$ ne peut
\^etre saillant ; de plus, il est imm\'ediat que l'indice
$j_p=m$ est saillant. Soient alors~$k$ et~$i$ des
entiers tels que $1\le k<p$ et $j_k<i\le m$ ; il existe
un entier~$k'$ tel que $k\le k'<p$ et $j_{k'}<i\le
j_{k'+1}$ ; comme le mot $w_{k'+1}$ est domin\'e, on a
$x_i\le x_{j_k'+1}=Fw_{k'+1}\le Fw_k=x_{j_k}$ ; ceci
prouve que~$j_k$ est saillant. En particulier, si l'on a
$j_{k'}<i<j_{k'+1}$, alors $x_i<x_{j_{k'+1}}$ et
l'indice~$i$ n'est donc pas saillant. On a prouv\'e que les
indices saillants sont $j_1$, \dots~, $j_p$.

Supposons r\'eciproquement que les indices saillants
de~$w$ soient $j_1$, \dots~, $j_p$. Pour tout
entier~$k$ tel que $1\le k<p$, on a $j_k<j_{k+1}$ et
comme~$j_k$ est saillant, on a $Fw_k=x_{j_k}\ge
x_{j_{k+1}}=Fw_{k+1}$. Montrons que chacun des
mots~$w_k$ est domin\'e. Puisque l'indice $i'=j_k-1$
n'est pas saillant lorsque $j_k-j_{k-1}>1$, on a dans ce
cas $x_{i'}<x_{j_k}$. Il nous suffit donc de montrer que
l'hypoth\`ese $j_{k-1}<i<j_k$ et $x_{i'}<x_{j_k}$ pour
 $i<i'<j_k$ entra\^\i ne $x_i<x_{j_k}$. Or comme~$j_k$
est saillant, on a $x_{j_k}\ge x_r$ pour $j_k\le r\le m$
et comme~$i$ n'est pas saillant, il existe~$s$ avec
$i<s\le m$ et $x_i<x_s$ ; dans les deux cas $i<s<j_k$ et
$j_k\le s\le m$, on a $x_s\le x_{j_k}$, d'o\`u
$x_i<x_{j_k}$. (On a pos\'e $j_0=0$.)\cqfd

\medskip
Soit $w=x_1\cdots x_m$ un mot. Nous noterons
$\Delta(w)$ le flot $\gamma w_1\,\cdots \,\gamma
w_p\choose w_1\,\cdots\, w_p$ o\`u
$(w_1,\ldots,w_p)$ est la d\'ecomposition descendante
de~$w$ ; comme $\gamma w_j$ est un r\'earrangement
de~$w_j$, on voit que $\Delta(w)$ est un r\'earrangement.
Par ailleurs, \'etant donn\'es~$x$ et~$y$ dans~$X$, nous
noterons $\xi_{x,y}(w)$ le nombre d'entiers~$i$ tels que
$1\le i\le m-1$, $x_i=x$ et $x_{i+1}=y$. Enfin,
si~$c$ est une application de $X\times X$ dans un
mono\"\i de commutatif~$\Omega$, nous poserons
$\xi_c(w)=0$ si~$m$ est \'egal \`a~0 ou~1 et
$$
\xi_c(w)=c(x_1,x_2)+c(x_2,x_3)+\cdots +c(x_{m-1},x_m)
\leqno(13)
$$
si $m\ge 2$.

\goodbreak
\th Proposition 4.10|L'application $\Delta$ est une
bijection de $\Mo(X)$ sur~$Q(X)$. De plus, pour tout
mot~$w$, on a les relations
$$\theta(\Delta(w))=\epsilon(w),\qquad
n_{x,y}(\Delta(w))=\xi_{x,y}(w)$$ si $x<y$ et
$n_c(\Delta(w))=\xi_c(w)$ si l'applicatioon~$c$ de
$X\times X$ dans~$\Omega$ est telle que $c(x,y)=0$
pour $x\ge y$.
\finth

(a) Pour tout mot domin\'e $w=x_1\cdots x_m$, notons
$c(w)$ le lacet de sommets $x_mx_1x_2\cdots x_m$
dans le graphe~$G$ associ\'e \`a~$X$. Il est imm\'ediat que le
circuit
$b(c(w))$ (voir chapitre~III.5) est \'egal \`a $\gamma w\choose
w$ et que l'application
$w\mapsto c(w)$ induit une bijection de l'ensemble des
mots domin\'es sur l'ensemble des lacets irr\'eductibles dont
la source est le plus grand sommet. Avec ces notations,
on a $\Delta(w)=b(c(w_1))\cdots b(c(w_p))$ si
$(w_1,\ldots, w_p)$ est la d\'ecomposition
descendante de~$w$ ; comme la source du lacet $c(w_j)$
est la derni\`ere lettre de~$Fw_j$ de~$w_j$ et que l'on a
$Fw_1\ge \cdots \ge Fw_p$, l'application~$\Delta$
de~$\Mo(X)$ dans~$Q(X)$ transforme la d\'ecomposition
descendante d'un mot en la d\'ecompositin descendante du
circuit correspondant. La proposition~3.10 montre alors
que~$\Delta$ est bijective.

(b) Soit $w=x_1\cdots x_m$ un mot ; on note
$(w_1,\ldots, w_p)$ la d\'ecomposition descendante
de~$w$ et $j_1$, \dots~, $j_p$ les indices saillants
de~$w$ ; enfin, on note $x'=x'_1\cdots x'_m$ le
r\'earrangement $\gamma w_1\cdots \gamma w_p$
de~$w$. L'orsque l'indice $i\in \{1,2,\ldots,m\}$ est
distinct de $j_1$, \dots~, $j_p$, on a $x'_i=x_{i+1}$ ;
par ailleurs, pour $k\in \{1,2,\ldots, p\}$, on a
$$
x'_{j_k}=x_{j_{k-1}+1}\le x_{j_k}
$$
car le mot $w_k$ est domin\'e (on fait la convention
$j_0=0$) ; si de plus, on a $k\not=p$, on a
$x_{j_k+1}\le x_{j_k}$ car l'indice~$j_k$ est saillant.
Soient alors~$x$,~$y$ dans~$X$ avec $x<y$ ; les
remarques pr\'ec\'edentes montrent que l'on a $x_i=x$,
$x'_i=y$ si et seulement si l'on a $x_i=x$, $x_{i+1}
=y$ (et ceci ne peut avoir lieu pour $i$ dans
$\{j_1,\ldots, j_p\}$). Comme on a $\Delta(w)={w'\choose
w}$, la propri\'et\'e~(c) du n\omini~1 montre que l'on a 
$n_{x,y}(\Delta(w))=\xi_{x,y}(w)$ lorsque $x<y$.

(c) Enfin, soit $c$ une application de $X\times X$ dans
un mono\"\i de commutatif~$\Omega$ telle que
$c(x,y)=0$ lorsque $x\ge y$. On a alors
$n_c(f)=\sum_{x<y}n_{x,y}(f)\cdot c(x,y)$ pour tout
r\'earrangement~$f$ et $\xi_c(w)=\sum_{x<y}\xi_{x,y}(w)\cdot
c(x,y)$ pour tout mot~$w$. Le r\'esultat de l'alin\'ea~(b)
entra\^\i ne alors $n_c(\Delta(w))=\xi_c(w)$ pour tout mot~$w$.
La formule
$\theta(\Delta(w))=\epsilon(w)$ r\'esulte de~(6).\cqfd

\sectiona 5. Une m\'ethode de r\'earrangement|
Dans les num\'eros pr\'ec\'edents, nous avons d\'ecrit deux
bijections
$$
\Gamma:\Mo\rightarrow Q(X),\qquad
\Delta:\Mo(X)\rightarrow Q(x);
$$
par composition, on en d\'eduit une permutation
$\Phi=\Gamma^{-1}\circ \Delta$ de
l'ensemble $\Mo(X)$ des mots. On peut l'expliciter ainsi
: soit $w=x_1\cdots x_m$ un mot ; notons $s_1$,
\dots~, $s_q$ les lettres intervenant dans~$w$, rang\'ees
par ordre croissant, $\alpha(i)$ la multiplicit\'e
de~$s_i$ dans~$w$ et
$\beta(i)=\alpha(1)+\cdots+\alpha(i)$ (avec la
convention $\beta(0)=0$). Notons $\overline w=\overline
x_1\cdots \overline x_m$ le r\'earrangement croissant
$s_1^{\alpha(1)}\cdots s_q^{\alpha(q)}$ de~$w$
et~$\sigma$ la permutation de l'ensemble
$\{1,2,\ldots,m\}$ qui satisfasse \`a $\overline
x_i=x_{\sigma(i)}$ pour $1\le i\le m$ et qui soit
croissante sur chacun des intervalles
$[\beta(j-1)+1,\beta(j)]$ pour $1\le j\le q$. Par
ailleurs, soit $(w_1,\ldots,w_q)$ la d\'ecomposition
descendante de~$w$ ; on pose
$\gamma w_1\,\cdots\,\gamma w_p=y_1\cdots y_m$ ;
on a alors $\Phi(w)=y_{\sigma(1)}\cdots y_{\sigma(m)}$.

\titrecourant={\eightrm 5. UNE M\'ETHODE DE
R\'EARRANGEMENT}

\th Th\'eor\`eme 4.11|Soient $w=x_1\cdots x_m$ un mot,
$\overline w=\overline x_1\cdots \overline x_m$ son
r\'earrangement croissant et $x'=x'_1\cdots x'_m$ le mot
$\Phi(w)$. Alors

{\rm (a)} Le mot $w'$ est un r\'earrangement de~$w$.

{\rm (b)} Si $x$ et $y$ sont deux \'el\'ements de~$X$ tels
que $x<y$, le nombre $\nu_{x,y}(w')$ des entiers~$i$
tels que $1\le i\le m$ et $\overline x_i=x$, $x'_i=y$
est \'egal au nombre $\xi_{x,y}(w)$ des entiers~$i$ tels
que $1\le i<m$ et $x_i=x$, $x_{i+1}=y$.

{\rm (c)} Soit $c$ une application de $X\times X$ dans
un mono\"\i de commutatif~$\Omega$, telle que
$c(x,y)=0$ pour $x\ge y$. On a
$$
\sum_{i=1}^{m-1}c(\overline x_i,x'_i)
=\sum_{i=1}^{m-1} c(x_i,x_{i+1}).\leqno(14)
$$
\finth

On a $\Delta(w)=\Gamma(w')$. D'apr\`es les formules (10)
et (11) et la proposition~4.10, on a
$\epsilon(w)=\theta(\Delta(w))
=\theta(\Gamma(w'))=\epsilon(w')$ et
$\xi_{x,y}(w)=n_{x,y}(\Delta(w))=n_{x,y}(\Gamma(w'))
=\nu_{x,y}(w')$ pour $x<y$. Ceci prouve (a) et (b). On a
aussi
$$
\sum_{i=1}^mc(\overline x_i,x'_i)
=\nu_c(w')=n_c(\Gamma(w'))
=n_c(\Delta(w))
=\xi_c(w)=\sum_{i=1}^{m-1}c(x_i,x_{i+1})
$$
d'apr\`es les formules (12) et (13) et la proposition 4.10 ;
comme on a $\overline x_m\ge x'_m$, on a aussi
$c(\overline x_m,x'_m)=0$, d'o\`u imm\'ediatement la
formule (14).\cqfd

\medskip
Soient $x=x_1\cdots x_m$ un mot et $\overline
w=\overline x_1\cdots \overline x_m$ son r\'earrangement
croissant. On note $\nu(w)$ le nombre des entiers~$i$
tels que $1\le i\le m$ et $\overline x_i<x_i$ et
$\xi(w)$ le nombre des entiers~$i$ tels que $1\le i\le
m-1$ et $x_i<x_{i+1}$. On a
$$
\nu(w)=\sum_{x<y}\nu_{x,y}(w),\qquad
\xi(w)=\sum_{x<y}\xi_{x,y}(w)
$$
et le th\'eor\`eme 4.11 entra\^\i ne $\xi(w)=\nu(\Phi(w))$. On
en d\'eduit le r\'esultat suivant, d\^u \`a MacMahon [3,
page~186].

\goodbreak
\th Corollaire 4.12|Soient $w$ un mot et $r$ un entier
positif. Parmi les r\'earrangements~$w'$ de~$w$, il y en
a autant pour lesquels on a $\nu(w')=r$ que pour
lesquels on a $\xi(w')=r$.
\finth

\rem Exemple $4.13$|Pour d\'eterminer les indices
saillants d'un mot $w=x_1\cdots x_m$, le plus simple
est de d\'eterminer le mot $\widehat w=y_1\cdots y_m$
d\'efini par $y_i=\max\{x_i,x_{i+1}, \ldots,x_m\}$ ; un
indice~$i$ est saillant si et seulement si l'on a
$x_i=y_i$. Consid\'erons par exemple le mot
$$
\leqalignno{
w&=\overline{4\ \underline 6}\ \underline 6\ 5\ 4\ 4\ 3\ 
\overline{1\ 2\ \underline 6}\ 2\ 2\ \overline{1\ 3\
\underline 4}\ \underline 3\ 2\ \overline{1\ 2\ \underline
3}
\ 1\ \overline{1\ \underline 2}\cr
\widehat w&=6\ 6\ 6\ 6\ 6\ 6\ 6\ 6\ 6\ 6\ 4\ 4\ 4\ 4\ 
4\ 3\ 3\ 3\ 3\ 3\ 2\ 2\ 2,&\hbox{d'o\`u}\cr
}
$$
ce qui permet de d\'eterminer les indices saillants
(soulign\'es). La d\'ecomposi\-tion descendante s'obtient en
coupant~$w$ apr\`es chaque indice saillant, soit
$$
\leqalignno{
w&=4\ 6\mid 6\mid 5\ 4\ 4\ 3\ 
1\ 2\ 6\mid 2\ 2\ 1\ 3\
4\mid 3\mid 2\ 1\ 2\ 3\mid
\ 1\ 1\ 2\;;\cr
\noalign{\hbox{on en d\'eduit}}
\Delta(w)&=\left(\matrice{6&4\cr
4&6\cr}\right|\matrice{6\cr 6\cr}
\left|\matrice {4&4&3&1&2&6&5\cr
5&4&4&3&1&2&6\cr}\right|
\matrice{2&1&3&4&2\cr
2&2&1&3&4\cr}
\left|\matrice{3\cr 3\cr}\right|
\matrice{1&2&3&2\cr
2&1&2&3\cr}
\left|\matrice{1&2&1\cr
1&1&2\cr}\right),\cr
\noalign{\hbox{d'o\`u apr\`es permutation des colonnes}}
\Delta(w)&=
\left(\matrice{2&3&2&1&2&6&2&1&1&3&1&1&4&3&2&6&4
&3&2&4&4&6&5\cr
1&1&1&1&1&2&2&2&2&2&2&3&3&3&3&4&4&4&4&5&6&6&6\cr}
\right)\cr
\noalign{\hbox{et finalement}}
\matrice{w'=\Phi(w)={}\cr
\qquad\qquad \overline w={}\cr}
&\kern-5pt\petitematrice{\overline2\cr 
\underline{\vrule depth4pt width 0pt1}\cr}\kern-4pt
\petitematrice{\overline3\cr 
\underline{\vrule depth4pt width 0pt1}\cr}\kern-4pt
\petitematrice{\overline2\cr 
\underline{\vrule depth4pt width 0pt1}\cr}\kern-4pt
\matrice{1\cr 1\cr}\kern-4pt
\petitematrice{\overline2\cr 
\underline{\vrule depth4pt width 0pt1}\cr}\kern-4pt
\petitematrice{\overline6\cr 
\underline{\vrule depth4pt width 0pt2}\cr}\kern-4pt
\matrice{2&1&1\cr 2&2&1\cr}\kern-4pt
\petitematrice{\overline3\cr 
\underline{\vrule depth4pt width 0pt2}\cr}\kern-4pt
\matrice{1&1\cr 2&3\cr}\kern-4pt
\petitematrice{\overline4\cr 
\underline{\vrule depth4pt width 0pt3}\cr}\kern-4pt
\matrice{3&2\cr 3&3\cr}\kern-4pt
\petitematrice{\overline6\cr 
\underline{\vrule depth4pt width 0pt4}\cr}\kern-4pt
\matrice{4&3&2&4&4&6&5\cr
4&4&4&5&6&6&\,6.\cr}
\cr
}$$
On a entour\'e les paires montantes $(\overline x_i,x'_i)$
avec $\overline x_i<x'_i$ et coch\'e sur~$w$ les paires
montantes $(x_i,x_{i+1})$ avec $x_i<x_{i+1}$.

Enfin, voici les matrices
$$\displaylines{
N(w')=(\nu_{x,y}(w'))_{x,y\in X}\quad
{\rm et}\quad \Xi(w)=(\xi_{x,y}(w))_{x,y\in X}:\cr
\noalign{\medskip}
N(w')=\left(\matrice{
1&3&1&0&0&0\cr
3&1&1&0&0&1\cr
1&1&1&1&0&0\cr
0&1&1&1&0&1\cr
0&0&0&1&0&0\cr
0&0&0&1&1&1\cr}\right)
\qquad\kern8pt
\Xi(w)=\left(\matrice{
1&3&1&0&0&0\cr
2&1&1&0&0&1\cr
2&1&0&1&0&0\cr
0&0&2&1&0&1\cr
0&0&0&1&0&0\cr
0&1&0&0&1&1\cr}\right)
\cr}
$$
dont les parties au-dessus de la diagonale principale
co\"\i ncident. On a $$\nu(w')=\xi(w)=8.$$

\vfill\eject
\pagetitretrue

\auteurcourant={{\eightrm 
CHAPITRE V : SUR LE ``MASTER THEOREM" DE
MACMAHON}}

\vglue 2cm
\centerline{{\eightrm CHAPITRE V}}
\vskip 2mm
\centerline{{\bf SUR LE ``MASTER THEOREM" DE
MACMAHON}}

\vskip 6mm plus 2mm
\sectiona 1. Une g\'en\'eralisation non commutative du
``Master Theorem"|
On note $A$ un anneau avec \'el\'ement unit\'e, non
n\'ecessairement commutatif. Bien que l'anneau~$A$ ne
soit pas commutatif, on peut d\'efinir le d\'eterminant
d'une matrice carr\'ee $T=(t_{i,j})_{1\le i,j\le n}$ \`a
coefficients dans~$A$ par la formule usuelle
$$
\det T=\sum_{\sigma\in {\goth S}_n}
\varepsilon_\sigma\prod_{i=1}^n t_{i,\sigma(i)}.
\leqno(1)
$$
On rappelle que ${\goth S}_n$ est l'ensemble des
permutations de l'ensemble $\{1,\!2,\!\ldots,\!n\}$ et
$\varepsilon_\sigma$ est la signature de la
permutation~$\sigma$. Par ailleurs, on note~$I_n$ la
matrice unit\'e d'ordre~$n$ et $A_n$ l'anneau des s\'eries
formelles \`a coefficidents dans~$A$ en des ind\'etermin\'ees
commutatives $X_1$, \dots~, $X_n$. Le th\'eor\`eme
suivant se r\'eduit au \og Master Theorem\fg\ lorsque
l'anneau~$A$ est suppos\'e commutatif.

\th Th\'eor\`eme 5.1|Soit $\bf X$ la matrice diagonale
d'\'el\'ements $X_1,\ldots,X_n$ et soit $B=(b_{ij})$ une
matrice carr\'ee d'ordre~$n$ \`a coefficients dans~$A$. On
suppose que $b_{ij}$ commute \`a~$b_{i'j'}$ lorsque~$i$
et~$i'$ sont distincts. On pose
$Y_i=\vrule height 11pt width
0pt \smash{\sum\limits_{j=1}^n} b_{ij}X_j$ pour
$i\in
\{1,2,\ldots,n\}$.

Quels que soient les entiers positifs $\alpha(1)$, \dots~,
$\alpha(n)$, le coefficient
$t_{\alpha(1),\ldots,\alpha(n)}$ du mon\^ome
$X_1^{\alpha(1)}\cdots X_n^{\alpha(n)}$ dans le produit
$Y_1^{\alpha(1)}\cdots Y_n^{\alpha(n)}$ est \'egal au
coefficient du m\^eme mon\^ome dans la s\'erie formelle
$\det(I_n-B\cdot {\bf X})^{-1}$.
\finth

Nous noterons $Q$ le mono\"\i de des r\'earrangements
construit sur l'ensemble $\{1,2,\ldots, n\}$ (voir~IV.1)
et~$\mu$ la fonction de M\"obius de~$Q$. Vu
l'hypoth\`ese de commutativit\'e faite sur les \'el\'ements de la
matrice~$B$, il existe un homomorphisme~$u$ de~$Q$
dans le mono\"\i de multiplicatif~$\Omega$ de
l'anneau~$A_n$, tel que
$$
u{\textstyle{j_1\cdots j_p\choose i_1\cdots i_p}}=
\prod_{i=1}^p b_{i_kj_k}X_{j_k}.\leqno(2)
$$

(A) {\it Calcul de la s\'erie}\qquad
$t=\kern-10pt\displaystyle\sum_{\alpha(1),\ldots,\alpha(n)}
\kern-10pt
t_{\alpha(1),\ldots,\alpha(n)}\,X_1^{\alpha(1)}\cdots
X_n^{\alpha(n)}$ :

Soient $\alpha(1)$, \dots~, $\alpha(n)$ des entiers
positifs. Pour $i\in \{1,2,\ldots,n\}$, on a
$$
Y_i^{\alpha(i)}=\kern-10pt
\sum_{j_1,\ldots,j_{\alpha(i)}}\kern-7pt
b_{ij_1}\cdots b_{ij_{\alpha(i)}}\,
X_{j_1}\cdots X_{j_{\alpha(i)}};\leqno(3)
$$

\goodbreak
\noindent
posons $p=\alpha(1)+\cdots+\alpha(n)$ et notons $i_1$,
\dots~, $i_p$ la suite croissante o\`u~1 appara\^\i t
$\alpha(1)$ fois, 2 appara\^\i t $\alpha(2)$ fois, \dots~, et
o\`u~$n$ appara\^\i t $\alpha(n)$ fois. Multipliant les
\'egalit\'es~(3) membre \`a membre, on obtient
$$
Y_1^{\alpha(1)}\cdots Y_n^{\alpha(n)}
=\sum_{j_1,\ldots, j_n}b_{i_1j_1}\cdots b_{i_pj_p}\,
X_{j_1}\cdots X_{j_p},\leqno(3)
$$
o\`u les entiers $j_1$, \dots~, $j_p$ prennent
ind\'ependamment les valeurs $1,2,\ldots,n$. On obtient le
produit
$t_{\alpha(1),\ldots,\alpha(n)}
X_1^{\alpha(1)}\cdots X_n^{\alpha(n)}$ 
en ne conservant dans la somme pr\'ec\'edente que les
termes pour lesquels chacun des entiers $i\in
\{1,2,\ldots, n\}$ appara\^\i t $\alpha(i)$ fois dans la suite 
$j_1,\ldots,j_p$.

On a donc
$$
t_{\alpha(1),\ldots,\alpha(n)}
X_1^{\alpha(1)}\cdots X_n^{\alpha(n)}=
\sum u\textstyle{j_1\,\ldots\,j_p\choose
i_1\,\ldots\,i_p}\leqno(4)
$$
o\`u la sommation est \'etendue \`a tous les syst\`emes
$i_1,\ldots,i_p,j_1,\ldots,j_p$ satisfaisant aux deux
conditions suivantes :

(a) la suite $i_1,\ldots,i_p$ est croissante ;

(b) chacun des entiers $i\in \{1,\ldots,n\}$ appara\^\i t
$\alpha(i)$ fois dans chacune des suites
$i_1,\ldots,i_p$ et $j_1,\ldots,j_p$. 

Si l'on somme sur les suites
$(\alpha(1),\ldots,\alpha(n))$ de~$n$ entiers positifs,
on obtient une fois et une seule tout \'el\'ement de~$Q$, d'o\`u
$$
t=\sum_{f\in Q}u(f).\leqno(5)
$$

(B) {\it Calcul de la s\'erie}\quad
$d=\det(I_n-B\cdot {\bf X})$ :

Soit $U=(u_{ij})$ une matrice carr\'ee d'ordre~$n$ ; pour
toute partie~$H$ de l'ensemble $\{1,2,\ldots,n\}$,
soit~$D_H$ le d\'eterminant de la matrice obtenue en
supprimant de~$U$ les lignes et les colonnes dont les
indices n'appartiennent pas \`a~$H$ ; on a alors
$$
\det(I_n-U)=\sum_{r=0}^n (-1)^r
\sum_{|H|=r} D_H.\leqno(6)
$$

Cette formule est bien connue lorsque les \'el\'ements
de~$U$ commutent deux \`a deux et la d\'emonstration
usuelle s'\'etend imm\'ediatement au cas g\'en\'eral. Appliquons
ceci au cas de la matrice $U=B\cdot {\bf X}$ d'\'el\'ements
$u_{ij}=b_{ij}X_j$ ; pour toute partie~$H$ avec
$|H|=r$, on a
$$
D_H=\sum_{\sigma \in {\goth S}_r} \varepsilon_\sigma
\prod_{i\in H} u_{i,\sigma(i)}
=\sum_{\sigma\in {\goth S}_r}
\varepsilon_\sigma\, u(
\prod_{i\in H}{\sigma(i)\choose i}).\leqno(7)
$$

Lorsque $\sigma$ parcourt le groupe sym\'etrique 
${\goth S}_r$, l'\'el\'ement $\prod\limits_{i\in
H}{\sigma(i)\choose i}$ parcourt l'ensemble des circuits
simples de support~$H$ ; d'apr\`es la remarque~3.6,
$\mu(f)$ est \'egal \`a $(-1)^r\cdot \varepsilon_\sigma$
lorsque~$f$ est de la forme pr\'ec\'edente et l'on a
$\mu(f)=0$ si le circuit~$f$ n'est pas simple. De~(6)
et~(7), on d\'eduit facilement
$$
d=\sum_{f\in Q}\mu(f)\cdot u(f).\leqno(8)
$$

\goodbreak
(C) {\it Fin de la d\'emonstration }:

Rappelons qu'on a $u(f')\cdot u(f'')=u(f'f'')$ pour $f',f''$
dans~$Q$. Des formules (5) et (8), on d\'eduit alors
$$
d\,t=\sum_{f',f''} \mu(f')\cdot u(f')u(f'')
=\sum_f u(f)\sum_{f'f''=f}\mu(f').
$$
Par d\'efinition de la fonction de M\"obius~$\mu$
de~$Q$, on a par ailleurs
$$
\sum_{f'f''=f}\mu(f')=\cases{1,&si $f=1$ ;\cr
0,&si $f\not=1$ ;\cr}
$$
d'o\`u imm\'ediatement $d\,t=u(1)=1$. La d\'emonstration de
la formule $t\,d=1$ est analogue.\cqfd

\titrecourant={\eightrm 2. UNE AUTRE G\'EN\'ERALISATION
DU TH\'EOR\`EME DE MACMAHON}
\sectiona 2. Une autre g\'en\'eralisation du th\'eor\`eme de
MacMahon|
Dans ce n\omini, on note~$A$ un anneau {\it
commutatif} avec \'el\'ement unit\'e. On introduit des
ind\'etermin\'ees non commutatives $\xi_1$, \dots~,
$\xi_n$ et des s\'eries formelles \`a coefficients dans~$A$
en ces ind\'etermin\'ees. Rappelons qu'une telle s\'erie s'\'ecrit
de mani\`ere unique sous la forme $h=\sum_wa_w\cdot
w$ o\`u~$w$ parcourt l'ensemble des mots en $\xi_1$,
\dots~, $\xi_n$ ; de mani\`ere explicite, on a
$$
h=\sum_{r=0}^\infty\, \sum_{i_1,\ldots,i_r=1}^\infty
a_{i_1,\ldots,i_r}\,\xi_{i_1}\cdots \xi_{i_r}.
\leqno(10)
$$
On a d\'efini au chapitre IV.3 le produit d'intercalement
$w\intercal w'$ pour deux mots~$w$ et~$w'$ ; on \'etend
cette d\'efinition au cas des s\'eries en posant
$$\displaylines{(11)\quad
\Bigl(\sum_w a'_w\cdot w\Bigr)
\intercal
\Bigl(\sum_w a''_w\cdot w\Bigr)
=\sum_{w'w''}a'_{w'}a''_{w''}(w'\intercal w'')\hfill\cr
\noalign{\vskip -10pt}
\hfill{}
=\sum_w\Bigl(\sum_{w'\intercal w''=w}
a'_{w'}a''_{w''}\Bigr).w.\quad\cr}
$$
Pour cette multiplication, les s\'eries formelles en
$\xi_1$, \dots~, $\xi_n$ forment un
anneau~$A_n^\tau$.

Soit $B=(b_{ij})$ une matrice carr\'ee d'ordre~$n$ \`a
\'el\'ements dans~$A$. Nous lui associerons les deux
s\'eries
$$
\displaylines{\rlap{(12)}\hfill
t^\tau=\sum_{r=0}^\infty
\sum_{k_1,\ldots,k_r}
b_{\ell_1k_1}\cdots b_{\ell_rk_r}\,
\xi_{k_1}\cdots \xi_{k_r}\hfill\cr
\noalign{\hbox{(o\`u $\ell_1$, \dots~, $\ell_r$ d\'esigne le
r\'earrangement croissant de $k_1$, \dots~, $k_r$) et}}
\rlap{(13)}\hfill
d^\tau=\sum_{r=0}^n(-1)^r
\sum_{i_1<\cdots<i_r}\;
\sum_{\sigma\in {\goth S}_r}
\varepsilon_\sigma\,
b_{i_1,\sigma(i_1)}\cdots b_{i_r,\sigma(i_r)}\,
\xi_{\sigma(i_1)}\cdots \xi_{\sigma(i_r)}.\hfill\cr}
$$

\th Proposition 5.2|Les s\'eries $t^\tau$ et $d^\tau$
sont inverses dans l'anneau $A_n^\tau$.
\finth

On note $Q$ le mono\"\i de des r\'earrangements et $Q'$
le mono\"\i de d'intercalement construits sur l'ensemble
$\{1,2,\ldots,n\}$ (voir chap.~IV.1 et IV.3). Comme au
n\omini\ pr\'ec\'edent, on construit un homomorphisme~$v$
de~$Q$ dans le mono\"\i de multiplicatif~$\Omega$ de
l'anneau~$A$ par la formule
$$
v{\textstyle{j_1\cdots j_p\choose i_1\cdots i_p}}
=\prod_{k=1}^p b_{i_k,j_k}.\leqno(14)
$$
En tenant compte de l'isomorphisme $\Gamma$ de $Q'$
sur~$Q$ d\'efini au chapitre~IV.3, on obtient un
homomorphisme $b=v\circ \Gamma$ de~$Q'$
dans~$\Omega$ ; si $w=k_1\cdots k_r$ est un mot et si
$\ell_1\cdots \ell_r$ est son r\'earrangement croissant,
on a
$$
b(w)=b_{\ell_1k_1}\cdots b_{\ell_rk_r}.\leqno(15)
$$

La forme de la fonction de M\"obius de $Q$ (voir
remarque~3.6) et la formule pr\'ec\'edente permettent de
mettre les s\'eries $t^\tau$ et $d^\tau$ sous la forme
$$
\leqalignno{t^\tau&=\sum_{w\in Q'}b(w)\cdot w&(16)\cr
d^\tau&=\sum_{w\in Q'}b(w)\mu(w)\cdot w.&(17)\cr}
$$
Comme on a $b(w'\intercal w'')=b(w')\cdot b(w'')$, la
formule $t^\tau d^\tau=d^\tau t^\tau=1$ r\'esulte de
(16) et (17) par un raisonnement analogue \`a celui de la
partie~(C) de la d\'emonstration du th\'eor\`eme~5.1.\cqfd

\medskip
Soit $A_n$ l'anneau des s\'eries formelles \`a coefficients
dans~$A$ en des ind\'etermin\'ees commutatives $X_1$,
\dots~, $X_n$. Pour toute s\'erie formelle $h\in
A_n^\tau$, soit $\varepsilon_n(h)$ la s\'erie obtenue par
substitution de~$X_1$ \`a~$\xi_1$, \dots~, $X_n$
\`a~$\xi_n$ ; alors $\varepsilon_n$ est un
homomorphisme d'anneaux de $A_n^\tau$ dans~$A_n$.
Il est imm\'ediat que $\varepsilon_n$ transforme les
s\'eries~$t^\tau$ et~$d^\tau$ en les s\'eries~$t$ et~$d$
du n\omini~1. La relation $t^\tau d^\tau=d^\tau
t^\tau=1$ entra\^\i ne donc la relation $td=dt=1$, qui
n'est autre que le th\'eor\`eme de MacMahon. C'est en ce sens
que la proposition~5.2 g\'en\'eralise le th\'eor\`eme de
MacMahon.



\vfill\eject
\pagetitretrue

\auteurcourant={{\eightrm 
CHAPITRE VI : RELATIONS ENTRE COEFFICIENTS BINOMIAUX}}

\vglue 2cm
\centerline{{\eightrm CHAPITRE VI}}
\vskip 2mm
\centerline{{\bf RELATIONS ENTRE COEFFICIENTS BINOMIAUX}}

\vskip 6mm plus 2mm
\sectiona 1. Description du graphe|
Le graphe $G$ a trois sommets num\'erot\'es 1, 2, 3 et des ar\^etes
$a_{ij}$ joignant le sommet~$i$ au sommet~$j$ pour
$i\not=j$. On voit imm\'ediatement qu'il y a cinq cycles
$$
c_1=[12],\quad c_2=[13],\quad c_3=[23],\quad
c_4=[123],\quad c_5=[132].
$$
Deux cycles distincts ayant toujours un sommet en commun, un
circuit~$f$ dans~$G$ s'\'ecrit de mani\`ere unique sous la forme
$f=c_{i_1}\cdots c_{i_m}$ avec $1\le i_k\le 5$ pour $1\le k\le
m$. On note $\varepsilon_k(f)$ le nombre de fois que le
cycle~$c_k$ appara\^\i t dans le circuit~$f$ ; la parit\'e d'un
circuit~$f$ est par d\'efinition celle de sa longueur, autrement
dit celle de l'entier $\varepsilon_4(f)+\varepsilon_5(f)$ car les
cycles~$c_1$, $c_2$ et~$c_3$ sont de longueur paire.

Soit $f$ un circuit ; la matrice d'incidence $N(f)$ de~$f$ est
\'egale \`a $\sum\limits_{k=1}^5 \varepsilon_k(f)\cdot I_k$,
o\`u~$I_k$ est la matrice d'incidence de~$c_k$. Les
matrices~$I_k$ sont donn\'ees dans la table suivante, o\`u les
points repr\'esentent des z\'eros :
$$\displaylines{
I_1=\pmatrix{\cdot&1&\cdot\cr
1&\cdot&\cdot\cr
\cdot&\cdot&\cdot\cr}\quad
I_2=\pmatrix{\cdot&\cdot&1\cr
\cdot&\cdot&\cdot\cr
1&\cdot&\cdot\cr}\quad
I_3=\pmatrix{\cdot&\cdot&\cdot\cr
\cdot&\cdot&1\cr
\cdot&1&\cdot\cr}\cr
\noalign{\medskip}
I_4=\pmatrix{\cdot&1&\cdot\cr
\cdot&\cdot&1\cr
1&\cdot&\cdot\cr}\quad
I_5=\pmatrix{\cdot&\cdot&1\cr
1&\cdot&\cdot\cr
\cdot&1&\cdot\cr}.\cr}
$$

\sectiona 2. \'Etude des circuits pairs|
Les multiplicit\'es $\varepsilon_k=\varepsilon_k(f)$ (pour $1\le
k\le 5$) d'un circuit pair sont des entiers positifs tels que
$\varepsilon_4+\varepsilon_5$ soit pair. Il est imm\'ediat qu'un
tel syst\`eme d'entiers s'\'ecrit de mani\`ere unique sous la forme
$$
\displaylines{\rlap{(1)}\hfill
\varepsilon_1=c-n,\quad
\varepsilon_2=b-n,\quad
\varepsilon_3=a-n,\hfill\cr
\rlap{(2)}\hfill
\varepsilon_4=n+k,\quad
\varepsilon_5=n-k,\hfill\cr
\noalign{\hbox{o\`u les entiers $a$, $b$, $c$, $n$, $k$ sont
assujettis aux relations}}
\rlap{(3)}\hfill
|k|\le n\le p,\hfill\cr}
$$

\goodbreak\noindent
o\`u $p$ est le plus petit des trois sommets $a$, $b$, $c$. La
matrice d'incidence
$N(f)=\sum\limits_{i=1}^5\varepsilon_i\cdot I_i$ est alors de
la forme
$$
N=\pmatrix{0&c+k&b-k\cr
c-k&0&b-k\cr
b+k&a-k&0\cr} ;
$$
on notera que $n$ n'intervient pas explicitement dans la
matrice pr\'ec\'edente ; de plus, on a $M=S+k\cdot V$ o\`u $S$ est
la matrice sym\'etrique {\eightpoint $\left(\matrice{0&c&b\cr
c&0&a\cr
b&a&0\cr}\right)$} et $V=I_4-I_5$ la matrice antisym\'etrique
{\eightpoint\smash{$\left(\matrice{0&1&-1\cr
-1&0&1\cr
1&-1&0\cr}\right)$,}} ce qui indique la signification des
entiers
$a$, $b$, $c$, $k$.

L'identit\'e (A) du formulaire s'obtient en  \'evaluant de deux
mani\`eres diff\'erentes le nombre~$N$ des circuits~$f$ tels que
$N(f)=M$. Rappelons qu'un circuit correspondant \`a la
matrice~$M$ s'obtient en attachant \`a chacun des sommets une
suite finie d'ar\^etes ayant ce sommet pour source ; la suite des
ar\^etes attach\'ees au sommet~1 doit faire intervenir $c+k$ fois
l'ar\^ete~$a_{12}$ et $b-k$ fois l'ar\^ete~$a_{13}$ et il y a donc
$b+c\choose c+k$ choix possibles. \footnote{$(^8)$}{Le nombre
de suites faisant intervenir $\alpha_1$ fois $x_1$, \dots~,
$\alpha_p$ fois~$x_p$ est \'egal \`a
$(\alpha_1+\cdots+\alpha_p)!/(\alpha_1!\,\cdots\, \alpha_p!)$.
On note $m\choose n$ le coefficient binomial
$m!/((m-n)!\,n!)$.} Raisonnant de mani\`ere analogue pour les
sommets~2 et~3, on trouve
$$
N={b+c\choose c+k}{c+a\choose a+k}{a+b\choose b+k}.\leqno(5)
$$
Par ailleurs, vu l'unicit\'e de la d\'ecomposition d'un circuit en
cycles, le nombre des circuits qui font
intervenir~$\varepsilon_i$ fois le cycle~$c_i$ pour $1\le i\le
5$ est \'egal \`a
$(\varepsilon_1+\varepsilon_2+\varepsilon_3+\varepsilon_4+
\varepsilon_5)!/(\varepsilon_1!\; \varepsilon_2!\;
\varepsilon_3!\;\varepsilon_4!\;\varepsilon_5!)$ ;
si l'on \'evalue les~$\varepsilon_i$ conform\'ement aux
formules~(1) et~(2) et qu'on somme sur l'entier~$n$ soumis \`a la
condition~(3), on trouve
$$
N=\sum_{n=|k|}^p
{(a+b+c-n)!\over (a-n)!\, (b-n)!\, (c-n)!\, (n+k)!\, (n-k)!}
\leqno(6)
$$
et la comparaison de~(5) et (6) \'etablit la formule (A).

\sectiona 3. \'Etude des circuits impairs|
L'entier $\varepsilon_4+\varepsilon_5$ \'etant cette fois impair,
il faut remplacer les formules~(2) et~(3) par les suivantes :
$$
\displaylines{\rlap{$(2')$}\hfill
\varepsilon_4=n+k,\quad \varepsilon_5=n-k+1,\hfill\cr
\rlap{$(3')$}\hfill
\kappa\le n\le p\quad{\rm avec}\ 
\kappa=\max\{-k,k-1\}\ {\rm et}\ 
p=\min\{a,b,c\}.\hfill\cr}
$$
La matrice d'incidence $N(f)=\sum\limits_{i=1}^5
\varepsilon_i\cdot I_i$ prend alors la forme
$$
M'=\pmatrix{0&c+k&b-k+1\cr
c-k+1&0&a+k\cr
b+k&a-k+1&0\cr};\leqno(4')
$$
l'\'evaluation directe du nombre~$N'$ des circuits~$f$ tels que
$N(f)=M'$ conduit \`a la formule
$$
N'={b+c+1\choose c+k}{c+a+1\choose a+k}
{a+b+1\choose b+k}\leqno(5')
$$
tandis que l'utilisation de la d\'ecomposition d'un circuit en
produit de cycles conduit \`a l'\'evaluation
$$
N'=\sum_{n=\kappa}^p
{(a+b+c-n+1)!\over (a-n)!\, (b-n)!\, (c-n)!\, (n+k)!\,
(n-k+1)!}.\leqno(6')
$$
La comparaison de ces deux r\'esultats \'etablit la formule
$({\rm A}')$.

\sectiona 4. Autres identit\'es|
Montrons d'abord comment la formule (A) entra\^\i ne toutes celles
du cas pair ; nous commencerons par~(B). Nous consid\'erons
l'ensemble~$I$ des couples $(k,n)$ d'entiers satisfaisant aux
in\'egalit\'es $|k|\le n\le p$, c'est-\`a-dire les points de
coordonn\'ees enti\`eres du triangle $ABC$ ci-apr\`es :

\titrecourant={\eightrm 4. AUTRES IDENTIT\'ES}
\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}}}}

$$\vbox{\offinterlineskip
\vskip3cm
\fleche(-30,0)\dir(1,0)\long{60}
\fleche(0,-10)\dir(0,1)\long{40}
\segment(-20,20)\dir(1,0)\long{40}
\segment(0,0)\dir(1,1)\long{20}
\segment(0,0)\dir(-1,1)\long{20}
\segment(20,20)\dir(0,-1)\long{1}
\segment(20,18)\dir(0,-1)\long{1}
\segment(20,16)\dir(0,-1)\long{1}
\segment(20,14)\dir(0,-1)\long{1}
\segment(20,12)\dir(0,-1)\long{1}
\segment(20,10)\dir(0,-1)\long{1}
\segment(20,8)\dir(0,-1)\long{1}
\segment(20,6)\dir(0,-1)\long{1}
\segment(20,4)\dir(0,-1)\long{1}
\segment(20,2)\dir(0,-1)\long{2}
%
\segment(-20,20)\dir(0,-1)\long{1}
\segment(-20,18)\dir(0,-1)\long{1}
\segment(-20,16)\dir(0,-1)\long{1}
\segment(-20,14)\dir(0,-1)\long{1}
\segment(-20,12)\dir(0,-1)\long{1}
\segment(-20,10)\dir(0,-1)\long{1}
\segment(-20,8)\dir(0,-1)\long{1}
\segment(-20,6)\dir(0,-1)\long{1}
\segment(-20,4)\dir(0,-1)\long{1}
\segment(-20,2)\dir(0,-1)\long{2}
%
\centerput(2,30){$n$}
\centerput(22,20){$B$}
\centerput(2,22){$p$}
\centerput(-22,20){$C$}
\centerput(-20,-3){$-p$}
\centerput(2,-3){$A$}
\centerput(20,-3){$p$}
\centerput(32,-1){$k$}
%
\segment(-18,20)\dir(0,-1)\long{2}
\segment(-16,20)\dir(0,-1)\long{4}
\segment(-14,20)\dir(0,-1)\long{6}
\segment(-12,20)\dir(0,-1)\long{8}
\segment(-10,20)\dir(0,-1)\long{10}
\segment(-8,20)\dir(0,-1)\long{12}
\segment(-6,20)\dir(0,-1)\long{14}
\segment(-4,20)\dir(0,-1)\long{16}
\segment(-2,20)\dir(0,-1)\long{18}
%
\segment(2,20)\dir(0,-1)\long{18}
\segment(4,20)\dir(0,-1)\long{16}
\segment(6,20)\dir(0,-1)\long{14}
\segment(8,20)\dir(0,-1)\long{12}
\segment(10,20)\dir(0,-1)\long{10}
\segment(12,20)\dir(0,-1)\long{8}
\segment(14,20)\dir(0,-1)\long{6}
\segment(16,20)\dir(0,-1)\long{4}
\segment(18,20)\dir(0,-1)\long{2}
\vskip.8cm
}
$$
Pour toute fonction $f$ sur $I$, on a la formule de sommation
$$\displaylines{\rlap{(7)}\hfill
\sum_{(k,n)\in I}f(k,n)=\sum_{k=-p}^p
\sum_{n=|k|}^pf(k,n)=\sum_{n=0}^p\sum_{k=-n}^nf(k,n).\hfill\cr
\noalign{\hbox{Posons en particulier}}
f(k,n)={(a+b+c-n)!\over (a-n)!\, (b-n)!\, (c-n)!}
{u^{p+k}\over (n+k)!} {v^{p-k}\over (n-k)!} ;\cr
\noalign{\hbox{La formule du bin\^ome entra\^\i ne}}
(uv)^{p-n}{(u+v)^{2n}\over (2n)!}
=\sum_{k=-n}^n
{u^{p+k}\over (n+k)!} {v^{p-k}\over (n-k)!},\cr
}
$$

\goodbreak\noindent
et le second membre de (B) est donc \'egal \`a
$\sum\limits_{n=0}^p \sum\limits_{k=-n}^n f(k,n)$. D'autre
part, la formule~(A) montre que le premier membre de~(B) est
\'egal \`a $\sum\limits_{k=-p}^p\sum\limits_{n=|k|}^p  f(k,n)$,
d'o\`u~(B) d'apr\`es~(7).

Il est clair que (C) est le cas particulier $u=v=1$ de~(B). Si
l'on fait $u=1$ et $v=-1$, on a $(u+v)^{2n}=0$ pour $n>0$
et le second membre de~(B) se r\'eduit au seul terme pour lequel
$n=0$, lui-m\^eme \'egal \`a $(-1)^p(a+b+c)!/(a!\,b!\,c!)$ ;
la formule (D) est donc le cas particulier $u=1$, $v=-1$
de~(B). Si l'on fait $a=b=c=q$ et $k=\ell-q$, d'o\`u $p=q$,
dans~(A) et qu'on remplace l'indice de sommation~$n$ par
$q-m$, on obtient~(E) ; on d\'eduit~(F) de~(B) par les m\^emes
transformations. Enfin~(G) s'obtient en faisant $u=v=1$
dans~(F) et~(H) est le cas particulier $a=b=c=q$ de~(D).

Les formules du cas impair se d\'eduisent de $({\rm A}')$ de
mani\`ere analogue ; seules $({\rm D}'')$ et $({\rm H}')$ m\'eritent
un nouvel examen. Rempla\c cons~$u$ par $1+t$ et~$v$ par~$-1$
dans~$({\rm B}')$ ; on obtient une \'egalit\'e de la forme
$$\displaylines{\rlap{(8)}\hfill
\sum_{k=-p}^{p+1}r_k(-1)^{k+1}(1+t)^{p+k}
=\sum_{n=0}^p s_n(-1)^n (1+t)^{p-n}{t^{2n+1}\over (2n+1)!}
\hfill\cr
\noalign{\hbox{avec}}
r_k={b+c+1\choose c+k}{c+a+1\choose a+k}
{a+b+1\choose b+k}\ {\rm et}\ 
s_n={(a+b+c-n+1)!\over (a-n)!\, (b-n)!\, (c-n)!}.\cr}
$$
Le coefficient de~$t$ dans le polyn\^ome $(1+t)^{p+k}$ est
\'egal \`a $p+k$ et les termes du second membre de~(8) avec
$n>0$ sont divisibles par~$t^3$ et ne contribuent donc pas au
coefficient de~$t$. Prenant le coefficient de~$t$ dans les deux
membres de~(8), on obtient
$$
\sum_{k=-p}^{p+1}r_k(-1)^{k+1}(p+k)=s_0;\leqno(9)
$$
faisant $t=0$ dans (8), on obtient par ailleurs
\smash{$\sum\limits_{k=-p}^{p+1}(-1)^{k+1}r_k=0$, }d'o\`u
finalement
$\sum\limits_{k=-p}^{p+1}(-1)^{k+1}k\,r_k=s_0$, ce
qui n'est autre que $({\rm D}'')$. On d\'emontre de mani\`ere
analogue $({\rm H}')$ en faisant $u=1+t$ et $v=-1$ dans
$({\rm F}')$ et en \'egalant les coefficients de~$t$ dans les deux
membres de l'\'egalit\'e obtenue ainsi.

\sectiona 5. Utilisation du ``Master Theorem" de MacMahon|
Nous allons montrer comment d\'eduire les relations~(B)
et~$({\rm B}')$ du th\'eor\`eme de MacMahon appliqu\'e \`a la matrice
{\eightpoint $\left(\matrice{0&s&t\cr
t&0&s\cr
s&t&0\cr}\right)$} o\`u~$s$ et~$t$ sont deux ind\'etermin\'ees.
Notons $a$, $b$, $c$ des entiers positifs et $p$ le plus petit
de ces entiers. Nous noterons $X_1$, $X_2$ et $X_3$ de
nouvelles ind\'etermin\'ees, $P$ le polyn\^ome
$$
(sX_2+tX_3)^{b+c}(sX_3+tX_1)^{c+a}(sX_1+tX_2)^{a+b}
$$

\goodbreak
\noindent
et $D$ le d\'eterminant de la matrice
$$
\pmatrix{1&-sX_2&-tX_3\cr
-tX_1&1&-sX_3\cr
-sX_1&-tX_2&1\cr}.
$$
Enfin, nous noterons $U$ le coefficient du mon\^ome
$X_1^{b+c}X_2^{c+a}X_3^{a+b}$ dans~$P$ et~$V$ le
coefficient du m\^eme mon\^ome dans la s\'erie formelle~$D^{-1}$.

\medskip
(a) {\it Calcul de} $U$ : en utilisant la formule du bin\^ome, on
d\'eveloppe~$f$ sous la forme
$$
\displaylines{\quad
F=\sum_{\lambda=-c}^b {b+c\choose c+\lambda}
(sX_2)^{c+\lambda} (tX_3)^{b-\lambda}
\sum_{\mu=-a}^c {c+a\choose a+\mu} (sX_3)^{a+\mu}
(tX_1)^{c-\mu}\hfill\cr
\hfill{}\times\sum_{\nu=-b}^a {a+b\choose b+\nu}
(sX_1)^{b+\nu} (tX_2)^{a-\nu}\cr
\kern.65cm{}=
\sum_{\lambda,\mu,\nu}{b+c\choose c+\lambda}
{c+a\choose a+\mu} {a+b\choose b+\nu}
s^{(a+b+c)+(\lambda+\mu+\nu)}
t^{(a+b+c)-(\lambda+\mu+\nu)}\hfill\cr
\noalign{\vskip-10pt}
\hfill{}\times X_1^{b+c-\mu+\nu}
X_2^{c+a-\nu+\lambda}
X_3^{a+b-\lambda+\mu}.\cr
}$$
On obtient le coefficient $U$ de
$X_1^{b+c}X_2^{c+a}X_3^{a+b}$ en faisant la somme de tous
les termes pour lesquels $\lambda=\mu=\nu$ sont \'egaux \`a un
entier~$k$ tel que $-p\le k\le p$, d'o\`u
$$
U=\sum_{k=-p}^p {b+c\choose c+k}{c+a\choose
a+k}{a+b\choose b+k}\,s^{a+b+c+3k}\,t^{a+b+c-3k}.\leqno(10)
$$

(b) {\it Calcul de }$V$ : on trouve imm\'ediatement
$$
D=1-stX_2X_3-stX_3X_1-stX_1X_2-(s^3+t^3)X_1X_2X_3
=1-H
$$
d'o\`u par la formule du bin\^ome
$$\displaylines{
D^{-1}=\sum_{m=0}^\infty H^m
=\kern-10pt\sum_{\alpha,\beta,\gamma,\delta\ge 0}\kern-5pt
{(\alpha+\beta+\gamma+\delta)!
\over \alpha!\,\beta!\,\gamma!\,\delta!}
(stX_2X_3)^\alpha (stX_3X_1)^\beta
(stX_1X_2)^\gamma\hfill\cr
\noalign{\vskip-10pt}
\hfill{}\times (s^3+t^3)^\delta (X_1X_2X_3)^\delta\cr
\kern.7cm{}
=\kern-10pt\sum_{\alpha,\beta,\gamma,\delta\ge 0}\kern-5pt
{(\alpha+\beta+\gamma+\delta)!
\over \alpha!\,\beta!\,\gamma!\,\delta!}
(st)^{\alpha+\beta+\gamma}(s^3+t^3)^\delta
X_1^{\beta+\gamma+\delta}
X_2^{\gamma+\alpha+\delta}
X_3^{\alpha+\beta+\delta}.\hfill\cr}
$$
Or les nombres entiers positifs solutions du syst\`eme d'\'equations
lin\'eaires
$$
\eqalign{\beta+\gamma+\delta&=b+c\cr
\gamma+\alpha+\delta&=c+a\cr
\alpha+\beta+\delta&=a+b\cr}
$$
sont donn\'es par $\alpha=a-n$, $\beta=b-n$, $\gamma=c-n$,
$\delta=2n$ o\`u~$n$ parcourt l'ensemble des entiers compris
entre~0 et~$p$. 
On conclut alors
$$
V=\sum_{n=0}^p {(a+b+c-n)!\over (a-n)!\, (b-n)!\, (c-n)!}
(st)^{a+b+c-3n}
{(s^3+t^3)^{2n}\over (2n)!}.\leqno(11)
$$

(c) {\it D\'emonstration de }(B) : le th\'eor\`eme de MacMahon fournit
l'\'egalilt\'e $U=V$. Si l'on remplace~$s^3$ par~$u$ et~$t^3$
par~$v$ dans l'\'egalit\'e
$$
(st)^{3p-(a+b+c)}U=(st)^{3p-(a+b+c)}V,
$$
on obtient imm\'ediatement (B).

La d\'emonstration de $({\rm B}')$ s'obtient de mani\`ere analogue
par la consid\'e\-ration des coefficients du mon\^ome
$X_1^{b+c+1}X_2^{c+a+1}X_3^{a+b+1}$ dans le poly\-n\^ome
$$
Q=(sX_2+tX_3)^{b+c+1}(sX_3+tX_1)^{c+a+1}
(sX_1+tX_2)^{a+b+1}$$
et dans la s\'erie formelle $D^{-1}$.

\vfill\eject
\titrecourant={{\eightrm FORMULAIRE}}
\centerline{\bf FORMULAIRE}

\bigskip
Dans tout ce formulaire, on note $q$, $a$, $b$ et $c$ des
entiers positifs et l'on pose $p=\min\{a,b,c\}$.

\medskip
I. {\it Cas pair}.
$$\displaylines{({\rm A})\quad
{b+c\choose c+k}{c+a\choose a+k}{a+b\choose b+k}\hfill\cr
\hfill{}
=\sum_{n=|k|}^p {(a+b+c-n)!\over
(a-n)!\, (b-n)!\, (c-n)!\, (n+k)!\, (n-k)!}\ 
\hbox{
lorsque $|k|\le p$.}\cr
({\rm B})\quad
\sum_{k=-p}^p
{b+c\choose c+k}{c+a\choose a+k}{a+b\choose b+k}
u^{p+k}v^{p-k}\hfill\cr
\kern1.6cm {}=\sum_{n=0}^p
{(a+b+c-n)!\over
(a-n)!\, (b-n)!\, (c-n)!}
(uv)^{p-n}{(u+v)^{2n}\over (2n)!}\hfill
 \hbox{\rm [Foata 1965]}\cr
({\rm C})\quad
\sum_{k=-p}^p
{b+c\choose c+k}{c+a\choose a+k}{a+b\choose b+k}
=\sum_{n=0}^p
{(a+b+c-n)!\over
(a-n)!\, (b-n)!\, (c-n)!}
{2^{2n}\over (2n)!}\hfill\cr
({\rm D})\quad
\sum_{k=-p}^p (-1)^k
{b+c\choose c+k}{c+a\choose a+k}{a+b\choose b+k}
={(a+b+c)!\over a!\,b!\,c!}\hfill
 \hbox{\rm [Fjeldstad 1954]}\cr
({\rm E})\quad
{2q\choose \ell}^3=
\sum_{m=0}^\ell
{(2q+m)!\over (m!)^3\, (\ell-m)!\, (2q-\ell-m)!}
\quad{\rm si}\ 0\le \ell\le 2q\hfill\cr
({\rm F})\quad
\sum_{\ell=0}^{2q}
{2q\choose \ell}^3u^\ell v^{2q-\ell}=
\sum_{m=0}^\ell
{(2q+m)!\over (m!)^3\, (2q-2m)!}
(uv)^m(u+v)^{2q-2m}\hfill\cr
\noalign{\vskip-5pt}
\hfill
\hbox{\rm [MacMahon 1915]}\cr
({\rm G})\quad
\sum_{\ell=0}^{2q}
{2q\choose \ell}^3=
\sum_{m=0}^\ell
{(2q+m)!\over (m!)^3\, (2q-2m)!}
2^{2q-2m}\hfill
\hbox{\rm [MacMahon 1915]}\cr
({\rm H})\quad
\sum_{\ell=0}^{2q}(-1)^\ell
{2q\choose \ell}^3=
(-1)^q
{(3q)!\over (q!)^3}
\hfill
\hbox{\rm [Dixon 1890]}\cr
}$$

\medskip
II. {\it Cas impair } :
$$\displaylines{({\rm A}')\quad
{b+c+1\choose c+k}{c+a+1\choose a+k}{a+b+1\choose b+k}
\hfill\cr
\hfill{}
=\sum_{n=\kappa}^p
{(a+b+c-n+1)!\over (a-n)!\, (b-n)!\, (c-n)!\,(n+k)!\,
(n-k+1)!}\cr
\hfill
\hbox{lorsque $\kappa=\max\{-k,k-1\}$ est major\'e par
$p$.}\cr}
$$

$$
\displaylines{({\rm B}')\quad
\sum_{k=-p}^{p+1}
{b+c+1\choose c+k}{c+a+1\choose a+k}{a+b+1\choose b+k}
u^{p+k}v^{p-k+1}
\hfill\cr
\hfill{}
=\sum_{n=0}^p
{(a+b+c-n+1)!\over (a-n)!\, (b-n)!\, (c-n)!}
(uv)^{p-n}{(u+v)^{2n+1}\over (2n+1)!}\cr
({\rm C}')\quad
\sum_{k=-p}^{p+1}
{b+c+1\choose c+k}{c+a+1\choose a+k}{a+b+1\choose b+k}
\hfill\cr
\hfill{}
=\sum_{n=0}^p
{(a+b+c-n+1)!\over (a-n)!\, (b-n)!\, (c-n)!}
{2^{2n+1}\over (2n+1)!}\kern1.7cm\cr
({\rm D}')\quad
\sum_{k=-p}^{p+1}(-1)^k
{b+c+1\choose c+k}{c+a+1\choose a+k}{a+b+1\choose b+k}
=0\hfill\cr
({\rm D}'')\quad
\sum_{k=-p}^{p+1}(-1)^{k+1}k
{b+c+1\choose c+k}\!{c+a+1\choose a+k}\!{a+b+1\choose b+k}
\!=\!{(a+b+c+1)!\over a!\,b!\,c!}\hfill\cr
({\rm E}')\quad
{2q+1\choose \ell}^3
=\sum_{m=0}^\ell
{(2q+m+1)!\over (m!)^3\,(\ell-m)!\,(2q-\ell-m+1)!}
\quad{\rm si}\ 0\le \ell\le q\hfill\cr
({\rm F}')\quad
\sum_{\ell=0}^{2q+1}
{2q+1\choose \ell}^3
u^\ell v^{2q-\ell+1}\hfill\cr
\noalign{\vskip-8pt}
\hfill{}
=\sum_{m=0}^\ell
{(2q+m+1)!\over (m!)^3\,(2q-2m+1)!}
(uv)^m(u+v)^{2q-2m+1}\cr
({\rm G}')\quad
\sum_{\ell=0}^{2q+1}
{2q+1\choose \ell}^3
=\sum_{m=0}^\ell
{(2q+m+1)!\over (m!)^3\,(2q-2m+1)!}
2^{2q-2m+1}\hfill\cr
({\rm H}')\quad
\sum_{\ell=0}^{2q+1}(-1)^{\ell+1}\ell\,
{2q+1\choose \ell}^3
=(-1)^q
{(3q+1)!\over (q!)^3}.\hfill\cr
}
$$

\vfill\eject
\pagetitretrue

\auteurcourant={{\eightrm 
CHAPITRE VII : APPLICATIONS PROBABILISTES}}

\vglue 2cm
\centerline{{\eightrm CHAPITRE VII}}
\vskip 2mm
\centerline{{\bf APPLICATIONS PROBABILISTES}}

\vskip 6mm plus 2mm
\sectiona 1. Identit\'e de Spitzer|
Nus consid\`ererons dans la suite des s\'eries formelles \`a
coefficients complexes en une ind\'etermin\'ee~$t$. Si~$U$ est
une telle s\'erie, sans terme constant, son exponentielle est la
s\'erie \smashbot{$\exp U=\sum\limits_{m=0}^\infty
U^m/m!$}\  La formule du bin\^ome montre imm\'ediatement que
l'on a
$$
\exp(U+V)=(\exp U)\cdot (\exp V).\leqno(1) 
$$
De plus, pour toute s\'erie $V$ sans terme constant, il existe une
s\'erie~$U$ sans terme constant telle que
$V=\sum\limits_{m=1}^\infty U^m/m!=(\exp U)-1$ et une
seule : ceci r\'esulte des th\'eor\`emes usuels sur la r\'esolution
``d'\'equations formelles." On en d\'eduit que l'application
exponentielle est une bijection de l'ensemble des s\'eries
sans terme constant, sur l'ensemble des s\'eries de terme
constant~1. L'application r\'eciproque est appel\'ee logarithme ; on
note $\log V$ le logarithme de~$V$.

Ces g\'en\'eralit\'es \'etant rappel\'ees, consid\'erons deux suites
$$\displaylines{\noalign{\vskip-5pt}
(a_n)_{n\ge 1}=(a_1,a_2,\ldots\,)\quad
{\rm et}\quad(b_n)_{n\ge 1}=(b_1,b_2,\ldots\,)\cr
\noalign{\line{de nombres complexes. On dit qu'elles satisfont \`a
l'{\it identit\'e de Spitzer} si l'on~a}}
\rlap{(2)}\hfill
1+\sum_{n=1}^\infty a_n\,t^n=\exp\sum_{k=1}^\infty
{b_k\over k}\,t^k.\hfill\cr}
$$
D'apr\`es ce qui pr\'ec\`ede, la correspondance
$(a_n)_{n\ge 1}\leftrightarrow (b_n)_{n\ge 1}$
exprim\'ee par cette identit\'e est bijective.

On peut donner une forme r\'ecurrente plus simple \`a cette
relation. Notons~$U'$ la d\'eriv\'ee d'une s\'erie~$U$ ; on sait que
la d\'eriv\'ee de $\exp U$ est $U'\cdot \exp U$. Posons alors
$$
A=1+\sum_{n=1}^\infty a_n\,t^n,\quad
B=\sum_{k=1}^\infty {b_k\over k}\,t^k.$$
La relation (2) s'\'ecrit $A=\exp B$, d'o\`u $tA'=tB'\cdot \exp
B=A\cdot (tB')$ ; or on~a $tA'=\sum\limits_{n=1}^\infty
na_nt^n$ et $tB'=\sum\limits_{k=1}^\infty b_kt^k$ ; en
prenant le coefficient de~$t^n$ dans l'identit\'e
$tA'=A\cdot (tB')$, on trouve
$$
na_n=b_n+\sum_{k=1}^{n-1}a_k\cdot b_{n-k}
\quad(n\ge 1).\leqno(3)
$$
La suite $(b_n)_{n\ge 1}$ \'etant donn\'ee, les relations (3) pour
$n=1,2,\ldots$ d\'eterminent de mani\`ere unique la suite
$(a_n)_{n\ge 1}$ par r\'ecurrence. Autrement dit, la relation de
Spitzer \'equivaut au syst\`eme des relations~(3).

Notre but est maintenant de calculer explicitement le
coefficient~$a_n$ en fonction de $b_1$, \dots~, $b_n$ 
(pour $n\ge 1$ donn\'e). On a $B=B_1+B_2$ avec
$$
B_1=b_1t+{b_2\over 2}t^2+\cdots+ {b_n\over n}t^n,
\quad
B_2=\sum_{k=n+1}^\infty {b_k\over k}t^k.
$$
Comme la s\'erie $B_2$ est divisible par $t^{n+1}$, il en est de
m\^eme de la s\'erie
$(\exp B_2)-1=\sum\limits_{m=1}^\infty (B_2)^m/m!$ et
{\it a fortiori} de
$$
(\exp B_1)((\exp B_2)-1)=(\exp B_1)(\exp B_2)
-\exp B_1=\exp B-\exp B_1.
$$
Le coefficient de $t^n$ dans $\exp B$ est donc le m\^eme que
dans $\exp B_1$ ; or on a
$$\leqalignno{
\exp B_1&=\exp\Bigl(b_1t+{b_2\over 2}t^2+\cdots+{b_n\over
n}t^n\Bigr)\cr
&=\prod_{k=1}^n\exp {b_k\over k} t^k\cr
&=\prod_{k=1}^n \sum_{m=0}^\infty 
{1\over m!}\Bigl({b_k\over k}\Bigr)^mt^{km}\cr
&=\sum_{m_1,\ldots,m_n}
\prod_{k=1}^n {1\over m_k!}\Bigl({b_k\over k}\Bigr)^{m_k}
t^{km_k}.\cr
\noalign{\hbox{Finalement, on a}}
a_n&=\sum{b_1^{m_1}\cdots b_n^{m_n}
\over m_1!\,\cdots\,m_n!\; 1^{m_1}2^{m_2}\cdots n^{m_n}},
&(4)\cr
}
$$
la sommation \'etant \'etendue \`a toutes les suites
$(m_1,\ldots,m_n)$ de~$n$ entiers positifs satisfaisant \`a
$1m_1+2m_2+\cdots+m_n=n$.

Avant d'\'enoncer la proposition 7.1, il nous faudra introduire
quelques notations. On note~$\bboard C$ l'ensemble des nombres
complexes ; pour tout entier $n\ge 1$, on note ${\goth S}_n$
l'ensemble des permutations de $\{1,2,\ldots,n\}$ et
$\gamma_n$ la permutation circulaire d'ordre~$n$ d\'efinie par
$$
\gamma_n(i)=\cases{i+1,&si $1\le i\le n-1$ ;\cr
1,&si $i=n$.\cr}\leqno(5)
$$
Enfin, si $\sigma\in {\goth S}_m$ et $\tau\in {\goth S}_n$,
on note $\sigma\oplus \tau$ l'\'el\'ement~$\rho$ de ${\goth
S}_{m+n}$ d\'efini par
$$
\rho(i)=\cases{\sigma(i),&si $1\le i\le m$ ;\cr
m+\tau(i-m),&si $m+1\le i\le m+n$.\cr}\leqno(6)
$$

\goodbreak
\th Proposition 7.1|On suppose donn\'ee une suite de fonctions
\hfil\break
$h_n:{\goth S}_n\rightarrow {\bboard C}$ $($pour $n\ge 1)$
satisfaisant aux relations :

{\rm (a)} on a $h_n(\tau\sigma\tau^{-1})=h_n(\sigma)$
pour $\sigma,\tau$ dans ${\goth S}_n$ ;

{\rm (b)} on a $h_{m+n}(\sigma\oplus \tau)=h_m(\sigma)\cdot
h_n(\tau)$ pour $\sigma\in {\goth S}_m$ et $\tau\in {\goth
S}_n$.

\noindent
Posons $a_n=(1/n!)\sum_{\sigma\in {\goth S}_n} h_n(\sigma)$
et $b_n=h_n(\gamma_n)$. L'identit\'e de Spitzer est satisfaite
pour les suites 
$(a_n)_{n\ge 1}$ et $(b_n)_{n\ge 1}$.
\finth

Soit $\sigma\in {\goth S}_n$ ; supposons que $\sigma$ se
d\'ecompose en~$p$ cycles de longueurs respectives $n_1$,
\dots~, $n_p$. Il est bien connu qu'il existe $\tau\in {\goth
S}_n$ tel que
$$
\tau\sigma\tau^{-1}=\gamma_{n_1}\oplus\cdots\oplus
\gamma_{n_p};
$$
d'apr\`es les hypoth\`eses (a) et (b), on a alors
$$
h_n(\sigma)=h_n(\tau\sigma\tau^{-1})
=h_{n_1}(\gamma_{n_1})\cdots h_{n_p}(\gamma_{n_p})
=b_{n_1}\cdots b_{n_p}.
$$
Autrement dit, si $\sigma$ comporte $m_k$ cycles de
longueur~$k$ pour $k=1,2,\ldots, n$, on a
$h_n(\sigma)=b_1^{m_1}\cdots b_k^{m_k}$.
Il est bien connu qu'il existe dans~${\goth S}_n$ un nombre
\'egal \`a $n!/(m_1!\,\cdots\,m_n!\, 1^{m_1}\cdots n^{m_n})$
permutations ayant~$m_k$ cycles de longueur~$k$ pour
$k=1,2,\ldots,n$. On a alors
$$
a_n={1\over n!}\sum_{\sigma\in {\goth S}_n}h_n(\sigma)
={1\over n!}\sum{n!\over m_1!\,\cdots\,m_n!\;1^{m_1}\cdots
n^{m_n}}\,b_1^{m_1}\cdots b_n^{m_n},
$$
c'est-\`a-dire que la relation (4) est satisfaite.\cqfd

\rem Remarque $7.2$|Si l'on pose $h_n(\sigma)=1$ pour tout
$n\ge 1$ et tout $\sigma\in {\goth S}_n$, les conditions~(a)
et~(b) de la proposition~7.1 sont remplies. On a dans ce cas
$a_n=b_n=1$, d'o\`u
$$
1+\sum_{n=1}^\infty t^n=\exp\sum_{k=1}^\infty {t^k\over k}.
$$
Le premier membre est l'inverse de $1-t$ ; changeant~$t$
en~$-t$, puis prenant le logarithme de l'inverse des deux
membres (on a $(\exp U)^{-1}=\exp(-U)$\thinspace), on
retrouve l'identit\'e bien connue
$$
\log(1+t)=\sum_{k=1}^\infty (-1)^{k-1}{t^k\over k}.
$$

\def\Per{\mathop{\rm Per}\nolimits}
\sectiona 2. Propri\'et\'es du permanent|
Rappelons d'abord la d\'efinition du permanent $\Per(a_{ij})$
d'une matrice carr\'ee complexe $(a_{ij})_{1\le i,j\le n}$ : c'est
le nombre
$$
\sum_{\sigma\in {\goth S}_n}\prod_{i=1}^n a_{i,\sigma(i)}.
$$
Cette d\'efinition ne diff\`ere de celle du d\'eterminant que par
l'omission des signes~$\pm$.

\titrecourant={\eightrm 2. PROPRI\'ET\'ES DU PERMANENT}
\goodbreak
Dans la suite de ce n\omini, on note $X$ un ensemble
totalement ordonn\'e et~$u$ une fonction \`a valeurs complexes sur
$X\times X$. \footnote{$(^{10})$}{La d\'efinition du permanent
conserve un sens pour des matrices \`a coefficients dans un
anneau commutatif quelconque. On peut g\'en\'eraliser de mani\`ere
analogue les lemmes~7.3 et 7.4.}

\th Lemme 7.3|Pour $x_1$, \dots~, $x_n$ dans $X$, posons
$$
h_n(x_1,\ldots, x_n)=\prod_{i=1}^n u(\overline x_i,x_i),
\leqno(7)
$$
o\`u $\overline x_1\cdots \overline x_n$ est le r\'earrangement
croissant de $x_1\cdots x_n$. On a alors
$$
\sum_{\sigma\in {\goth S}_n}
h_n(x_{\sigma(1)},\ldots,x_{\sigma(n)})
=\Per(u(x_i,x_j))_{1\le i,j\le n}.\leqno(8)
$$
\finth

Notons $a(x_1,\ldots, x_n)$ le premier membre de (8) et
$b(x_1,\ldots,x_n)$ le second. Soit $\tau\in {\goth S}_n$ ; on a
$$
\leqalignno{b(x_{\tau(1)},\ldots, x_{\tau(n)})
&=\sum_{\sigma\in {\goth S}_n}
\prod_{i=1}^n u(x_{\tau(i)},x_{\tau\sigma(i)})\cr
&=\sum_{\sigma\in {\goth S}_n}
\prod_{i=1}^n u(x_j,x_{\tau\sigma\tau^{-1}(j)})\cr
&=\sum_{\sigma\in {\goth S}_n}
\prod_{i=1}^n u(x_j,x_{\sigma(j)})\cr
&=b(x_1,\ldots,x_n).\cr}
$$
Autrement dit, la fonction de $n$ variables~$b$ est sym\'etrique
; comme il en est \'evidemment de m\^eme de~$a$, il suffit
d'\'etablir la formule~(8) lorsque la suite $(x_1,\ldots,x_n)$ est
croissante. Mais dans ce cas, pour tout $\sigma\in {\goth
S}_n$, le mot $x_1\cdots x_n$ est le r\'earrangement croissant
de $x_{\sigma(1)}\cdots x_{\sigma(n)}$, d'o\`u
$$
h_n(x_{\sigma(1)},\ldots,x_{\sigma(n)})
=\prod_{i=1}^n u(x_i,x_{\sigma(i)});
$$
en sommant sur~$\sigma$, on trouve imm\'ediatement (8).\cqfd

\th Lemme 7.4|On suppose que l'on a $n\ge 2$ et $u(x,y)=1$
lorsque $x\ge y$. Pour $x_1$, \dots~, $x_n$ dans~$X$, posons
$$
\leqalignno{
k_n(x_1,\ldots, k_n)&=\prod_{i=1}^{n-1} u(x_i,x_{i+1}).&(9)\cr
\noalign{\hbox{On a alors}}
\sum_{\sigma\in {\goth S}_n}
k_n(x_{\sigma(1)},\ldots, x_{\sigma(n)})
&=\Per (u(x_i,x_j))_{1\le i,j\le n}.&(10)\cr}
$$
\finth

\goodbreak
En raisonnant comme dans le lemme pr\'ec\'edent, on voit qu'il
suffit de prouver l'identit\'e~(10) dans le cas d'une suite
croissante $(x_1,\ldots, x_n)$. Posons alors $a_{ij}=u(x_i,x_j)$
pour $1\le i,j\le n$ d'o\`u $a_{ij}=1$ lorsque $i\ge j$. On est
donc ramen\'e \`a prouver la relation
$$
\sum_{\sigma\in {\goth S}_n}
\prod_{i=1}^{n-1} a_{\sigma(i), \sigma(i+1)}
=\sum_{\sigma\in {\goth S}_n}
\prod_{i=1}^{n-1} a_{i,\sigma(i)}\leqno(11)
$$
(noter que l'on a $n\ge \sigma(n)$ d'o\`u
$a_{n,\sigma(n)}=1$).

Or les r\'earrantements du mot $12\cdots n$ sont les suites
$\sigma(1)\sigma(2)\cdots \sigma(n)$ o\`u $\sigma$ parcourt
${\goth S}_n$. Appliquons le th\'eor\`eme~4.11,~(c) au cas o\`u
$X=\{1,2,\ldots,n\}$, o\`u~$\Omega$ est le mono\"\i de
multiplicatif des nombres complexes et $c(i,j)=a_{ij}$. On en
d\'eduit qu'il existe une bijection~$\Phi:\sigma\mapsto\sigma'$
de~${\goth S}_n$ sur lui-m\^eme telle que
$$
\prod_{i=1}^{n-1}
a_{\sigma(i),\sigma(i+1)}
=\prod_{i=1}^{n-1}
a_{i,\sigma'(i)}\quad(\sigma\in {\goth S}_n).\leqno(12)
$$
Sommant sur~$\sigma$ (ou, ce qui revient au m\^eme,
sur~$\sigma'$), on d\'eduit imm\'ediate\-ment~(11) de~(12).\cqfd

\titrecourant={3. FONCTIONS CARACT\'ERISTIQUES}

\sectiona 3. Fonctions caract\'eristiques de certaines variables
al\'eatoires|
Dans ce n\omini, on note $(\xi_n)_{n\ge 1}$ une suite de
variables al\'eatoires ind\'ependantes de m\^eme loi sur un espace
probabilis\'e $(\Omega,{\goth F},{\rm P})$ ; on note ${\bboard
E}[\tau]$ l'esp\'erance d'une variable al\'eatoire~$\tau$ d\'efinie sur
$(\Omega,{\goth F},{\rm P})$. On rappelle que~$\bboard R$ est
l'ensemble des nombres r\'eels.

\th Lemme 7.5|Soit $u$ une fonction bor\'elienne et born\'ee sur
${\bboard R}^2$, \`a valeurs complexes. Pour tout entier $n\ge
1$, posons
$$
\leqalignno{
a_n&={1\over n!}{\bboard E}[\Per(u(\xi_i,\xi_j))
_{1\le i,j\le n}]\cr
b_n&={\bboard E}[u(\xi_1,\xi_2)\cdots u(\xi_{n-1},\xi_n)
u(\xi_n,\xi_1)].\cr}
$$
Les suites $(a_n)_{n\ge 1}$ et $(b_n)_{n\ge 1}$ satisfont \`a
l'identit\'e de Spitzer.
\finth

Pour tout entier $n\ge 1$ et tout $\sigma\in {\goth S}_n$,
posons
$$
\displaylines{\noalign{\vskip-5pt}
h_n(\sigma)={\bboard E}\Bigl[\prod_{i=1}^n
u(\xi,\xi_{\sigma(i)})\Bigr].\cr
\noalign{\hbox{Il est clair qu'on a}}
\noalign{\vskip-5pt}
a_n={1\over n!}\sum_{\sigma\in {\goth S}_n} h_n(\sigma),
\quad
b_n=h_n(\gamma_n);\cr}
$$
il suffit donc de prouver que les fonctions $h_n$ satisfont aux
hypoth\`eses~(a) et~(b) de la proposition~7.1.

(a) Soient d'abord $\sigma$ et $\tau$ dans~${\goth S}_n$ ;
d\'efinissons une fonction bor\'elienne et born\'ee~$v$ sur
${\bboard R}^n$ par
$$
v(x_1,\ldots, x_n)=\smash{\prod_{i=1}^n} u(x_i,x_{\sigma(i)}).
$$

\goodbreak
\noindent
On a
$$
\leqalignno{\noalign{\vskip-10pt}
v(x_{\tau(1)},\ldots,v_{\tau(n)})
&=\prod_{i=1}^n u(x_{\tau(j)},x_{\tau\sigma(j)})\cr
&=\prod_{i=1}^n u(x_i,x_{\tau\sigma\tau^{-1}(i)})\cr}
$$
(la premi\`ere \'egalit\'e par substitution dans la d\'efinition de~$v$,
la seconde par le changement $j=\tau^{-1}(i))$. On en d\'eduit
$$
\leqalignno{
h_n(\sigma)&={\bboard E}[v(\xi_1,\ldots, \xi_n)]\cr
h_n(\tau\sigma\tau^{-1})&=
{\bboard E}[v(\xi_{\tau(1)},\ldots,
\xi_{\tau(n)})];\cr}
$$
mais le vecteur al\'eatoire $(\xi_1,\ldots,\xi_n)$ est \`a
composantes ind\'ependantes de m\^eme loi et sa loi est
invariante par permutation des coordonn\'ees ; les varia\-bles
al\'eatoires 
$v(\xi_n,\ldots, \xi_n)$ et 
$v(\xi_{\tau(1)},\ldots,
\xi_{\tau(n)})$
ont donc m\^eme esp\'erance. En conclusion, on a 
$h_n(\tau\sigma\tau^{-1})=h_n(\sigma)$.

(b) Soient $\sigma\in {\goth S}_m$ et $\tau\in {\goth S}_n$ ;
posons $\rho=\sigma\oplus\tau$. On a
$$
\leqalignno{
h_{m+n}(\rho)&={\bboard E}\Bigl[\prod_{i=1}^m
u(\xi_i,\xi_{\sigma(i)})
\cdot 
\prod_{j=1}^n u(\xi_{m+j},\xi_{m+\tau(j)})\Bigr]\cr
h_m(\sigma)&={\bboard E}
\Bigl[\prod_{i=1}^mu(\xi_i,\xi_{\sigma(i)})\Bigr]\cr
h_n(\tau)&={\bboard E}
\Bigl[\prod_{j=1}^n u(\xi_j,\xi_{\tau(j)})\Bigr];\cr
}$$
mais les hypoth\`eses faites sur la suite $(\xi_n)_{n\ge 1}$
entra\^\i nent que les vecteurs al\'eatoires $(\xi_1,\ldots, \xi_m)$
et $(\xi_{m+1},\ldots,\xi_{m+n})$ sont ind\'ependants et que le
vecteur al\'eatoire $(\xi_{m_1}, \ldots, \xi_{m+n})$ a m\^eme loi
que $(\xi_1,\ldots, \xi_m)$. La formule
$h_{m+n}(\rho)=h_m(\sigma)\cdot h_n(\tau)$ est alors
imm\'ediate.\cqfd

\medskip
Avant d'\'enoncer les deux th\`eor\`emes fondamentaux de ce chapitre,
nous introduirons quelques notations suppl\'ementaires. On
note~$b$ une fonction bor\'elienne sur ${\bboard R}^2$, \`a
valeurs r\'eelles. Pour tout entier  $n\ge 1$, on note 
$\overline \xi^{(n)}_1$, \dots~, $\overline \xi^{(n)}_n$ le
r\'earrangement croissant de la suite $\xi_1$, \dots~, $\xi_n$
; \footnote{$(^{11})$}{Autrement dit, pour tout $\omega\in
\Omega$, la suite $\overline \xi^{(n)}_1(\omega)$, \dots~,
$\overline \xi^{(n)}_n(\omega)$ est le r\'earrangement croissant
de la suite $\xi_1(\omega)$, \dots~, $\xi_n(\omega)$.}
on pose
$$
\leqalignno{
\eta_n&=\sum_{i=1}^n b(\overline \xi^{(n)}_i,\xi_i)&(13)\cr
\zeta_n&=\sum_{i=1}^{n-1}b(\xi_i,\xi_{i+1})&(14)\cr
\theta_n&=\zeta+b(\xi_n,\xi_1).&(15)\cr}
$$
Enfin, si $\xi$ est une variable al\'eatoire r\'eelle et~$q$ un
nombre r\'eel, on pose
$$
\varphi_\xi(q)={\bboard E}[e^{iq\xi}]\leqno(16)
$$
($\varphi_\xi$ est la fonction caract\'eristique de~$\xi$).

\th Th\'eor\`eme 7.6|Soit $q$ un nombre r\'eel. Pour tout entier
$n\ge 1$, on pose $a_n=\varphi_{\eta_n}(q)$ et
$b_n=\varphi_{\theta_n}(q)$. Alors les suites $(a_n)_{n\ge 1}$
et $(b_n)_{n\ge 1}$ satisfont \`a l'identit\'e de Spitzer.
\finth

\th Th\'eor\`eme 7.7|Supposons que l'on ait $b(x,y)=0$ lorsque
$x\ge y$. Alors les variables al\'eatoires $\eta_n$ et~$\zeta_n$
ont m\^eme loi.
\finth

Posons $u(x,y)=e^{iqb(x,y)}$ ; la fonction $u$ sur ${\bboard
R}^2$ est bor\'elienne et de module~1, donc born\'ee. On
d\'efinit~$h_n$ comme dans le lemme~7.3, d'o\`u
$$
a_n={\bboard E}\Bigl[\prod_{i=1}^n u(\overline
\xi^{(n)}_i,\xi_i)\Bigr] ={\bboard E}[h_n(\xi_1,\ldots,\xi_n)];
$$
comme le vecteur al\'eatoire $(\xi_1,\ldots, \xi_n)$ est
sym\'etrique, on a donc
$$\displaylines{
a_n={1\over n!}\Bigl[\sum_{\sigma\in {\goth S}_n}
h_n(\xi_{\sigma(1)},\ldots,\xi_{\sigma(n)})\Bigr].\cr
\noalign{\hbox{Le lemme 7.3 entra\^\i ne}}
a_n={1\over n!}{\bboard E}[\Per(u(\xi_i,\xi_j))_{1\le i,j\le
n}];\cr
\noalign{\hbox{comme on a \'evidemment}}
b_n={\bboard E}[u(\xi_1,\xi_2)u(\xi_2,\xi_3)\cdots
u(\xi_{n-1},\xi_n)u(\xi_n,\xi_1)],\cr}
$$
le lemme 7.5 montre que les suites $(a_n)_{n\ge 1}$ et
$(b_n)_{n\ge 1}$ satisfont \`a l'identit\'e de Spitzer. Ceci
d\'emontre le th\'eor\`eme~7.6.

Supposons maintenant que l'on ait $b(x,y)=0$ pour $x\ge y$ ;
posons encore $u(x,y)=e^{iqb(x,y)}$, d'o\`u $u(x,y)=1$ pour
$x\ge y$. Enfin posons
$$
a'_n=\varphi_{\zeta_n}(q)={\bboard E}\Bigl[\prod_{i=1}^{n-1}
u(\xi_i,\xi_{i+1})\Bigr].
$$
En raisonnant comme pr\'ec\'edemment, mais en utilisant le lemme
7.4 en place du lemme~7.3, on voit que les suites $(a'_n)_{n\ge
1}$ et $(b_n)_{n\ge 1}$ satisfont \`a l'identit\'e de Spitzer. On a
donc $a'_n=a_n$, c'est-\`a-dire
$\varphi_{\zeta_n}(q)=\varphi_{\eta_n}(q)$ pour tout $n\ge 1$
et tout nombre r\'eel~$q$. Autrement dit, les variables
al\'eatoires~$\zeta_n$ et~$\eta_n$ ont m\^eme fonction
caract\'eristique, donc m\^eme loi. Ceci d\'emontre le
th\'eor\`eme~7.7.\cqfd

\rem Exemple $7.8$|Soit $[c,d]$ un intervalle fini, le cas
particulier $c=d$ n'\'etant pas d\'epourvu d'int\'er\^et. D\'efinissons la
fonction~$b$ sur ${\bboard R}^2$ par
$$
b(x,y)=\cases{1,&si $x<c$ et $y>d$ ;\cr
0,&sinon.\cr}
$$
Il est clair qu'on a $b(x,y)=0$ lorsque $x\ge y$. La
signification des variables $\eta_n$ et $\zeta_n$ est facile \`a
\'elucider dans ce cas :

(a) si $N$ est le nombre al\'eatoire d'indices $i$ tels que $1\le
i\le n$ et $\xi_i<c$, alors $\eta_n$ est le nombre al\'eatoire
d'indices~$j$ tels que $1\le j\le N$ et $\xi_h>d$. Ceci
s'interpr\`ete ais\'ement en termes de m\'ethode d'\'echantillonnage.

(b) $\zeta_n$ est le nombre al\'eatoire d'indice $i$ tels que
$1\le i\le n-1$, $\xi_i<c$ et $\xi_{i+1}>d$ ; on peut
l'appeler le nombre des travers\'ees croissantes de l'intervalle
$[c,d]$.

Ces deux variables al\'eatoires prennent les valeurs 0, 1, 2,
\dots~, $n-1$ ; le th\'eor\`eme~7.7 entra\^\i ne qu'elles ont m\^eme loi.


\vfill
{\eightpoint

\centerline{\bf BIBLIOGRAPHIE}

\bigskip

\article 1|Foata (D.)|\'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|

\livre 2|Hardy (G. H.) et Wright (E. M.)|An Introduction to the
Theory of Numbers|4\emini\ \'edition, Oxford Univ. Press,
{\oldstyle 1960}|

\livre 3|MacMahon (P. A.)|Combinatory Analysis, $1$|Cambridge
Univ. Press, {\oldstyle 1915} (r\'eimpression : Chelsea Publ. Co.,
New York, {\oldstyle 1960})|

\article 4|Rota (G.-C.)|On the Foundations of Combinatorial
Theory I. Theory of M\"obius Functions|Z.
Wahrscheinlichkeitstheorie|2|1964|340--368|

\article 5|Spitzer (F.)|A combinatorial lemma and its
appllication to probability theory|Trans. Amer. Math.
Soc.|82|1956|323--339|


}
\vfill\vfill\eject
\def\intercal{\mathrel{\tau}}



\pagetitretrue

\auteurcourant={{\eightrm 
INDEX DES PRINCIPALES NOTATIONS}}

\titrecourant={{\eightrm 
INDEX DES PRINCIPALES NOTATIONS}}

\vglue 2cm
\centerline{\bf INDEX DES PRINCIPALES NOTATIONS}
\vskip 2mm
\centerline{(Une r\'ef\'erence telle que IV.3 renvoie au n\omini\ 3
du chapitre IV.)}

\vskip 6mm plus 4mm

\halign{\strut$#$\hfil\quad&#\hfil\quad&#\hfil\cr
{\sl Symbole}&\hbox{\sl R\'ef\'erence}&{\sl Signification}\cr
\noalign{\bigskip}
\Mo(Z)&I.1&Mono\"\i de libre construit sur $Z$.\cr
\Ab(Z)&I.1&Mono\"\i de commutatif libre construit sur $Z$.\cr
\epsilon&I.1&Homomorphisme canonique de $\Mo(Z)$ dans
$\Ab(Z)$.\cr 
L(Z;C)&I.2&Mono\"\i de d\'efini par des relations de
commutation.\cr
\pi&I.2&Homomorphisme canonique de $L(Z;C)$ dans $\Ab(Z)$.\cr
\lambda&I.2&Homomorphisme canonique de $\Mo(Z)$ dans
$L(Z;C)$.\cr
\iota&I.2&Involution de $L(Z;C)$.\cr
[z]&I.2&\'El\'ement de $L(Z;C)$ correspondant \`a $z\in Z$.\cr
[F]&I.2&Produit des \'el\'ements $[z]$ pour $z$ parcourant la\cr
&&partie commutative $F$.\cr
\noalign{\medskip}
\mu_M&II.1&Fonction de M\"obius du mono\"\i de $M$.\cr
|F|&II.3&Nombre d'\'el\'ements d'un ensemble fini $F$.\cr
\noalign{\medskip}
\sigma(a)&III.1&Source de l'ar\^ete $a$.\cr
\beta(a)&III.1&But de l'ar\^ete $a$.\cr
N(f)&III.1&Matrice d'incidence du flot $f$.\cr
b(a)&III.2&Flot associ\'e \`a l'ar\^ete $a$.\cr
\sigma(c)&III.5&Source du chemin $c$.\cr
\beta(c)&III.5&But du chemin $c$.\cr
b(c)&III.5&Flot associ\'e au chemin $c$.\cr
\noalign{\medskip}
F(X)&IV.1&Mono\"\i de des flots sur l'ensemble $X$.\cr
Q(X)&IV.1&Mono\"\i de des r\'earrangements construit sur $X$.\cr
\theta&IV.1&Homomorphisme canonique de $F(X)$ dans
$\Ab(X)$.\cr
n_{x,y}(f)&IV.1&Multiciplicit\'e du couple $(x,y)$ dans le flot
$f$.\cr
w\choose w'&IV.1&R\'earrangement d\'efini par les mots $w$ et
$w'$.\cr
n_c&IV.1&Homomorphisme de $F(X)$ dans $\Omega$ associ\'e\cr
&&\`a l'application $c$ de $X\times X$ dans $\Omega$.\cr
\gamma w&IV.2&Mot d\'eduit de $w$ par permutation
circulaire.\cr
[w]&IV.2&Cycle associ\'e \`a un mot $w$ sans lettres r\'ep\'et\'ees.\cr
\overline w&IV.3&R\'earrangement croissant du mot $w$.\cr
Q'(X)&IV.3&Mono\"ide d'intercalement construit sur l'ensemble\cr
&&totalement ordonn\'e $X$.\cr
\noalign{\goodbreak}
\Gamma&IV.3&Isomomorphisme de $Q'(X)$ sur $Q(X)$ d\'efini\cr
&&par $\Gamma(w)={w\choose \overline w}$.\cr
\Pi&IV.3&Isomorphisme r\'eciproque de $\Gamma$.\cr
w\intercal w'&IV.3&Produit d'intercalement des mots $w$ et
$w'$.\cr
\nu_{x,y}(w)&IV.3&Nombre des paires $(\overline x_i,x_i)$
\'egales \`a $(x,y)$\cr
&&o\`u $w=x_1\cdots x_m$ et $\overline w=\overline x_1 \cdots
\overline x_m$.\cr
\nu_c&IV.3&Homomorphisme de $Q'(X)$ dans $\Omega$
associ\'e\cr
&&\`a l'application $c$ de $X\times X$ dans $\Omega$.\cr
\xi_{x,y}(w)&IV.4&Nombre de couples $(x_i,x_{i+1})$ \'egaux \`a\cr
&&$(x,y)$ o\`u $w=x_1\cdots x_m$.\cr
\xi_c(w)&IV.4&Somme $c(x_1,x_2)+\cdots+c(x_{m-1},x_m)$ 
pour\cr
&&$w=x_1\cdots x_m$ et une application\cr
&&$c$ de $X\!\times
\!X$ dans $\Omega$.\cr
Fw&IV.4&Derni\`ere lettre du mot $w$.\cr
\Delta&IV.4&Bijection de $\Mo(X)$ sur $Q(X)$ d\'efinie par\cr
&&$\Delta(w)={\gamma w_1\cdots \gamma w_p\choose
w_1\cdots w_p}$ si $(w_1,\ldots,w_p)$ est\cr
&&la d\'ecomposition
descendante de $w$.\cr 
\Phi&IV.5&Permutation $\Gamma^{-1}\circ \Delta$ de
$\Mo(X)$.\cr
\nu(w)&IV.5&Nombre des indices $i$ avec $\overline x_i<x_i$
o\`u\cr
&&$w=x_1\cdots x_m$ et $\overline w=\overline x_1\cdots
\overline x_m$.\cr
\xi(w)&IV.5&Nombre des indices $i$ tels que $x_i<x_{i+1}$\cr
&&pour le mot $w=x_1\cdots x_m$.\cr
\noalign{\medskip}
\gamma_n&VII.1&Permutation circulaire de $12\cdots n$.\cr
\sigma\oplus\tau&VII.1&Permutation
{\eightpoint
$\petitematrice{\sigma(1)&\cdots&\sigma(m)&m+\tau(1)&\cdots
&m+\tau(n)\cr 1&\cdots&m&m+1&\cdots&m+n\cr}$}.\cr
\Per(a_{i,j})&VII.2&Permanent de la matrice carr\'ee $(a_{ij})$.\cr
(\xi_n)_{n\ge 1}&VII.3&Une suite de variables al\'eatoires
ind\'ependantes\cr
&&et de m\^eme loi.\cr
\smash{\overline\xi^{(n)}_1,\ldots,\overline\xi^{(n)}_n}&VII.3
&R\'earrangement croissant de $\xi_1,\ldots,\xi_n$.\cr
b&VII.3&Fonction bor\'elienne de deux variables r\'eelles.\cr
\gamma_n, \zeta_n, \theta_n&VII.3&Variables al\'eatoires
d\'eduites de $\xi_1,\ldots,\xi_n$ et $n$.\cr }


\bigskip\bigskip
\centerline{\bf Notations g\'en\'erales}
\medskip
\halign{#\hfil&#\hfil\cr
$\bboard Z$ &: ensemble des nombres entiers.\cr
$\bboard R$ &: ensemble des nombres r\'eels.\cr
$\bboard C$ &: ensemble des nombres complexes.\cr
${\goth S}_n$ &: ensemble des permutations de l'ensemble
$\{1,2,\ldots,n\}$.\cr}


\vfill\eject

\pagetitretrue
\auteurcourant={DOMINIQUE FOATA}
\titrecourant={INVERSIONS DE M\"OBIUS}

\vglue 1cm

\centerline{{\bf INVERSIONS DE
M\"OBIUS \footnote{$(^1)$}{The  present text was written
on the occasion of the {\it Science Research Council
Rencontre}, Aberdeen, July 6--12 1975 and had never been
published since.}}} 

\medskip
\centerline{\sl Dominique Foata}
\vskip 6mm minus 2mm
La formule d'inversion de M\"obius, comme le soulignait
fort justement le professeur Temperley lors de la Rencontre
d'Aberdeen (6-12 juillet 1975), n'est en fait qu'une
sublimation du principe d'inclusion-exclusion. Chacun sait
bien que le plus difficile dans les applications est de {\it
calculer} la fonction de M\"obius sous-jacente et \`a
l'exception de quelques cas simples, ce calcul ne d\'erive pas
des principes, mais reste une affaire d'ing\'eniosit\'e et
d'exp\'erience.

La formule   d'inversion, de fa\c con habituelle (\cf., par
exemple, Rota (1964)),  est pr\'esent\'ee dans le cadre des {\it
ensembles ordonn\'es localement finis} (``locally finite
partially ordered sets"). Dans Cartier-Foata (1969,
chap.~2), on trouve une d\'efinition de fonction de M\"obius
des {\it mono\"\i des \`a factorisation finie}. Le but de
cette note est de montrer la connexion entre ces deux
pr\'esentations.

En aucun cas, je ne veux faire ici \oe uvre originale : mon
but est simplement de montrer qu'il n'y a qu'une ``th\'eorie"
de l'inversion de M\"obius. Le cadre choisi pour pr\'esenter
la formule d'inversion est au fond accessoire et ne peut
\^etre qu'une structure alg\'ebrique rudimentaire. En fait, la
proposition~1 ci-dessous doit \^etre attribu\'ee \`a Rota (1972)
et la proposition~2 \`a Sch\"utzenberger (1974) dans des
communications priv\'ees avec l'auteur.


\sectiona 1. Ensembles ordonn\'es|
La construction de la fonction de M\"obius pour les
ensembles ordonn\'es est tr\`es clairement expos\'ee dans Rota
(1964). Soit~$P$ un ensemble ordonn\'e  localement fini,
c'est-\`a-dire que si $x\le y$, il n'y a qu'un nombre {\it
fini} de $z\in P$ tels que $x\le z\le y$. On forme
l'ensemble
$R(P\times P)$ des fonctions r\'eelles de deux variables~$x$
et~$y$, o\`u~$x$ et~$y$ sont dans~$P$, ayant les
propri\'et\'es suivantes :
\decale{(i)}|$f(x,y)=0$ si $x\not\le y$;
\decale{(ii)}|$f(x,x)$ est, pour tout $x\in P$, une constante
qui ne d\'epend que de~$f$.\footnote{$(^2)$}{La restriction
(ii) n'est en g\'en\'eral pas impos\'ee. Elle est ici mentionn\'ee
par commodit\'e. On se persuadera que les fonction~$\xi_P$
et $\mu_P$ d\'efinies ci-apr\`es appartiennent bien \`a
$R(P\times P)$.}

\noindent
L'ensemble $R(P\times P)$ est muni d'une structure
d'alg\`ebre associative sur le corps des r\'eels -- on
l'appellera d\'esormais l'{\it alg\`ebre d'incidence} de~$P$
-- en prenant  pour somme $f+g$ et produit $fg$ de
deux \'el\'ements~$f$, $g$ de $R(P\times P)$, les fonctions
d\'efinies par
$$
\eqalignno{\noalign{\vskip-5pt}
(f+g)(x,y)&=f(x,y)+g(x,y);\cr
(fg)(x,y)&=\sum_{x\le z\le y} f(x,z)g(z,y);\cr}
$$

\goodbreak
\noindent pour tout $x,y$ dans $P$. L'alg\`ebre $R(P\times
P)$ a un \'el\'ement unit\'e~$\delta$ (la fonction de
Kronecker). On distingue enfin une application~$\xi_P$
d\'efinie par
$$
\xi_P(x,y)=\cases{1,&si $x\le y$ ;\cr
0,&autrement.\cr}
$$
La fonction de M\"obius $\mu_P$ de $P$ n'est autre que
l'inverse (on d\'emontre qu'il existe!) de~$\xi_P$ dans
$A(P\times P)$. Autrement dit, $\mu_P$ est la fonction
satisfaisant~\`a
$$
\xi_P\,\mu_P=\mu_P\,\xi_P=\delta.
$$

\sectiona 2. Mono\"\i des \`a factorisation finie|
Soit maintenant $M$ un mono\"\i de, c'est-\`a-dire un
ensemble muni d'une op\'eration associative (qu'on notera
multiplicativement), admettant un \'el\'e\-ment unit\'e (qu'on
notera~1). Le mono\"\i de~$M$ peut ou non contenir un
\'el\'ement z\'ero, not\'e~0, tel que $0\cdot x=x\cdot 0=0$ pour
tout~$x$ dans~$M$. On note~$M^+$ l'ensemble des
\'el\'ements non nuls de~$M$.

On appelle {\it d\'ecomposition} d'un \'el\'ement~$x$ de~$M$
toute suite finie $s=(x_1,\ldots,x_q)$ d'\'el\'ements de~$M$,
diff\'erents de~0 et de~1, telle que $x=x_1\cdots x_q$.
L'entier~$q$ s'appelle le {\it degr\'e} de la
d\'ecomposition~$s$. On admet, par convention, une
d\'ecomposition vide de~1, de degr\'e~0. On dit que le
mono\"\i de~$M$ est \`a {\it factorisation finie}, si tout
\'el\'ement de~$M^+$ n'admet qu'un nombre fini de
d\'ecompositions.

Soit $R(M)$ l'ensemble des fonctions r\'eelles sur $M^+$. On
munit  $R(M)$ d'une structure d'alg\`ebre associative en
posant
$$
\eqalignno{(f+g)(x)&=f(x)+g(x);\cr
(fg)(x)&=\sum_{x_1x_2=x}f(x_1)g(x_2).\cr}
$$
Dans la seconde r\`egle ci-dessus, la sommation est \'etendue
\`a tous les couples $(x_1,x_2)$ tels que $x_1x_2=x$, en
particulier, aux couples $(1,x)$ et $(x,1)$. On dira encore
que $R(M)$ est l'{\it alg\`ebre d'incidence} de~$M$. De
m\^eme, on distingue deux \'el\'ements $\xi_M$ et
$\epsilon_M$ dans $R(M)$, d\'efinis par $\xi_m(x)=1$ pour
tout~$x$ dans~$M^+$ et $\epsilon_M(x)=1$ ou~0 suivant
que $x=1$ ou $x\not=0,1$.

\sectiona 3. Formules d'inversion|
La formule d'inversion de M\"obius dans le cas des
ensembles ordonn\'es est la suivante : soient~$f$ et~$g$
deux fonctions r\'eelles d'{\it une} variable~$x$ courant
dans un ensemble ordonn\'e~$P$ et~$p$ un \'el\'ement de~$P$.
Alors les relations suivantes sont \'equivalentes :
$$
\eqalignno{g(x)&=\sum_{p\le y\le x}f(y),&\hbox{pour tout
$x$ dans $P$ ;}\cr
f(x)&=\sum_{p\le y\le x}g(y)\mu_P(y,x),&\hbox{pour tout
$x$ dans $P$.}\cr}
$$

Dans le cas des mono\"\i des \`a factorisation finie, la
formule d'inversion de M\"obius est une identit\'e dans
l'alg\`ebre d'incidence $R(M)$ du mono\"\i de~$M$
(\cf. Cartier-Foata (1969), p.~20). Soient~$f$ et~$g$
deux fonctions r\'eelles sur~$M^+$. On a l'\'equivalence entre
les deux formules
$$
\eqalignno{g(x)&=\sum_{x_1x_2=x}f(x_2),&\hbox{pour tout
$x$ dans $M^+$ ;}\cr
f(x)&=\sum_{x_1x_2=x}\mu_M(x_1)g(x_2),&\hbox{pour tout
$x$ dans $M^+$.}\cr
}$$

Un dernier rapprochement entre~$\mu_P$ et $\mu_M$.
Dans le cas des ensembles ordonn\'es, on
d\'etermine~$\mu_P$ par r\'ecurrence au moyen des formules
$\mu_P(x,x)=1$ et
$$
\mu_P(x,y)=-\sum_{x\le z\le y,\,z\not=y}\mu_P(x,z),
$$
en utilisant le fait qu'il n'y a qu'un ensemble fini de $z$
tels que $x\le z\le y$.

Dans le cas des mono\"\i des, la fonction de M\"obius
$\mu_M$ est donn\'ee en chaque point~$x$ par l'argument
suivant. Pour tout~$x$ dans~$M^+$ on note $d_+(x)$
(resp. $d_-(x)$) le nombre de d\'ecompositions de $x$ de
degr\'e pair (resp. impair). Alors
$$
\mu_M(x)=d_+(x)-d_-(x)
$$ pour tout $x$ dans $M$.

\sectiona4. Alg\`ebres d'incidence des mono\"\i des|
Voyons maintenant comment le calcul de toute fonction de
M\"obius d'un ensemble ordonn\'e peut \^etre ramen\'e au calcul
d'une fonction de M\"obius d'un mono\"\i de \`a
factorisation finie.

\th Proposition 1|Soit $R(P\times P)$ l'alg\`ebre d'incidence
d'un ensemble ordonn\'e localement fini~$P$. Alors il existe
un mono\"\i de \`a factorisation finie~$M$ tel que son
alg\`ebre d'incidence $R(M)$ soit isomorphie \`a $R(P\times
P)$.
\finth

\dem
Soit $J$ l'ensemble des couples $(x,y)$ d'\'el\'ements de~$P$
tels que $x\le y$ et $x\not=y$. Soient encore deux
\'el\'ements que nous noterons~0 et~1 n'appartenant pas
\`a~$P$. On munit l'ensemble $M=\{0,1\}\cup J$ d'une
structure de mono\"\i de en posant
$$
\eqalign{0\cdot m&=m\cdot 0=0,\ \qquad\hbox{pour
tout
$m$ dans $M$;}\cr
1\cdot m&=m\cdot 1=m,\qquad\hbox{pour tout $m$
dans $M^+=M\setminus\{0\}$;}\cr}\leqno(*)
$$
et pour $(x,y)$ , $(z,t)$ dans $J$
$$
(x,y)\cdot(z,t)=\cases{(x,t),&si $y=z$ ;\cr
0,&sinon.\cr}\leqno(**)
$$
La multiplication ainsi d\'efinie est \'evidemment
associative. Si $(x,y)$ est dans~$J$, il n'admet qu'un
nombre fini de d\'ecompositions, puisque le segment
$[x,y]=\{z\in P:x\le z\le y\}$ est fini. Le mono\"\i
de~$M$ est donc \`a factorisation finie.

\goodbreak
Soit maintenant $f\in R(P\times P)$. On d\'efinit la
fonction r\'eelle~$f_M$ sur $M^+$ par les relations
$$\leqalignno{
f_M(1)&=f(x,x),\qquad\hbox{pour un \'el\'ement~$x$
quelconque de~$P$;}&{\rm (i)}\cr
f_M(x,y)&=f(x,y),\qquad\hbox{pour $x<y$.}&{\rm (ii)}\cr}
$$
Montrons que l'application $f\mapsto f_M$ est un
isomorphisme de $R(P\times P)$ sur $R(M)$. Le caract\`ere
bijectif de $f\mapsto f_M$ est \'evident d'apr\`es les
relations~(i) et (ii) et la relation $(f+g)_M=f_M+g_M$ est
triviale. Reste \`a v\'erifier : $(fg)_M=f_Mg_M$. Or, pour
$x<y$, on a
$$
\eqalignno{
(fg)_M(x,y)&=\sum_{x\le z\le y}f(x,z)g(z,y)\cr
&=\sum_{x< z< y} f(x,z)g(z,y)+f(x,x)g(x,y)+f(x,y)g(y,y)\cr
&=\sum
f_M(x_1,y_1)g_M(x_2,y_2)+f_M(1)g_M(x,y)+f_M(x,y)g_M(1),\cr}
$$
o\`u la sommation est \'etendue \`a l'ensemble des paires de
couples $(x_1,y_1)$, $(x_2,y_2)$ tels que $(x_1,y_1)\cdot
(x_2,y_2)=(x,y)$. D'o\`u
$$
\eqalignno{
(fg)_M&=(f_Mg_M)(x,y).\cr
\noalign{\hbox{Enfin, pour tout $x$ dans $P$,}}
(fg)_M(1)&=(fg)(x,x)\cr
&=f(x,x)g(x,x)=f_M(1)g_M(1)\cr
&=(f_Mg_M)(1).\qed\cr}
$$

\th Corollaire|Soit $M$ le mono\"\i de associ\'e \`a l'ensemble
ordonn\'e~$P$ par les relations $(*)$ et $(**)$. On a alors
$$
\mu_P(x,y)=\mu_M(x,y)
$$
pour tout couple $(x,y)$ tel que $x\le y$.
\finth

En effet, $\mu_M$ est l'image de $\mu_P$ par
l'isomomorphisme $f\mapsto f_M$.


\sectiona 5. Alg\`ebres d'incidence des ensembles ordonn\'es|
R\'eciproquement, on peut ramener le calcul de la fonction
de M\"obius d'un mono\"\i de \`a factorisation finie~$M$ \`a
celui de la fonction de M\"obius d'un ensemble
ordonn\'e~$P$. Il y a cependant une restriction \`a imposer
sur le mono\"\i de~$M$. On dit qu'un mono\"\i de~$M$ est
{\it simplifiable} (\`a droite) si pour~$x, u, v$ dans~$M$
avec $x\not=0$ on a :
$[xu=xv]\Rightarrow [u=v]$.
Supposons~$M$ simplifiable. Si $u$, $x$, $y$ sont
dans~$M$ et si $y=xu$, l'\'el\'ement~$u$ est d\'efini de fa\c con
unique. On peut donc poser
$$
u=y/x\quad{\rm et\ ainsi\quad }y=x\,(y/x).
$$
Compte tenu de cette restriction, on a le r\'esultat suivant.

\goodbreak
\th Proposition 2|Soit $R(M)$ l'alg\`ebre d'incidence d'un
mono\"\i de \`a factoorisation finie et simplifiable. Alors il
existe un ensemble ordonn\'e localement fini~$P$ tel que
son alg\`ebre d'incidence $R(P\times P)$ soit isomorphe
\`a~$R(M)$.
\finth

\dem
L'ensemble ordonn\'e $P$ qu'on va associer \`a~$M$ est la
paire $(M,\le)$, o\`u ``$\le $" est l'ordre d\'efini par
$$
x\le y\quad\hbox{si $y=xu$ pour un certain $u$ dans
$M$.}
$$
On d\'efinit de cette fa\c con un ordre sur~$M$, car si $y=xu$
et $y=zv$, on a $z=xuv$ ; d'o\`u $x\le y$ et $y\le z$
entra\^\i nent $x\le y$. De plus, cet ordre est localement fini,
car si l'on a $x\le y\le z$, on a aussi $z=yv$ pour un
certain~$v$, o\`u encore $(y,v)$ est une d\'ecomposition de
degr\'e~2 de~$z$. Comme il n'y a qu'un nombre fini de
d\'ecompositions de~$z$, il n'y a donc qu'un nombre fini
d'\'el\'ements~$y$ satisfaisant \`a $x\le y\le z$. Comme on a
suppos\'e~$M$ {\it simplifiable}, il existe un et un seul
\'el\'ement not\'e $y/x$ tel que $y=x(y/x)$ lorsque $x\le y$.

Soit $f$ une fonction appartenant \`a $R(M)$. On pose alors
pour $x,y$ dans~$M$
$$
f_P(x,y)=\cases{f(y/x),&si $x\le y$ ;\cr
0,&sinon.\cr}
$$
Comme pr\'ec\'edemment on peut v\'erifier que $f\mapsto f_P$
est bijectif et lin\'eaire. Soient~$f$ et~$g$ deux \'el\'ements
de $R(M)$. On a pour $x\le y$
$$
\leqalignno{
(fg)_P(x,y)&=(fg)(y/x)=\sum_{u_1u_2=y/x}f(u_1)g(u_2)\cr
&=\sum_{x\le y\le z}f(z/x)g(y/z)\cr
&=\sum_{x\le y\le z} f_P(x,z)g_P(z,y)=(f_Pg_P)(x,y).\qed\cr}
$$
La fonction de M\"obius $\mu_P$ de l'ensemble $P=(M,\le)$
est alors donn\'ee par
$$
\mu_P(x,y)=\mu_M(y/x),\quad{\rm lorsque}\ x\le y.
$$


\medskip
\centerline{\bf Bibliographie}
\medskip
{\eightpoint

\smallskip\noindent
Pierre Cartier, Dominique Foata (1969)\pointir {\sl
Probl\`emes combinatoires de commutation et
r\'earrangements}\pointir Lecture Notes in Math., no.~{\bf
85}, Springer-Verlag, Berlin.

\smallskip\noindent
Gian-Carlo Rota (1964)\pointir On the Foundations of
Combinatorial Theory~I. Theory of M\"obius Inversion, {\sl
Z. Wahrscheinlichkeitstheorie}, {\bf 2}, p.~340--368.

\smallskip\noindent
Gian-Carlo Rota (1972)\pointir Communication priv\'ee.

\smallskip\noindent
Marcel-Paul Sch\"utzenberger (1974)\pointir
Communication priv\'ee.


\bigskip
\line{\hbox{Retyped with \TeX,
December 10, 2005.}\hfil\vbox{\halign{#\hfil\cr Institut
Lothaire\cr 1, rue Murner\cr
67000 Strasbourg, France\cr}}\hskip.5cm}

}

\vfill\eject

\leavevmode
\auteurcourant={}

\vfill\eject


\pagetitretrue
\auteurcourant={BODO LASS}
\titrecourant={LE POLYNOME CHROMATIQUE}

\vglue 1cm
\centerline{\bf LE POLYN\^OME CHROMATIQUE}

\bigskip
\centerline{Bodo LASS}
\bigskip

{\eightpoint

\centerline{\vbox{\halign{\hfil #\hfil\cr
Institut Camille Jordan ({\sixrm UMR} 5208 du {\sixrm CNRS})\cr
Universit\'e Claude Bernard -- Lyon 1\cr
B\^atiment Doyen Jean Braconnier (101)\cr
43, Boulevard du 11 Novembre 1918\cr
F-69622 Villeurbanne Cedex \cr
\noalign{\medskip} 
Courriel : {\tt lass@math.univ-lyon1.fr}\cr}}}

}
\bigskip

Regardons la toute premi\`ere identit\'e dans Cartier-Foata ([1], p.~1,
formule~(1)) (ou bien le th\'eor\`eme~2.4, p.~13) et associons un graphe
(simple) $G = (V,E)$ \`a cette identit\'e~: chaque sommet $v \in V$ correspond
\`a une variable $T_v$ et chaque ar\^ete $\{u,v\} \in E$ correspond, de fa\c
con bijective, \`a deux variables $T_u, T_v$ qui ne commutent pas. Par
cons\'equent, les mon\^omes form\'es de lettres distinctes commutant deux \`a
deux correspondent aux ensembles de sommets qui ne contiennent aucune
ar\^ete~:  on les appelle {\sl ind\'ependants}.

Imposons maintenant les relations suppl\'ementaires $T_v^2 = 0$ pour tout $v
\in V$ ainsi que $T_uT_v = T_vT_u$ pour toute ar\`ete $\{u,v\} \in E$ (pour
travailler avec l'alg\`ebre commutative des fonctions d'ensembles ${\bb
Z}[T_v]/\langle T_v^2 \rangle$, $v \in V$).  L'identit\'e~(1) devient alors
$$
\Bigl[ 1 + \sum_{\scriptstyle \emptyset \subset I \subseteq V, \atop
\scriptstyle I \;
\hbox{\sevenrm ind\'ependant} \;\; } (-1)^{|I|} \prod_{v \in I} T_v
\Bigr]^{-1}\; = \; 1 + \sum_{\emptyset \subset V' \subseteq V} a(G[V'])
\prod_{v \in V'} T_v, 
$$
o\`u $a(G[V'])$ est le nombre d'orientations acycliques du graphe $G[V']$ qui
contient toutes les ar\^etes ayant leurs deux extr\'emit\'es dans $V' \subseteq
V$. En effet, les mon\^omes distincts form\'es des lettres non-commutatives 
$T_v$, $v \in V'$, correspondaient aux orientations acycliques du graphe $G[V']$.

On appelle une coloration des sommets de~$G$ {\sl r\'eguli\`ere} si et seulement si les deux extr\'emit\'es de chaque ar\^ete
obtiennent des couleurs diff\'erentes. Notons $\chi_G(\lambda)$ le nombre de ces colorations avec $\lambda$ couleurs. 
Puisque $\chi_G(\lambda)$ compte les partitions de~$V$ en $\lambda$ ensembles ind\'ependants, nous avons l'identit\'e 
(voir Tutte [3])
$$\eqalignno{
1 + \sum_{\emptyset \subset V' \subseteq V} \chi_{G[V']}(\lambda) 
\prod_{v \in V'} T_v &=
\Bigl[ 1 + \sum_{\scriptstyle \emptyset \subset I \subseteq V, \atop
\scriptstyle I \;
\hbox{\sevenrm ind\'ependant}}
\prod_{v \in I} T_v \Bigr]^{\lambda}\hfill\cr
\cr
&=1 + \sum_{k=1}^{|V|} {\lambda \choose k} 
     \Bigl[ \sum_{\scriptstyle \emptyset \subset I \subseteq V, \atop
\scriptstyle I \;
\hbox{\sevenrm ind\'ependant}}
\prod_{v \in I} T_v \Bigr]^{k},\cr}
$$
puisque $k > |V|$ implique 
$\bigl[ \sum_{\emptyset \subset I \subseteq V, \;\; I \; 
\hbox{\sevenrm ind\'ependant} \;\; } \prod_{v \in I} T_v \bigr]^{k} = 0$
dans l'alg\`ebre commutative des fonctions d'ensembles ${\bb Z}[T_v]/\langle
T_v^2 \rangle$, $v \in V$.  En particulier, $\chi_G(\lambda)$ est un
polyn\^ome~: le {\sl polyn\^ome chromatique}.

En rempla\c cant chaque variable $T_v$ par $-T_v$ nous voyons donc que
l'identit\'e~(1) (ou bien le th\'eor\`eme~2.4) est une g\'en\'eralisation
non-commu\-ta\-tive de l'identit\'e  $(-1)^{|V|}\chi_G(-1) = a(G)$ (voir
Stanley [4]).

Une autre g\'en\'eralisation peut \^etre obtenue en associant \`a chaque
ar\^ete $\{u,v\}$ l'hyperplan $x_u = x_v$ dans l'espace ${\bb R}^{|V|}$. Les
orientations acycliques de~$G$ corres\-pondent alors aux r\'egions de cet
arrangement d'hyperplans. En fait, la formule 
$(-1)^{|V|}\chi_G(-1) = a(G)$ se g\'en\'eralise non 
seulement aux arrangements d'hyper\-plans (voir Winder [4]) mais encore
aux matro\"\i des orient\'es. 

\bigskip\bigskip\bigskip

{\eightpoint
\centerline{BIBLIOGRAPHIE}
\bigskip
\livre 1|Pierre Cartier, Dominique Foata|Probl\`emes combinatoires de
commutation et r\'ear\-ran\-gements|Lecture Notes in Math.~{\bf 85},
Springer-Verlag, Berlin, {\oldstyle 1969}; electronically reedited {\oldstyle
2006}|

\article 2|R.~P.~Stanley|Acyclic orientations of graphs|Discrete
Math.|5|1973|171-178|

\article 3|W.~T.~Tutte|On dichromatic polynomials|J.~Combin.
Theory|2|1967|301-320|

\article 4|R.~O.~Winder| Partitions of $N$-space by hyperplanes|SIAM
J.~Appl. Math.|14|1966|811-818|

}



\bye