\catcode'32=9
\magnification=1200

% particularite du pilote canon

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

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

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

% Chargement des fontes AMS

\font\tengoth=eufm10
\font\tenbboard=msbm10
\font\eightgoth=eufm7 at 8pt
\font\eightbboard=msbm8
\font\sevengoth=eufm7
\font\sevenbboard=msbm7
\font\sixgoth=eufm6
\font\fivegoth=eufm5

\newfam\gothfam
\newfam\bboardfam

\catcode`\@=11

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

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

\let\bb=\bboard

\tenpoint

%���������������������� dactylographie fran�aise �����������������

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

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

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

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

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

\frenchspacing

%���������������������� format de sortie �����������������

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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

\def\virg{\raise 2pt\hbox{,}}   % virgule apr�s une fraction

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

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

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

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

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

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

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

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

% ���������������������  syst�me d'�quations  ���������������������
% copi\'e sur \eqalign, on s'en sert comme une matrice
% syntaxe : signe & coef & inconnue
% les coef sont justifi\'es \`a droite (\hfil coef)
% et les inconnues \`a gauche (inconnue\hfil)
% attention : double && avant le signe =
% pour justification correcte !
% Exemple : $$\system{
%             &2 &x &- &3 & y & = &&       -5 \cr
%            -&  &x &+ &  & y & = && \hfill 6 \cr
%           }$$

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

\def\pv{\kern 2pt\string;\ }

\def\\#1{{\cal#1}}


\catcode`\@=12


\def\Lig{\mathop{\rm Ligne}\nolimits}
\def\Ilig{\mathop{\rm Iligne}\nolimits}
\def\Colig{\mathop{\rm Coligne}\nolimits}
\def\Icolig{\mathop{\rm Icoligne}\nolimits}
\def\des{\mathop{\rm des}\nolimits}
\def\maj{\mathop{\rm maj}\nolimits}
\def\codes{\mathop{\rm codes}\nolimits}
\def\comaj{\mathop{\rm comaj}\nolimits}
\def\ides{\mathop{\rm ides}\nolimits}
\def\imaj{\mathop{\rm imaj}\nolimits}
\def\icodes{\mathop{\rm icodes}\nolimits}
\def\icomaj{\mathop{\rm icomaj}\nolimits}
\def\ig{\hbox{\bf i}} 
\def\rg{\hbox{\bf r}} 
\def\cg{\hbox{\bf c}} 
\def\R{\mathop{\rm R{}}}
\def\Bij{\mathop{\rm Bij}}
\def\Inv{\hbox{Inv}\nolimits}
\def\Fix{\mathop{\rm Fix}\nolimits}
\def\Trans{\mathop{\rm Trans}\nolimits}
\def\U{\mathord{\mkern 2mu\overline{\mkern -2mu U\mkern -1mu}\mkern 1mu}}
\def\T{\mathord{\mkern 2mu\overline{\mkern -2mu T}}}



\let\findem=\cqfd

\auteurcourant={D. FOATA}
\titrecourant={PERMUTATIONS COLOR\'EES ET TABLEAUX GAUCHES}
\vglue 2cm

\centerline{{\bf PERMUTATIONS COLOR\'EES ET TABLEAUX GAUCHES}}
\vskip 10pt
\centerline{\sevenrm PAR}
\vskip 10pt
\centerline{{\petcap Dominique} FOATA}
 
\bigskip
\resume{Une correspondance est propos\'ee entre 
permutations color\'ees et tableaux gauches permettant
le calcul de certaines statistiques sur les
permutations \`a partir de l'alg\`ebre des fonctions
de Schur.}

\section 1. Introduction|L'alg\`ebre des fonctions de Schur a \'et\'e utilis\'ee dans
[Desfo1] et [Desfo2] pour le calcul des distributions
de statistiques classiques sur le groupe sym\'e\-tri\-que.
Plus r\'ecemment, \pd REMMEL [Rem3] a pu prolonger ce calcul
\`a l'aide des {\it fonctions de Schur $(k,l)$-crochets}.
Il a introduit le concept fort utile de bipermutation
et calcul\'e les fonctions g\'en\'eratrices correspondantes.
Comme il est expos\'e dans [Fo2], on peut reprendre toute l'approche de
\pd REMMEL et la prolonger \`a une classe
plus importante de permutations dites $(k,l)$-color\'ees.
La th\'eorie combinatoire des fonctions de Schur $(k,l)$-crochets,
telle qu'elle est expos\'ee dans
[Bereg, Berem, Rem1, Rem3] et habilement utilis\'ee par
\pd REMMEL [Rem3],
n'est alors plus indispensable, on peut
simplement s'appuyer sur l'alg\`ebre des fonctions
de Schur usuelles. L'outil de transfert fondamental est
alors une correspondance entre tableaux gauches
d'une forme bien particuli\`ere et des triplets
form\'es par une permutation et deux partitions
ordonn\'ees. 

L'objet de cet article est de 
d\'ecrire cette correspondance. A titre
d'illus\-tra\-tion, un calcul de fonctions
g\'en\'eratrices pour les permutations
$(3,2)$-color\'ees est reproduit \`a la fin.
On se reportera \`a [Fo2] pour un expos\'e
exhaustif, r\'ealis\'e dans le cadre
des fonctions hyperg\'eom\'etriques \`a plusieurs bases.

L'\'etude des statistiques d'ordre sur le
groupe sym\'e\-tri\-que remonte \`a \pd MACMAHON [Mac1, 2, 3, 4],
qui a introduit les notions de {\it nombre de descentes} 
(``$\des$'') et
d'{\it indice majeur} (``$\maj$'') pour une suite finie de nombres
et calcul\'e les premi\`eres s\'eries g\'en\'eratrices.
Le polyn\^ome g\'en\'erateur du groupe des
permutations par nombre de descentes
est le {\it polyn\^ome eul\'erien} (\cf. [Fosch1]).
Le~polyn\^ome \hbox{$q$-eul\'erien}
est le polyn\^ome g\'en\'erateur pour le couple $(\des,\maj)$
(\cf.~[Car1,~2,~3]). Avec la statistique {\it nombre des inversions},
on obtient un autre polyn\^ome $q$-eul\'erien (\cf. [St2, Ro, Fo1]).
Un pas d\'ecisif a \'et\'e fait par \pd GARSIA et \pd GESSEL [Gage] 
(voir aussi [Ra1]) lorsqu'ils ont 
trouv\'e la bonne normalisation des s\'eries de facult\'e
\`a consid\'erer. Il fallait prendre des produits de deux $q$-factorielles
montantes. Pour chaque permutation $\sigma $
on peut, en plus, introduire le nombre de descentes
et l'indice majeur de l'inverse $\sigma ^{-1}$,
not\'es $\ides \sigma $ et $\imaj \sigma $.
La distribution du 4-vecteur
$(\des,\ides,\maj,\imaj)$
est alors calculable (\cf. [Gage, Ra1])
ainsi que son groupe de sym\'etrie (\cf. [Fosch2]).
D'autres r\'esultats parall\`eles ont \'et\'e obtenus
par diff\'erents auteurs
(\cf. [Car4, Chemo, St1, Ge, Ra2]).

C'est, en fait, l'\'etude approfondie de l'alg\`ebre combinatoire
des tableaux r\'ealis\'ee par \pc SCH\"UTZENBERGER|
[Sch1, 2, Lasch1, 2, 3, 4]
qui a permis une insertion compl\`ete du calcul des
statistiques d'ordre sur le groupe des permutations
dans l'alg\`ebre des fonctions sym\'e\-tri\-ques.
Il devenait enfin
possible d'utiliser toute la richesse de
cette derni\`ere alg\`ebre et de puiser les
ingr\'edients indispensables dans les ouvrages classiques 
[St1, Macd, Jake, Wy].
La tr\`es c\'el\`ebre correspondance de Robinson-Schensted
(\cf. [Knu, p.~48--72])
\'etait le passage oblig\'e 
entre le calcul des distributions de statistiques
d'ordre et celui des fonctions sym\'e\-tri\-ques.

Le pr\'esent article montre que ladite correspondance
reste encore ce passage oblig\'e lorsqu'on
veut prolonger ce calcul de distributions
\`a des classes plus importantes
d'objets combinatoires, comme les
permutations $(k,l)$-color\'ees
dont il est question ci-apr\`es.

\section 2. Permutations $(k,l)$-color\'ees|Quand $\sigma $ est une permutation de l'intervalle
$[\,n\,]$, la {\it ligne de route} $\Lig \sigma $,
la {\it ligne inverse de route} $\Ilig \sigma $,
la {\it coligne de route} $\Colig \sigma $ et
la {\it coligne inverse de route} $\Icolig \sigma $
sont habituellement d\'efinies (\cf. [Foulk], [FoSch2])
par
$$\eqalign{
\Lig \sigma    &=\Bigl\{ r:1\leq r\leq n-1,\,\sigma (r)>\sigma(r+1)\Bigr\}               \pv\cr 
\Ilig \sigma   &=\Lig \sigma ^{-1}\pv \quad\Colig \sigma =[\,n-1\,]\setminus \Lig \sigma \pv\cr
\Icolig \sigma &=[\,n-1\,]\setminus \Ilig \sigma \;(=\Colig \sigma ^{-1})                \pv\cr
}$$
o\`u $\sigma ^{-1}$
d\'esigne l'inverse de $\sigma $.
Le cardinal de $\Lig \sigma $ et la somme des \'el\'ements de $\Lig \sigma $
sont respectivement appel\'es {\it nombre
de descentes} et {\it indice majeur} de~$\sigma $.
Il y a des d\'efinitions analogues pour les autres lignes de route.

On peut prolonger la d\'efinition de ces lignes de route
aux permutations $(k,l)$-color\'ees. On d\'esigne par l\`a
des triplets $\tau =(\sigma ,{\bf a,b})$, o\`u $\sigma $ est une permutation de l'intervalle
$[\,n\,]$ et o\`u ${\bf a}=(a_1,\ldots,a_k)$ et ${\bf b}=(b_1,\ldots,b_l)$
sont des suites de $k$ et $l$ entiers positifs, respectivement,
de somme $n$.
L'{\it inverse} d'une permutation $(k,l)$-color\'ee
$\tau =(\sigma ,{\bf a,b})$ est d\'efinie comme la permutation $(l,k)$-color\'ee
$\tau ^{-1}=(\sigma ^{-1},{\bf b,a})$.
Il est commode de poser
$a_0=b_0=0$ et de noter ${\bf a}_i$ et ${\bf b}_j$
les {\it sommes partielles} ${\bf a}_i=a_1+\cdots+a_i$
$(0\leq i\leq k)$ et ${\bf b}_i=b_1+\cdots+b_j$
$(0\leq j\leq l)$.

Les partitions {\bf a} et {\bf b} d\'eterminent des sous-intervalles
de $[\,n\,]$ dans lesquels les diff\'erentes lignes de route
peuvent aussi \^etre d\'efinies. Pour chaque $i=1,\ldots,k$ 
et $j=1,\ldots,l$ on pose :
$$\eqalign{
\Lig_i \tau &=\Bigl\{ r:{\bf a}_{i-1}+1\leq r\leq {\bf a}_i-1,\,
\sigma (r)>\sigma (r+1)\Bigr\} \pv\cr
\Colig_i \tau &=[{\bf a}_{i-1}+1,{\bf a}_i-1]\setminus \Lig_i \tau \pv\quad
\Ilig_j \tau =\Lig_j \tau ^{-1}\pv\cr
\Icolig_j \tau &=\Colig_j \tau ^{-1}
=[{\bf b}_{j-1}+1,{\bf b}_j-1]\setminus \Ilig_j \tau .\cr
}$$
Par cons\'equent :
  $$\Ilig_j\tau =\Bigl\{ s:{\bf b}_{j-1}+1\leq s\leq {\bf b}_j-1,\,
\sigma ^{-1}(s)>\sigma ^{-1}(s+1)\Bigr\}\cdotp$$

\rem Remarque $2.1$|
Notons que si $\sigma ({\bf a}_i)>\sigma ({\bf a}_i+1)$,
l'entier ${\bf a}_i$ appartient \`a $\Lig \sigma $, mais n'apporte aucune
contribution \`a $\Lig_i \sigma $ ; on a donc simplement l'inclusion
$\sum _i\Lig_i \tau  \subset \Lig \sigma $.
Notons aussi que $\Lig_i \tau $ peut aussi \^etre
d\'efinie comme l'ensemble de tous les entiers $r$
tels que ${\bf a}_{i-1}+1\leq r\leq {\bf a}_i-1$ ayant la propri\'et\'e que
  $$(r+1)\ \hbox{est \`a la gauche de } r
\hbox{ dans le mot } \sigma ^{-1}(1)\cdots \sigma ^{-1}(n).\leqno(2.1)$$

\rem Notation $2.2$|
Consid\'erons une bijection $\sigma $ d'un sous-ensemble
$\{ r_1<r_2<\cdots<r_n\} $
de $\bboard  N$ sur un sous-ensemble $J$ de $\bboard  N$. Par convention,
$\sigma $ d\'esigne \`a la fois la bijection elle-m\^eme
et le {\it mot} $\sigma (r_1)\sigma (r_2)\cdots \sigma (r_n)$.

\rem D\'efinition $2.3$|
La {\it ligne inverse de route}
peut \^etre prolong\'ee au cas des {\it mots}
$\sigma =\sigma (r_1)\sigma (r_2)\cdots \sigma (r_n)$ ayant des lettres
{\it diff\'erentes}
en d\'esignant \'egalement par $\Ilig \sigma $ l'ensemble
de tous les entiers $s$ tels que
$s$ et $(s+1)$ sont des lettres de $\sigma $, l'entier $(s+1)$
\'etant \`a la gauche de
$s$ dans le mot $\sigma =\sigma (r_1)\sigma (r_2)\cdots \sigma (r_n)$.

Lorsque $\{ r_1<r_2<\cdots<r_n\} =J=[\,n\,]$, {\it i.e.},
quand $\sigma $ est une permutation de $[\,n\,]$, on v\'erifie imm\'ediatement
que la ligne inverse de route qui vient d'\^etre d\'efinie
co\"{\i}ncide avec la d\'efinition donn\'ee au d\'ebut de ce paragraphe.

\medskip

Soient $\tau _{1,j},\ldots,\tau _{k,j}$ des bijections d'ensembles finis
sur des sous-ensembles {\it disjoints} $J_{1,j},\ldots,J_{k,j}$
de {\bf N}. Pour chaque $i=1,\ldots,k$ soit
$\Ilig(\leftarrow \tau _{i,j})$ l'ensemble et tous les entiers $r$
tels que $r$ est une lettre de $\tau _{i,j}$ et
$(r+1)$ est une lettre de $\tau _{i',j}$ pour un certain
$i'<i$. Alors, la ligne inverse de route
du produit de juxtaposition
$\tau _{1,j}\cdots \tau _{k,j}$ est \'egale \`a :
  $$\Ilig \tau _{1,j}\cdots \tau _{k,j}=
\sum _i \Ilig \tau _{i,j} +\sum _i \Ilig(\leftarrow \tau _{i,j}).\leqno(2.2)$$




\section 3. Une premi\`ere bijection|Soit $\tau =(\sigma ,{\bf a,b})$ 
une permutation $(k,l)$-color\'ee.
Pour chaque couple $(i,j)$ tel que $1\leq i\leq k$ et
$1\leq j\leq l$ notons $I_{ij}$ l'ensemble de tous les entiers de
l'intervalle $[\,{\bf a}_{i-1}+1,{\bf a}_i\,]$
qui sont envoy\'es par $\sigma $ dans
$[\,{\bf b}_{j-1}+1,{\bf b}_j\,]$. En d'autres termes,
$r$ appartient \`a $I_{ij}$ si et seulement si les deux relations
${\bf a}_{i-1}+1\leq r\leq {\bf a}_i$ 
et ${\bf b}_{j-1}+1\leq \sigma (r)\leq {\bf b}_j$ sont satisfaites.
Posons $J_{ij}=\sigma (I_{ij})$ et notons $\tau _{ij}$
la restriction de $\sigma $ \`a $I_{ij}$.
Il est clair que $\tau _{ij}$ est une bijection de
$I_{ij}$ sur $J_{ij}$ ; notons $\tau ^{-1}_{ij}$
la bijection inverse envoyant $J_{ij}$ sur $I_{ij}$.
On a :
  $$\eqalign{\sum _{1\leq j\leq l} I_{ij}&
=[\,{\bf a}_{i-1}+1,{\bf a}_i\,]\qquad (1\leq i\leq k),\cr
\sum _{1\leq i\leq k} J_{ij}&
=[\,{\bf b}_{j-1}+1,{\bf b}_j\,]\qquad (1\leq j\leq l),\cr}\leqno(3.1)$$
de sorte que la r\'eunion des valeurs prises par 
$\tau ^{-1}_{i1}$,
$\tau ^{-1}_{i2}$,~\dots,
$\tau ^{-1}_{il}$
(resp. $\tau _{1j}$,
$\tau _{2j}$,~\dots,
$\tau _{kj}$)
n'est autre que l'intervalle $[\,{\bf a}_{i-1}+1,{\bf a}_i\,]$
(resp. $[\,{\bf b}_{j-1}+1,{\bf b}_j\,]$).
Par cons\'equent, le produit de juxtaposition
$\tau ^{-1}_i=\tau ^{-1}_{i1} \tau ^{-1}_{i2}\cdots \tau ^{-1}_{il}$
des {\it mots} (\cf. {\it notation}~2.1) $\tau ^{-1}_{i1}$,
$\tau ^{-1}_{i2}$,\dots,
$\tau ^{-1}_{il}$
et le produit de juxtaposition
$\tau _j=\tau _{1j} \tau _{2j}\cdots \tau _{kj}$
des mots
$\tau _{1j}$,
$\tau _{2j}$,\dots,
$\tau _{kj}$ sont des r\'earrangements de
$({\bf a}_{i-1}+1)({\bf a}_{i-1}+2)\cdots {\bf a}_i$
et $({\bf b}_{j-1}+1)({\bf b}_{j-1}+2)\cdots {\bf b}_j$,
respectivement. On peut donc parler des 
lignes inverses de route de $\tau ^{-1}_i$
et $\tau _j$, suivant la {\it d\'efinition}~2.3.

\goodbreak
\th Proposition 3.1|On a :
  $$\Lig_i \tau =\Ilig \tau ^{-1}_i\,,\quad
\Ilig_j \tau =\Ilig \tau _j\,,\leqno(3.2)$$
pour tout $i=1,\ldots,k$ et tout $j=1,\ldots,l$.\finth
  
\goodbreak
\dem Comme not\'e dans (2.1), $\Lig_i \tau $ est aussi l'ensemble de tous les
$r$ tels que ${\bf a}_{i-1}+1\leq r\leq {\bf a}_i-1$ et tels que
$(r+1)$ soit \`a la gauche de $r$ dans
$\sigma ^{-1}(1)\cdots \sigma ^{-1}(n)$. Or, d'apr\`es la {\it d\'efinition}~2.3,
ceci est pr\'ecis\'ement la ligne inverse de route
du mot~$\tau ^{-1}$.

La m\^eme observation s'applique \`a
$\Ilig_j \tau $ et $\Ilig \tau _j$.\findem

Ainsi, l'application $\tau \mapsto  (\tau _{ij})$ est une bijection de
l'ensemble de toutes les permutations $(k,l)$-color\'ees
$\tau =(\sigma ,{\bf c,d})$ telles que  ${\bf c=a}$ et ${\bf d=b}$
sur l'ensemble des $k\times l$ bijections 
$(\tau _{ij}:I_{ij}\rightarrow J_{ij})$ satisfaisant (3.1).
De plus, la \pc PROPOSITION|~3.1 est v\'erifi\'ee.

\medskip

Pour mieux suivre les diff\'erentes \'etapes de la construction,
il semble utile de donner l'exemple suivant qui sera trait\'e
tout au long de l'article.

\rem $3.2.$ Exemple|
Soient $n=12$, $(k,l)=(3,2)$,
${\bf a}=(5,4,3)$, ${\bf b}=(7,5)$ et
$\tau =(\sigma ,{\bf a,b})$ 
la permutation $(k,l)$-color\'ee d'ordre~$n$ 
  $$\sigma =\left(\vcenter{\halign{&$\;$\hfil#\hfil$\;$\cr
{\bf 1}&2&3&{\bf 4}&5\cr
6&1&4&10&5\cr}}\right|
\left.\vcenter{\halign{&$\;$\hfil#\hfil$\;$\cr
6&{\bf 7}&{\bf 8}&9\cr
2&11&9&8\cr}}\right|
\left.\vcenter{\halign{&$\;$\hfil#\hfil$\;$\cr
10&{\bf 11}&12\cr
3&12&7\cr}}\right).$$
(Les \'el\'ements de $\Ilig_i \sigma $ $(i=1,2,3)$
sont reproduits en gras.)
La permutation $\sigma ^{-1}$ s'\'ecrit :
  $$\sigma ^{-1}=\left(\vcenter{\halign{&$\;$\hfil#\hfil$\;$\cr
1&2&{\bf 3}&4&{\bf 5}&6&7\cr
2&6&10&3&5&1&12\cr}}\right|
\left.\vcenter{\halign{&$\;$\hfil#\hfil$\;$\cr
{\bf 8}&{\bf 9}&10&11&12\cr
9&8&4&7&11\cr}}\right)$$
(les \'el\'ements de $\Lig_j \sigma ^{-1}$ $(j=1,2)$
sont \'egalement reproduits en gras). Quant aux
bijections $\tau _{ij}$ $(1\leq i\leq k=3,\,1\leq j\leq l=2)$, 
elles sont \'egales~\`a :
$$\eqalign{
\tau _{11}&=\left(\vcenter{\halign{&$\;$\hfil#\hfil$\;$\cr
                          1&2&3&5\cr
                          6&1&4&5\cr}}\right);\cr 
tau _{22}&=\left(\vcenter{\halign{&$\;$\hfil#\hfil$\;$\cr
                          7&8&9\cr
                          11&9&8\cr}}\right);\cr}
\quad\eqalign{
\tau _{12}&=\left(\vcenter{\halign{&$\;$\hfil#\hfil$\;$\cr
                          4\cr
                          10\cr}}\right);\cr
\tau _{21}&=\left(\vcenter{\halign{&$\;$\hfil#\hfil$\;$\cr
                          6\cr
                          2\cr}}\right);\cr}
\quad\eqalign{
\tau _{31}&=\left(\vcenter{\halign{&$\;$\hfil#\hfil$\;$\cr
                          10&12\cr
                          3&7\cr}}\right);\cr     
\tau _{32}&=\left(\vcenter{\halign{&$\;$\hfil#\hfil$\;$\cr
                          11\cr
                          12\cr}}\right);\cr
}$$
et les mots $\tau _i$ et $\tau ^{-1}_j$ \`a :
 $$\displaylines{
\tau _1 =6,1,4,{\bf 5},2,{\bf 3},7\pv \qquad
\tau _2 =10,11,{\bf 9},{\bf 8},12 \pv\cr
\tau _1^{-1}=2,3,5,{\bf 1},{\bf 4}\pv \qquad
\tau _2^{-1}=6,9,{\bf 8},{\bf 7}\pv \qquad
\tau _3^{-1}=10,12,{\bf 11}\pv\cr
}$$
et l'on a : 
$$\displaylines{
\Lig_1\tau =\Ilig \tau _1^{-1}=\{ {\bf 1,4}\} ,\quad
\Lig_2\tau =\Ilig \tau _2^{-1}=\{ {\bf 7,8}\} ,\hfill\cr
\Lig_3 \tau =\Ilig \tau _3^{-1}=\{ {\bf 11}\} ,\ 
\Ilig_1\tau =\Lig_1\tau ^{-1}=\Ilig \tau _1=\{ {\bf 3,5}\} ,\hfill\cr
\Ilig_2\tau =\Lig_2\tau ^{-1}=\Ilig \tau _2=\{ {\bf 8,9}\} .\hfill\cr
}$$


\section 4. La seconde bijection|Comme d'habitude, on d\'esigne par {\it partition} 
tout suite finie d\'ecroissante
$\nu =(\nu _1,\nu _2,\ldots,\nu _p)$ d'entiers
au moins \'egaux \`a~1.
Si la somme $\nu _1+\nu _2+\cdots+\nu _p$ 
est \'egale \`a $n$, alors $\nu $ 
est dite {\it partition de} $n$  et l'on \'ecrit
$\left|\nu \right|=n$. Le {\it diagramme de Ferrers}
associ\'e \`a $\nu $ est l'ensemble de tous les couples
$(i,j)$ du plan euclidien satisfaisant
$1\leq i\leq \nu _j$ et
$1\leq j\leq p$. On identifie
le diagramme de Ferrers \`a la partition elle-m\^eme.

Soient
$\nu =(\nu _1,\nu _2,\ldots,\nu _p)$ et
$\theta =(\theta _1,\theta _2,\ldots,\theta _r)$
deux diagrammes de Ferrers. 
Si $\nu \supset \theta $, la diff\'erence d'ensemble
$\nu \setminus \theta $, 
not\'ee $\nu /\theta $, est appel\'ee
{\it diagramme gauche}. 
On note $(\nu /\theta )'$ le {\it conjugu\'e} (ou
le {\it transpos\'e}) de $\nu /\theta $, obtenu en
faisant pivoter le diagramme gauche autour
de sa diagonale principale.
Si $\lambda /\mu $ est un autre diagramme gauche tel que
$\lambda =(\lambda _1,\ldots,\lambda _s)$, $\mu =(\mu _1,\ldots,\mu _t)$ et 
$\lambda \supset \mu $, le {\it produit} $(\nu /\theta )\otimes (\lambda /\mu )$
est d\'efini comme l'ensemble de tous les \'el\'ements
de ${\goth N}^2$,
qui sont ou bien de la forme
$(i,s+j)$ avec $(i,j)\in  (\nu /\theta )$,
ou bien de la forme $(\nu _1+i,j)$ avec
$(i,j)\in  (\lambda /\mu )$.

Le produit de $l$ diagrammes de Ferrers
$\lambda _{i,1},\ldots,\lambda _{i,l}$
est not\'e
$\lambda _{i,1}\otimes \cdots\otimes \lambda _{i,l}$,
ou simplement $\otimes _{j=1}^{j=l} \lambda _{i,j}$,
ou encore $\otimes _j \lambda _{i,j}$.

Par exemple, soient $\lambda _{1,1}=(3,1)$, $\lambda _{2,1}=(1)$
et $\lambda _{3,1}=(2)$ trois diagrammes de Ferrers.
Leur produit $\lambda _{1,1}\otimes \lambda _{2,1}\otimes \lambda _{3,1}$ est le diagramme gauche
de la forme :
  $$\vbox{\halign{&$\hfil#\hfil\;$\cr
\times &\cr
\times &\times &\times &\cr
\null&\null&\null&\times &\cr
\null&\null&\null&\null&\times &\times\cr}}$$

Soient $I$ un sous-ensemble fini de ${\goth N}$ de cardinal~$n$
et $\nu /\theta $ un diagramme gauche de $n$ points.
En \'ecrivant les $n$ entiers de $I$ sur les $n$ 
points du diagramme $\nu /\theta $ de fa\c con \`a obtenir
une croissance dans les lignes (de gauche \`a droite)
et dans les colonnes (de bas en haut). La configuration 
$T$ obtenue est appel\'ee {\it tableau injectif}
de {\it contenu} $I$ {\it et de forme} $\nu /\theta $.
Il est commode d'\'ecrire 
${\rm Cont}\,T=I$ et $\left|T\right|=\nu /\theta $.
Lorsque $I=[\,n\,]$, on remplace ``de contenu $I$''
par ``d'ordre~$n$''.

La {\it ligne inverse de route} d'un tableau injectif $T$
de contenu $I$ et de forme $\nu / \theta $ est d\'efinie comme
l'ensemble de tous les entiers $k$ tels que
$k$ et $(k+1)$ appartiennent \`a $I$, l'entier
$(k+1)$ \'etant \'ecrit {\it plus haut} que $k$ dans~$T$.
On note $\Ilig T$ la ligne inverse de route de $T$.
Lorsque $T$ est d'ordre~$n$, on d\'efinit aussi sa
{\it coligne inverse de route} par  $\Icolig T=[n-1]\setminus \Ilig T$.

Par ailleurs, le {\it transpos\'e} d'un tableau gauche
$T$ est le tableau $T'$ obtenu en faisant pivoter $T$ autour
de sa diagonale.
En d'autres termes, l'entier $m$ se trouve sur le point
$(i,j)$ dans $T'$, lorsque $m$ est sur
$(j,i)$ dans $T$. Si $\left|T\right|=\nu /\theta $,
alors $\left|T'\right|=(\nu /\theta )'=(\nu '/\theta ')$.
Par exemple, si $\left|T\right|=\lambda _{i,1}\otimes \cdots\otimes \lambda _{i,l}$,
alors $\left|T'\right|=\lambda _{i,l}'\otimes \cdots\otimes \lambda _{i,1}'$.
Si, de plus, $T$ est d'ordre~$n$, son transpos\'e
$T'$ est aussi d'ordre~$n$ et
  $$\Icolig T'=\Ilig T.\leqno(4.1)$$
\smallskip

\noindent 
Par exemple, les tableaux
$P_{1,1}=\vbox{\halign{&$\hfil#\hfil\;$\cr
                             6\cr
                             1&4&5\cr}}$ ;
$P_{2,1}=2$ ;
$P_{3,1}=3\;7$
sont tous injectifs, de forme $\lambda _{1,1}=(3,1)$, 
$\lambda _{2,1}=(1)$ et $\lambda _{3,1}=(2)$
respectivement. Ils sont aussi de contenu diff\'erent.
Par ailleurs, les deux tableaux
  $$T_1=\vcenter{\halign{&$\hfil#\hfil\ $\cr
                         6\cr
                         1&4&{\bf 5}\cr
                         \null&\null&\null&2\cr
                         \null&\null&\null&\null&{\bf 3}&7\cr}}\qquad
T_1'=\vcenter{\halign{&$\hfil#\hfil\ $\cr
                         7\cr
                         3\cr        
                         &{\bf 2}\cr
                         &&5\cr
                         &&{\bf 4}\cr
                         &&{\bf 1}&{\bf 6}\cr}}$$
sont injectifs {\it d'ordre} 7 et de forme
$\left|T_1\right|=\lambda _{1,1}\otimes \lambda _{2,1}\otimes \lambda _{3,1}$
et $\left|T'_1\right|=\lambda '_{3,1}\otimes \lambda '_{2,1}\otimes \lambda '_{1,1}$
respectivement. On a aussi $\Ilig T_1=\{ {\bf 3,5}\} $ 
et $\Icolig T_1=\Ilig T'_1=\{ {\bf 1,2,4,6}\} $.
Ils sont obtenus \`a partir des tableaux pr\'ec\'edents
de fa\c con \'evidente, de sorte que la notation 
  $$T_1=P_{1,1}\otimes P_{2,1}\otimes P_{3,1},\qquad
T'_1=P'_{3,1}\otimes P'_{2,1}\otimes P'_{1,1}$$
est claire.

Venons-en au principal th\'eor\`eme de cet article.

\th 4.1. Th\'eor\`eme|A toute permutation $(k,l)$-color\'ee
$\tau =(\sigma ,{\bf c,d})$ telle que ${\bf c=a}$ et ${\bf d=b}$ correspond
de fa\c con biunivoque :

$(i)$ une famille $(\lambda _{ij})$ $(1\leq i\leq k\,;\ 1\leq j\leq l)$ de diagrammes de Ferrers
tels que pour tout $i=1,\ldots,k$ et $j=1,\ldots,l$
on ait les relations :
  $$\left|\lambda _{i,1}\right|+\cdots+\left|\lambda _{i,l}\right|=a_i,
\qquad\left|\lambda _{1,j}\right|+\cdots+\left|\lambda _{k,j}\right|=b_j,$$

$(ii)$ une suite
$({\bf T,U})=(T_1,\ldots,T_l,U_1,\ldots,U_k)$
de $(k+l)$ tableaux gauches injectifs,
d'ordres $b_1,\ldots,b_l$, $a_1,\ldots,a_k$
et de forme
$\left|T_j\right|=\lambda _{1,j}\otimes \cdots\otimes \lambda _{k,j}$,
$\left|U_i\right|=\lambda _{i,1}\otimes \cdots\otimes \lambda _{i,l}$,
ayant la propri\'et\'e :
  $$\Ilig_j \tau -{\bf b}_{j-1}=\Ilig T_j,
\quad \Lig_i \tau -{\bf a}_{i-1}=\Ilig U_i\leqno(4.2)$$
pour tout $j=1,\ldots,l$ et $i=1,\ldots,k$.\finth

L'outil de base pour d\'emontrer ce th\'eor\`eme est
la correspondance de Robinson-Schensted
(\cf., par exemple, [Knu, p.~48--72] pour
un excellent expos\'e de la question),
correspondance qu'il faut prolonger \`a l'ensemble
des tableaux gauches.
Soit $\Bij(I,J)$ l'ensemble de toutes les bijections
d'un ensemble fini $I$ sur un ensemble $J$. La
correspondance de Robinson-Schensted
$\rho $ envoie bijectivement $\Bij(I,J)$
sur l'ensemble de tous les couples $(P,Q)$
de tableaux injectifs, de m\^eme forme $\lambda $,
le contenu de $P$ (resp. $Q$) \'etant $J$
(resp. $I$). Soient $\sigma \in  \Bij(I,J)$ et $\rho (\sigma )=(P,Q)$. 
Alors $\rho $
a la propri\'et\'e suppl\'ementaire suivante :
  $$\Ilig \sigma =\Ilig P\qquad{\rm et}\qquad\Ilig \sigma ^{-1}=\Ilig Q.$$

La correspondance de Robinson-Schensted 
envoie donc chacune des bijections
$\tau _{i,j}:I_{i,j}\rightarrow J_{i,j}$ sur un couple
$(P_{i,j},Q_{i,j})$ de tableaux injectifs de la
m\^eme forme, dont les contenus et les lignes
inverses de routes sont donn\'es par 
  $$\displaylines{
{\rm Cont}\,P_{i,j}    = J_{i,j},\qquad
{\rm Cont}\,Q_{i,j}    = I_{i,j},\cr
\Ilig \tau _{i,j}      = \Ilig P_{i,j},\quad
\Ilig \tau _{i,j}^{-1} = \Ilig Q_{i,j}.\cr
}$$
Soit $\lambda _{i,j}$ la forme commune de $P_{i,j}$ et $Q_{i,j}$.
Les tableaux gauches $\T_j=P_{1,j}\otimes \cdots \otimes P_{k,j}$
et $\U_i=Q_{i,1}\otimes \cdots \otimes Q_{i,l}$
sont alors de forme
$\lambda _{1,j}\otimes \cdots\otimes \lambda _{k,j}$
et $\lambda _{i,1}\otimes \cdots\otimes \lambda _{i,l}$,
respectivement. De plus,
  $${\rm Cont}\,\T_j
=\sum _i J_{i,j}=[{\bf b}_{j-1}+1,{\bf b}_j],\quad
{\rm Cont}\,\U_i=\sum _j I_{i,j}=[{\bf a}_{i-1}+1,{\bf a}_i]$$
et donc
$\left|\lambda _{1,j}\right|+\cdots+\left|\lambda _{k,j}\right|=b_j,\enspace
\left|\lambda _{i,1}\right|+\cdots+\left|\lambda _{i,l}\right|=a_i$.
Pour chaque $i=1,\ldots,k$ soit $\Ilig(\leftarrow P_{i,j})$ l'ensemble
de tous les entiers $s$ dans $[{\bf b}_{j-1}+1,{\bf b}_j-1]$
tels que $s$ soit dans $P_{i,j}$ et tels que $(s+1)$ apparaisse
dans $P_{i',j}$ pour un certain $i'<i$. Alors
  $$\eqalign{\Ilig \T_j&=\Ilig P_{1,j}\otimes \cdots \otimes P_{k,j}
=\sum _i \Ilig P_{i,j} + \sum _i \Ilig(\leftarrow P_{i,j})\cr
&=\sum _i \Ilig \tau _{i,j} + \sum _i \Ilig(\leftarrow \tau _{i,j})\cr
&=\Ilig \tau _{1,j}\cdots \tau _{k,j}=\Ilig \tau _j=\Ilig_j \tau .\cr}$$
De la m\^eme mani\`ere, $\Ilig \U_i=\Lig_i \tau $.

\goodbreak

On obtient enfin la suite
$({\bf T,U})=(T_1,\ldots,T_l,U_1,\ldots,U_k)$
en partant de la suite
$(\T_1,\ldots,\T_l,
\U_1,\ldots,\U_k)$ et en
rempla\c cant chaque \'el\'ement $r$ du tableau $\T_j$
(resp. $\U_i$) par l'\'el\'ement
$r-{\bf b}_{j-1}$ (resp. $r-{\bf a}_{i-1}$). Les
tableaux qui en r\'esultent sont alors d'ordre 
$b_1,\ldots,b_l,a_1,\ldots,a_k$. Les relations
(4.2) sont alors v\'erifi\'ees.

Ceci ach\`eve la d\'emonstration du th\'eor\`eme 4.1.

\medskip

Illustrons la construction du pr\'ec\'edent th\'eor\`eme \`a l'aide
de l'exemple du~\S \kern 2pt 3. Les diff\'erents
\'el\'ements $\tau _{ij}$ sont envoy\'es sur les couples de
tableaux :
  $$\displaylines{\tau _{11}\mapsto  (P_{1,1},Q_{1,1})
=\raise 8pt \hbox{$\left(\vcenter{\halign{&$\hfil#\hfil\;$\cr
                        6\cr
                        1&4&5\cr}}\right.$},\;
\raise 8pt \hbox{$\left.\vcenter{\halign{&$\hfil#\hfil\;$\cr
                 2\cr
                 1&3&5\cr}}\right)$};\quad
\tau _{1,2}\mapsto  (P_{1,2},Q_{1,2})=(10,\,4)\;;\cr
\noalign{\medskip}
\tau _{2,1}\mapsto  (P_{2,1},Q_{2,1})=(2,\,6)\;;\quad
\tau _{2,2}\mapsto  (P_{2,2},Q_{2,2})=
\raise 16pt \hbox{$\left(\vcenter{\halign{\hfil#\hfil\cr
                                                 11\cr
                                                 9\cr
                                                 8\cr}}\right.$},\;
\raise 16pt \hbox{$\left.\vcenter{\halign{\hfil#\hfil\cr
                     9\cr
                     8\cr
                     7\cr}}\right)$};\cr
\noalign{\vskip 2pt }
\tau _{3,1}\mapsto  (P_{31},Q_{3,1})=(3\;7\,,\;10\;12)\quad
\tau _{3,2}\mapsto  (P_{3,2},Q_{32})=(12,\,11).\cr}$$

\goodbreak

\noindent
D'o\`u l'on a :
$$\displaylines{  
T_1=\vcenter{\halign{&$\hfil#\hfil\;$\cr
                         6\cr
                         1&4&{\bf 5}\cr
                         &&&2\cr
                         &&&&{\bf 3}&7\cr}};\qquad
T_2=\vcenter{\halign{&$\hfil#\hfil\;$\cr
                         3\cr
                         &4\cr
                         &{\bf 2}\cr
                         &{\bf 1}\cr
                         &&5\cr}};\cr
\noalign{\medskip}
U_1=\vcenter{\halign{&$\hfil#\hfil\;$\cr
                         2\cr
                         {\bf 1}&3&5\cr
                         &&&{\bf 4}\cr}};\qquad
U_2=\vcenter{\halign{&$\hfil#\hfil\;$\cr
                         1\cr
                         &4\cr
                         &{\bf 3}\cr
                         &{\bf 2}\cr}};\qquad
U_3=\vcenter{\halign{&$\hfil#\hfil\;$\cr
                         1&3\cr
                         &&{\bf 2}\cr}}.\cr}$$


\section 5. Application|Le th\'eor\`eme combinatoire pr\'ec\'edent
permet de calculer les fonctions
g\'en\'e\-ra\-trices des permutations
$(k,l)$-color\'ees pour diff\'erentes statistiques.

Rappelons tout d'abord quelques notations
usuelles, comme la factorielle $q$-montante :
  $$\eqalignno{(a;q)_n&=\cases{1&si $n=0$,\cr
                               \noalign{\smallskip}
                               (1-a)(1-aq)\,
                               \ldots\,
                               (1-aq^{n-1})&si $n\geq 1$ ;\cr}\cr
\noalign{\smallskip}
               (a;q)_{\infty }&=\lim\nolimits_n(a;q)_n=
{\textstyle \prod _{n\geq 0}(1-aq^n)},\cr}$$
et une notation analogue dans le cas de
deux bases $q_1$, $q_2$ :
  $$\displaylines{(u;q_1,q_2)_{r,s}=\cases{1&si $r$ ou $s$ est nul,\cr
                                           \noalign{\smallskip}
                                          \prod _{1\leq i\leq r} \prod _{1\leq
j\leq s}  (1-uq_1^{i-1}q_2^{j-1})& si $r,s\geq 1$ ;\cr}\cr
\noalign{\smallskip}
(u;q_1,q_2)_{\infty ,\infty }
=\lim\nolimits_{r,s}(u;q_1,q_2)_{r,s}
={\textstyle \prod _{i\geq 1}\prod _{j\geq 1}}
(1-uq_1^{i-1}q_2^{j-1}).\cr}$$

Pour ne pas surcharger les notations, consid\'erons
le cas particulier $k=3$, $l=2$ (correspondant
aux donn\'ees de l'exemple trait\'e ci-dessus) et 
introduisons les indices majeurs attach\'es \`a
une permutation $(3,2)$-color\'ee $\tau =(\sigma ,{\bf a,b})$ comme
\'etant les nombres :
  $$\eqalign{
\maj_i \tau     &=\sum \bigl\{ r-{\bf a}_{i-1}:r\in  \Lig_i \tau
\bigr\} , \qquad (i=1,2)\pv\cr
\comaj_3 \tau   &=\sum \bigl\{ r-{\bf a}_2:r\in  \Colig_3 \tau \bigr\}\pv\cr
\imaj_1 \tau    &=\sum \bigl\{ r-{\bf a}_0:r\in  \Ilig_1 \tau \bigr\}\pv\cr
\icomaj_2 \tau  &=\sum \bigl\{ r-{\bf a}_1:r\in  \Icolig_2 \tau \bigr\}.\cr
}$$
Formons ensuite le mon\^ome 
  $$h(\tau )=p_1^{\maj_1\tau }
p_2^{\maj_2\tau }
p_3^{\comaj_3\tau }
q_1^{\imaj_1\tau }
q_2^{\icomaj_2\tau }$$

\goodbreak

\noindent
puis, pour tout couple $({\bf a,b})$, notons
$P({\bf a,b})$ le polyn\^ome
$P({\bf a,b})=\sum h(\tau )$, o\`u la sommation est \'etendue \`a
toutes les permutations $(3,2)$-color\'ee
$\tau =(\sigma ,{\bf c,d})$ telles que ${\bf c=a}$ et ${\bf d=b}$.

On peut alors montrer (\cf. [Fo2]) que la fonction
g\'en\'eratrice des polyn\^omes $P({\bf a,b})$ est donn\'ee par :
  $$\displaylines{\quad\sum _n u^n \sum _{{\bf a,b}} 
{A_1^{a_1} A_2^{a_2} A_3^{a_3}
B_1^{b_1} B_2^{b_2}
\over 
(p_1;p_1)_{a_1}
(p_2;p_2)_{a_2}
(p_3;p_3)_{a_3}
(q_1;q_1)_{b_1}
(q_2;q_2)_{b_2}}
P({\bf a,b})
\hfill\cr
\hfill{}={(-uA_1B_2;p_1,q_2)_{\infty ,\infty }
(-uA_2B_2;p_2,q_2)_{\infty ,\infty }
(-uA_3B_1;p_3,q_1)_{\infty ,\infty }
\over (uA_1B_1;p_1,q_1)_{\infty ,\infty }
(uA_2B_1;p_2,q_1)_{\infty ,\infty }
(uA_3B_2;p_3,q_2)_{\infty ,\infty }}\raise2pt\hbox{,}\quad\cr}$$
o\`u la seconde sommation est \'etendue \`a toutes
les partitions ordonn\'ees ${\bf a}=(a_1,a_2,a_3)$
et ${\bf b}=(b_1,b_2)$ satisfaisant
$a_1+a_2+a_3=b_1+b_2=n$.

Il existe toute une famille de ces identit\'es
que l'on obtient \`a partir du th\'eor\`eme combinatoire
pr\'ec\'edent et de l'alg\`ebre des fonctions de Schur. Notons
qu'une formule comme la pr\'ec\'edente appara\^{\i}t 
comme une formule de transformation d'un rapport
de produits infinis, o\`u les bases interviennent
{\it par paires}, en une somme o\`u le d\'enominateur
de normalisation ne contient que des
factorielles montantes {\it \`a une seule base}.

Une telle identit\'e se sp\'ecialise \'evidemment en
{\it l'identit\'e $q$-binomiale} : 
  $$\sum _n (z;q)_n{u^n\over  (q;q)_n}
={(zu;q)_\infty \over  (u;q)_\infty }\cdotp$$
Posons, en effet,
$A_1=B_1=1$, $A_2=B_2=0$, $A_3=-z$,
$p_1=p_2=p_3=q_2=0$ et $q_1=q$.
On obtient :
  $$\sum _n u^n \sum _{{\bf a,b}}
{(-z)^{a_3}
\over (q;q)_{b_1}}
P({\bf a,b})
={(uz;q)_\infty \over (u;q)_\infty }\cdotp$$
Les seules paires {\bf a}, {\bf b} qui apportent
une contribution non nulle \`a la seconde sommation se r\'eduisent 
aux partitions $a_1+a_3=n$ et $b_1=n$. Par ailleurs, $P({\bf a,b})$ 
est une sommation sur les seules
permutations $(3,2)$-color\'ees $\tau =(\sigma ,{\bf a,b})$
telles que $\maj_1 \tau =\comaj_3 \tau =0$.
De l\`a, $\sigma $ est de la forme 
  $$\sigma =r_1<r_2<\cdots<r_{a_1}\pv\enspace
s_1>s_2>\cdots>s_{a_3}.\leqno(5.1)$$
Enfin, le mon\^ome $h(\tau )$ se r\'eduit \`a $q^{\imaj_1 \tau }$.
On a donc
  $$\sum _{{\bf a,b}}z^{a_3}
P({\bf a,b})=\sum (-z)^{a_3}q^{\imaj_1 \tau },$$
o\`u la derni\`ere sommation est sur les seules permutations
$\tau =(\sigma ,{\bf a,b})$ avec $\sigma $ de la forme (5.1). Il est imm\'ediat de voir,
par exemple par r\'ecurrence sur $n$, que la pr\'ec\'edente somme vaut
$(-z;q)_n$. On retrouve donc bien 
la formule $q$-binomiale.

\hfuzz=7pt
\vskip 1cm
\goodbreak
 
\centerline{BIBLIOGRAPHIE} 
\penalty 10000 \vskip .5cm\noindent 

%\livre And|{\pc ANDREWS| (George E.)}|The Theory of
%Partitions|Reading, Mass., Ad\-di\-son-Wesley,
%{\oldstyle 1976} ({\sl Encyclopedia of Math. and Its 
%Appl.}, {\bf 2})| 
%\livre Bai|{\pc BAILEY| (W.N.)}|Generalized Hypergeometric 
%Series|Cambridge University Press, {\oldstyle 1935}|
\divers Bereg|{\pc BERELE|} (A.) and {\pc REGEV|} (A.)|Hook
Young diagrams with applications to combinatorics and
to representations of Lie superalgebras, {\sl Adv. in Math.},
\`a para\^{\i}tre|
\article Berem|{\pc BERELE|} (A.) and {\pc REMMEL|} (J.B.)|Hook
flag characters and their combinatorics|J. Pure and Appl.
Algebra|35|1985|22-245|
\article Car1|{\pc CARLITZ|} (Leonard)|$q$-Bernoulli and
Eulerian numbers|Trans. Amer. Math. Soc.|76|1954|332--350|
\article Car2|{\pc CARLITZ| (Leonard)}|Eulerian numbers and
polynomials|Math. Magazine|33|1959|247--260|
\article Car3|{\pc CARLITZ| (Leonard)}|A combinatorial property
of $q$-Eulerian numbers|Amer. Math. Monthly|82|1975|51--54|
\article Car4|{\pc CARLITZ| (Leonard)}|The Expansion of 
certain Products|Proc. Amer. Math.
Soc.|7|1956|558--564| 
\divers Chemo|{\pc CHEEMA| (M.S.) {\rm and} \pc MOTZKIN|
(T.S.)}|Multipartitions and Multipermutations,
{\sl Combinatorics} [Los Angeles. $\oldstyle 1968$], p.~39--70\pointir
Providence, Amer. Math. Soc., {\oldstyle 1971}
({\sl Proc. Symposia in Pure Math.}, {\bf 19})|
\article Desfo1|{\pc D\'ESARM\'ENIEN|} (Jacques) et
{\pc FOATA|} (Dominique)|Fonctions sym\'e\-tri\-ques
et s\'eries hyperg\'eom\'etriques basiques 
multivari\'ees|Bull. Soc. Math. France|113|1985|3--22|
\divers Desfo2|{\pc D\'ESARM\'ENIEN|} (Jacques) et
{\pc FOATA|} (Dominique)|Fonctions sym\'e\-tri\-ques
et s\'eries hyperg\'eom\'etriques basiques 
multivari\'ees, II, {\sl Combinatoire \smash{\'E}num\'erative}
[Actes Colloque Univ. Qu\'ebec, Montr\'eal. $\oldstyle 1985$]\pointir Berlin,
Springer-Verlag, $\oldstyle 1987$
({\sl Lecture Notes in Math., {\bf 1234}})|

\divers Fo1|\pd FOATA (Dominique)|Distributions
eul\'eriennes et mahonniennes sur le groupe
des permutations, {\sl Higher Combinatorics}
[M. Aigner, ed., Berlin. $\oldstyle 1976$], p.~27--49\pointir 
Amsterdam, D.~Reidel, $\oldstyle 1977$
(Proc. {\eightrm NATO} Adv. Study Inst.)|

\divers Fo2|\pd FOATA (Dominique)|{\sl Fonctions sym\'e\-tri\-ques
et s\'eries hyper\-g\'eo\-m\'e\-triques basiques 
multivari\'ees}, IV, Preprint, Univ. Strasbourg, $\oldstyle 1987$|

\livre Fosch1|{\pc FOATA| (Dominique)} et {\pc SCH\"UTZENBERGER|
(Marcel-Paul)}|Th\'eorie g\'eo\-m\'e\-trique des polyn\^omes
eul\'eriens|Berlin, Springer-Verlag, $1970$
({\sl Lecture Notes in Math.}, {\bf 138})|
\article Fosch2|{\pc FOATA| (Dominique)} et {\pc SCH\"UTZENBERGER|
(Marcel-Paul)}|Major Index and Inversion of 
Permutations|Math. Nachr.|83|1978|143--159|



\article Foulk|{\pc FOULKES| (Herbert)}|Enumeration of 
Permutations with Prescribed Up-down and Inversion
Sequences|Discrete Math.|15|1976|235--252|
\article Gage|{\pc GARSIA| (Adriano M.)} and {\pc GESSEL|
(Ira)}|Permutation Statistics and 
Partitions|Advances in
Math.|31|1979|288--305| 
\divers Ge|\pd GESSEL (Ira)|Generating functins and
enumeration of sequences, Ph.D. thesis, department
of mathematics, {\eightrm M.I.T.}, Cambridge, Mass.,
111~p., $\oldstyle 1977$|
\livre Jake|{\pc JAMES|} (Gordon) and {\pc KERBER|}
(Adalbert)|The Representation Theory of the
Symmetric Group|Reading, Mass., Ad\-di\-son-Wesley,
{\oldstyle 1981} ({\sl Encyclopedia of Math. and Its 
Appl.}, {\bf 16})| 
\livre Knu|{\pc KNUTH| (Donald E.)}|The Art of Computer 
Programming, {\rm vol. 3, Sorting and
Searching}|Don Mills, Ontario, 
Addison-Wesley, {\oldstyle 1972}|

\divers Lasch1|\pd LASCOUX (Alain) et {\pc SCH\"UTZENBERGER|}
(Marcel-Paul)|A new statistics on words,
{\sl Combinatorial Mathematics, Optimal Designs and
their Applications} [J.~Srivastava, ed.,
Fort Collins, Colorado. $\oldstyle 1978$], p.~251--255\pointir
Amsterdam, North-Holland, {\oldstyle 1980}
({\sl Annals of Discrete Math.},~{\bf 6})|
\article Lasch2|\pd LASCOUX (Alain) et {\pc SCH\"UTZENBERGER|}
(Marcel-Paul)|Sur une conjecture de H.O.~Foulkes|C.R.
Acad. Sc. Paris|286A|1978|385--387|
\divers Lasch3|\pd LASCOUX (Alain) et {\pc SCH\"UTZENBERGER|}
(Marcel-Paul)|Formulaire raisonn\'e des fonctions
sym\'e\-tri\-ques, {\eightrm L.I.T.P., U.E.R.} Math., Univ. Paris~VII,
138~p., $\oldstyle 1984$|
\divers Lasch4|{\pc LASCOUX| (Alain) et \pc SCH\"UTZENBERGER| 
(Marcel-Paul)}|Le mono\"\i de plaxi\-que, 
{\sl Non-commutative Structures in Algebra and
geometric Combinatorics} [A.~de Luca, ed., 
Napoli. $\oldstyle 1978$], p. 129--156\pointir
Roma, Consiglio Nazionale delle Ricerche, {\oldstyle 1981}
({\sl Quaderni de ``La Ricerca Scientifica''}, {\bf 109})|
\livre Macd|{\pc MACDONALD| (Ian G.)}|Symmetric Functions
and Hall Polynomials|Ox\-ford, Clarendon Press, 
{\oldstyle 1979}| 
\article Mac1|{\pc MAC|\pc MAHON|} (Percy Alexander)|The indices
of permutations and the derivation therefrom
of functions of a single variable associated with the
permutations of any assemblage of 
objects|Amer. J. Math.|35|1913|314--321|
\livre Mac2|{\pc MAC|\pc MAHON|} (Percy Alexander)|Combinatory
Analysis, {\rm vol.~1}|Cambridge, Cambridge Univ. Press,
$\oldstyle 1915$ (R\'eimprim\'e par Chelsea, New York,
$\oldstyle 1955$)|
\article Mac3|{\pc MAC|\pc MAHON|} (Percy Alexander)|Two
applications of general theorems in combinatory
analysis|Proc. London Math. Soc.|15|1916|314--321|

\divers Mac4|{\pc MAC|\pc MAHON|} (Percy Alexander)|{\sl Collected
Papers}, vol.~1
[G.E. {\pc ANDREWS|}, ed.]\pointir
Cambridge, Mass., The M.I.T. Press, $\oldstyle 1978$|


\article Ra1|{\pc RAWLINGS| (Don)}|Generalized Worpitzky
Identities with Applications to Permutation 
Enumeration|Europ. J. Comb.|2|1981|67--78|
\article Ra2|{\pc RAWLINGS| (Don)}|The Combinatorics of 
certain Products|Proc. Amer. Math. 
Soc.|83|1983|560--562|
\article Re1|\pd REMMEL (J.B.)|The combinatorics of $(k,l)$-hook
Schur functions|Cont. Math.|34|1984|253--287|
\divers Re2|\pd REMMEL (J.B.)|A bijective proof of a factorization theorem
for $(k,l)$-hook Schur functions, Preprint, Univ. Calif. San Diego,
$\oldstyle 1985$|
\divers Re3|\pd REMMEL (J.B.)|Permutation Statistics and
$(k,l)$-hook Schur functions, {\sl Discrete Math.}, \`a para\^{\i}tre|
\article Ro|{\pc ROSELLE| (David P.)}|Coefficients associated
with the Expansion of certain 
Products|Proc. Amer. Math. Soc.|45|1974|144--150|
\article Sch1|{\pc SCH\"UTZENBERGER| (Marcel-Paul)}|Quelques 
remarques sur une 
cons\-truction de 
Schen\-sted|Math. Scand.|12|1963|117--128| 
\divers Sch2|{\pc SCH\"UTZENBERGER| (Marcel-Paul)}|La 
correspondance de Robinson, {\sl Com\-bi\-na\-toire et
repr\'esentation du groupe sym\'e\-tri\-que} [Actes 
Table Ronde C.N.R.S., Strasbourg. $\oldstyle 1976$], 
p.~59--113\pointir Berlin, Springer-Verlag, {\oldstyle 1977} 
({\sl Lecture Notes in Math.}, {\bf 579})|
\livre St1|\pd STANLEY (Richard P.)|Ordered Structures and
Partitions|Providence, R.I., Amer. Math. Soc., $\oldstyle 1972$
({\sl Memoirs Amer. Math. Soc.}, {\bf 119})|
\article St2|\pd STANLEY (Richard P.)|Binomial posets, M\"obius
inversion, and permutation enumeration|J. Combinatorial
Theory Ser.~A|20|1976|336--356|
\livre Wy|{\pc WYBOURNE|} (Brian G.)|Symmetry principles
and atomic spectro\-scopy|New York, Wiley $\oldstyle 1970$|



\bye

