%this is a plain tex file
\catcode'32=9
\magnification=1200


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

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

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

% Chargement des fontes AMS

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

\newfam\gothfam
\newfam\bboardfam

\catcode`\@=11

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

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

\let\bb=\bboard

\tenpoint

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

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

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

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

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

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

\frenchspacing

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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

\overfullrule=0pt
\medmuskip=3.5mu plus 1mu minus 3.5mu
\thickmuskip=4mu plus 2mu

\def\young#1{\null\vcenter{\baselineskip=12pt\m@th 
\ialign{\hfil$##$\hfil&&\hskip 3pt\hfil$##$\hfil\crcr 
\vphantom(\crcr\noalign{\kern-\baselineskip} #1\crcr\mathstrut\crcr\noalign{\kern-\baselineskip}}}} \def\smallyoung#1{\null\vcenter{\baselineskip=8pt\m@th 
\ialign{\hfil$\scriptstyle ##$\hfil&&\hskip 1.4pt 
\hfil$\scriptstyle ##$\hfil\crcr
\vphantom{\scriptstyle (}\crcr\noalign{\kern-\baselineskip} #1\crcr\mathstrut\crcr\noalign{\kern-\baselineskip}}}} \let\aigu=\aig@
\catcode`@=12

\def\god{{\goth D}}
\def\gok{{\goth K}}
\def\gos{{\goth S}}
\def\des{\mathop{\rm des}\nolimits}
\def\rec{\mathop{\rm rec}\nolimits}
\mathchardef\fd="2221 % fleche a droite comme operation 
\mathchardef\fb="2223 % fleche en bas comme operation 
\abovedisplayskip=6pt plus 2pt minus 2pt
\abovedisplayshortskip=0pt plus 2pt minus 0pt 
\belowdisplayskip=6pt plus 2pt minus 2pt
\belowdisplayshortskip=6pt plus 2pt minus 0pt 

\vglue 1cm
\centerline{{\bf DESCENTES DES D\'ERANGEMENTS}} 
\vskip 3pt
\centerline{{\bf ET MOTS CIRCULAIRES%
\footnote{(*)}{Soutien par le P.R.C. Math\'ematiques 
et Informatique.}}}
\medskip\medskip 
\centerline{{\petcap Jacques} D\'ESARM\'ENIEN
\footnote{(**)}% 
{D\'epartement d'informatique, I.U.T. Strasbourg~III, 72,
route du Rhin, F-67400~Ill\-kirch-Graf\-fen\-staden.}
{\sevenrm ET}
{\petcap Michelle} WACHS \footnote{(***)}% 
{Department of
mathematics, University of Miami, Coral Gables, FL~33124, U.S.A.}}
\bigskip\bigskip 
\resume{Au moyen de deux bijections, dues \`a Macdonald
et \`a  Gessel, nous \'etablissons que l'ensemble des descentes 
des d\'erangements et l'ensemble des reculs d'une classe de
permutations caract\'eris\'ee par la suite de ses mont\'ees et
descentes ont m\^eme distribution.} 
\smallskip 
\abstract{Using two bijections by Macdonald and Gessel,  we show
that the set of the descents of derangements and the set of the
descents of the inverse of permutations characterized by their
up-down sequences have the same distribution.} 

\titre Introduction| 
Dans un pr\'e\-c\'e\-dent article, l'un des auteurs [2] a
montr\'e que l'ensemble des permutations d\'ebutant par 
un nombre impair de descentes est en bijection avec l'ensemble
des d\'erangements et fournit un cadre int\'eressant pour
expliquer des formules classiques de r\'ecurrence sur le nombre
de d\'erangements. De plus, cet ensemble se pr\^ete bien \`a des
$q$-extensions, et donne naissance \`a une famille de fonctions
sym\'etriques d'un type d\'ej\`a connu (\cf. [1], [4], [6]). Gessel,
dans un travail non publi\'e [7], a effectu\'e le
$q$-d\'enombrement des d\'erangements par indice majeur, qui
appara\^{\i}t \^etre identique au $q$-d\'enombrement par
indice majeur inverse des permutations que nous avions
\'etudi\'ees. En fait, une investigation plus pouss\'ee a conduit
\`a la constatation suivante, \'enonc\'ee dans [3], que les
distributions des ensembles des descentes des d\'erangements
et des ensembles des reculs des permutations d\'ebutant par un
nombre impair de descentes co\"{\i}ncident. Ceci est
\'evidemment un r\'esultat plus fort que la simple \'egalit\'e de
deux $q$-s\'eries. 

Malheureusement, le travail de Gessel ci-dessus mentionn\'e ne
contient aucune d\'emonstration,  et c'est au cours d'une
conversation avec l'une de nous qu'il a indiqu\'e son id\'ee de
d\'epart. Ceci a permis, non seulement de reconstituer les
d\'emonstrations du travail de Gessel (ce qui a \'et\'e fait
dans~[10]), mais aussi de montrer qu'il a d\'ecouvert un outil
susceptible d'autres utilisations.

En particulier il permet d'\'etablir l'\'egale distribution des
ensembles introduits plus haut.

Par ailleurs, diverses d\'emonstrations bijectives de ce
r\'esultat ont \'et\'e \'etablies par l'un des auteurs ({\it
cf.}~[11]), qui doivent \^etre incluses dans une r\'edaction
d\'efinitive de ce travail. 

\titre 1. Le probl\`eme|
Nous allons ici donner les d\'efinitions et
notations qui seront utilis\'ees dans toute la suite.

Tout d'abord, si $[n]=\{1,2,\ldots ,n\}$ et $E$ est une partie de
$[n-1]$, on dira que la suite $s=s_1,s_2,\ldots ,s_n$ d'entiers
strictement positifs est {\it compatible avec $E$}, ce que nous
noterons $s\perp E$, si :  
$$
\eqalign{&i\ :\ s_1\geq s_2\geq \cdots \geq s_n>0;\cr  &ii\ :\
i\in E\Rightarrow s_i>s_{i+1}.}
$$ 
Nous aurons \`a consid\'erer un ensemble $X=\{ x_1,x_2,\ldots
\} $ d'ind\'etermin\'ees commutatives. Le {\it poids} de la suite
$s$ est le produit $w(s)=x_{s_1}x_{s_2}\cdots x_{s_n}$.

Soit maintenant $\sigma \in \gos_n$ une permutation de $[n]$.
Un entier $i\in [n-1]$ est une {\it descente} (resp. {\it
mont\'ee}) de $\sigma $ si $\sigma _i>\sigma _{i+1}$ (resp.
$\sigma _i<\sigma _{i+1}$). Un {\it recul} de $\sigma $ est une
descente de $\sigma ^{-1}$. Notons $\des \sigma $ et $\rec
\sigma $ respectivement les ensembles des descentes et des
reculs de $\sigma $. 

La {\it forme} (``up-down sequence'') de $\sigma $ est la suite
de longueur $n-1$ dont le i-i\`eme symbole est $M$ ou $D$
selon que $i$ est une mont\'ee ou une descente de $\sigma $.

Si la d\'ecomposition en produit de cycles est constitu\'ee de
cycles de longueur $\lambda _1,\lambda _2,\ldots ,\lambda _k$ on
dira que la partition $\lambda $ de $n$ est le {\it type} (``cycle
structure'') de $\sigma $.

Nous aurons \`a consid\'erer deux ensemble de permutations :
l'un, classique, est celui des {\it d\'erangements}, ou
permutations sans point fixe, not\'e $\god_n$, dont le nombre
d'\'el\'ements est $d_n$ ; l'autre, introduit dans [2], est
l'ensemble $\gok_n$ des permutations dont la forme d\'ebute par
un nombre {\it impair} de $D$ ; le nombre de ses \'el\'ements est
$k_n$. On sait d\'ej\`a que $d_n=k_n$. Nous allons montrer un
r\'esultat plus fort, en consid\'erant les ensembles $\god_n^E$
et $\gok_n^E$ d'\'el\'ements de $\god_n$ et de $\gok_n$ dont
l'ensemble des descentes pour $\god_n$ et des reculs pour
$\gok_n$ est un ensemble $E$ donn\'e. (Il serait possible de ne
s'int\'eresser qu'aux ensembles de reculs : leur distribution est
identique \`a celle des descentes sur $\god_n$ ; c'est pour des
raisons historiques que nous avons maintenu cette distinction.)
Notons respectivement $d_n^E$ et $k_n^E$ le nombre de leurs
\'el\'ements. Le r\'esultat nouveau et principal de cet article
est le suivant. 

\th Th\'eor\`eme 1|Quel que soit $E$, on a l'\'egalit\'e $d_n^E=k_n^E$.
\finth

\titre 2. Les fonctions de Schur|
Pour tous d\'etails compl\'ementaires, on
renvoie \`a [8]. Soient $\mu /\lambda $ une forme gauche d'ordre $n$.
Un {\it tableau semi-standard} de forme $\mu /\lambda $ est une application $T$ de $\mu /\lambda $ dans l'ensemble des entiers strictement positifs telle que les indices vont en {\it d\'ecroissant strictement} de bas en haut dans les colonnes et en {\it d\'ecroissant au sens large} de gauche \`a droite dans les lignes. Par exemple,
$$\young{2&1\cr3&3&1\cr & &5\cr & &8&6&2\cr}$$ 
\smallskip\noindent
est un tableau semi-standard de forme $5332/22$. 

Le {\it poids} de $T$ est le produit $w(T)$ des ind\'etermin\'ees
de $X$ dont les indices figurent dans $T$. Un tel tableau
d\'efinit un ordre total $\preceq$ sur les points de la forme
$\mu /\lambda $ en convenant que $(i,j)\prec (i',j')$ si
$T(i,j)>T(i',j')$ ou $T(i,j)=T(i',j')$ et $i\leq i'$. En pla\c cant
l'entier $k$ sur le point $(i,j)$ de $\mu /\lambda $ s'il est le
k-i\`eme dans l'ordre ainsi d\'efini, on obtient un {\it tableau
standard} $\Theta $ de forme $\mu /\lambda $, contenant tous
les entiers de 1 \`a l'{\it ordre} $n$ de $\Theta $ avec
croissance stricte suivant les lignes et les colonnes.

Un {\it recul} d'un tableau standard $\Theta $ est un entier
$i\in [n-1]$ tel que $i+1$ apparaisse \`a gauche ou au dessus
de $i$ dans $\Theta $. 

Si $T$ est un tableau semi-standard et $\Theta $ le tableau
standard associ\'e, on voit ais\'ement que la suite
d\'ecroissante des \'el\'ements de $T$ est compatible avec
l'ensemble $\rec\Theta $ des reculs de $\Theta $. On a m\^eme le
r\'esultat suivant (\cf.~[4]). 

\th Proposition 2|Il y a une bijection entre l'ensemble des
tableaux semi-standard $T$ de forme $\mu /\lambda $ et
l'ensemble des couples $(\Theta ,s)$ constitu\'es d'un tableau
standard de forme $\mu /\lambda $ et d'une suite compatible
avec $\rec\Theta $. De plus, les poids de $T$ et de $s$ sont
\'egaux.  \finth

Le couple $(\Theta ,s)$ associ\'e au tableau semi-standard de
l'exemple pr\'e\-c\'e\-dent est : $$\Theta =\young{6&8\cr
4&{\bf 5}&9\cr &&{\bf 3}\cr &&1&{\bf 2}&{\bf 7}\cr}  \qquad
s=8{\bf 65}3{\bf 3}2{\bf 2}11\ ;$$ on a indiqu\'e en gras les
reculs de $\Theta $ ainsi que les \'el\'ements de $s$ dont
l'indice est un recul de $\Theta $. 

La {\it fonction de Schur} $S_{\mu /\lambda }(X)$ est la somme
des poids de tous les tableaux semi-standard de forme $\mu
/\lambda $. C'est une fonction sym\'etrique. La proposition
pr\'e\-c\'e\-dente peut donc \^etre r\'ecrite comme suit.

\th Proposition 3|La fonction de Schur vaut : 
$$
S_{\mu /\lambda }(X)=\sum _\Theta \sum _{s\perp\rec\Theta
}w(s),
$$  
la somme \'etant \'etendue aux tableaux standard
$\Theta $ de forme $\mu /\lambda $. 
\finth

\`A partir de cette proposition, on peut faire le lien entre
fonction de Schur et $q$-d\'enombrement des tableaux standard
par somme de leurs reculs (l'indice majeur inverse, \cf. [4, 9]). 

Le cas qui nous int\'eressera sp\'ecialement est celui o\`u la
forme $\mu /\lambda $ est un {\it ruban connexe} (\cf. [1]),
c'est \`a dire que tout point de la forme $\mu /\lambda $ a un
pr\'ed\'ecesseur situ\'e \`a gauche ou au dessus et un
successeur \`a droite ou au dessous, sauf deux points, l'origine
qui n'a pas de pr\'ed\'ecesseur et l'extr\'emit\'e qui n'a pas de
successeur. Un tableau standard dont la forme est un ruban
connexe peut \^etre vu comme la permutation obtenue en lisant
le tableau ligne apr\`es ligne ; la forme de la permutation est
alors identifi\'ee au ruban et les reculs du tableau sont ceux de
la permutation.

Un cas particulier est celui o\`u le ruban est une partition
contenant une seule part. La fonction de Schur est alors la {\it
fonction \'el\'ementaire compl\`ete} $S_n(X)$. 

\th Proposition 4|Lorsque $\rho $ et $\rho '$ sont deux rubans,
le produit des fonctions de Schur $S_\rho (X)$ et $S_{\rho
'}(X)$ se d\'ecompose en somme de deux fonctions de Schur
elles-m\^emes associ\'ees \`a des rubans :  
$$
S_\rho (X)S_{\rho '}(X)
=S_{\rho \fd \rho'}(X) +S_{\rho \fb \rho'}(X),
$$   
o\`u $\rho \fd \rho '$ et $\rho \fb \rho '$ sont obtenus en pla\c
cant l'origine de $\rho '$ respectivement \`a droite et en
dessous de l'extr\'emit\'e de $\rho $. \finth Cette
d\'ecomposition se voit tr\`es simplement en examinant les
tableaux semi-standard.

Par exemple,
$$
S_{\smallyoung{\times &\times \cr}}(X)S_{\smallyoung{\times \cr 
\times &\times \cr}}(X)=
S_{\smallyoung{\times &\times &\times \cr
&&\times &\times \cr}}(X) +S_{\smallyoung{\times &\times \cr&\times
\cr&\times &\times \cr}}(X).
$$ 

Un corollaire de la proposition pr\'e\-c\'e\-dente 
permet de d\'evelopper $S_1(X)^n$.

\th Proposition 5|On a la formule :
$$
S_1(X)^n=\sum _{\sigma \in \gos_n}
\sum_{s\perp\rec\sigma}w(s). 
$$  
\finth

Nous en arrivons maintenant aux permutations dans $\gok_n$. 
La forme du tableau standard associ\'e \`a un \'el\'ement de
$\gok_n$ commence donc par un nombre impair de pas verticaux,
c'est \`a dire que la premi\`ere colonne du ruban est de longueur
paire. Appelons $K_n(X)$ la fonction sym\'etrique somme des
poids des tableaux semi-standard dont la forme est un tel ruban
de longueur $n$. En somme,  
$$K_n(X)=\sum
_{\sigma \in \gok_n}\sum _{s\perp\rec\sigma }w(s).
$$ 

Par exemple,
$$K_4(X)
=S_{\smallyoung{\times \cr\times &\times &\times \cr}}(X) 
+S_{\smallyoung{\times \cr\times &\times \cr&\times \cr}}(X)
+S_{\smallyoung{\times \cr\times \cr\times \cr\times \cr}}(X).
$$ 

Partant d'un ruban quelconque, il existe une et une seule fa\c
con  d'en enlever, \`a partir de son origine, une bande
horizontale de mani\`ere \`a laisser un ruban qui commence par
un nombre impair de pas verticaux. Par exemple, 
$$
\young{\times &\times \cr&\times \cr&\times
&\times \cr}
=  \young{\times &\times \cr}\fb\young{\times \cr  \times
&\times \cr}\quad\hbox{et} 
\quad \young{\times &\times \cr&\times
&\times &\times \cr}
= \young{\times \cr}\fd\young{\times \cr\times
&\times &\times \cr}.$$ 

En tenant compte de la proposition pr\'e\-c\'e\-dente, cette
remarque  se traduit par la proposition suivante, qu'on peut
comparer \`a la formule d'inclusion-exclusion donnant le nombre
de d\'erangements. 

\th Proposition 6|La suite de fonctions sym\'etriques $K_n(X)$
est donn\'ee par la r\'ecurrence : 
$$\eqalign{i\ &:\ K_0(X)=1;\cr
ii\ &:\ S_1(X)^n=\sum _{0\leq k\leq n} S_k(X)K_{n-k}(X), 
\qquad n\geq 1.\cr}$$
\finth

\titre 3. La factorisation de Lyndon|

Un {\it mot de Lyndon} de longueur $n$ est un mot
$c=c_1c_2\cdots c_n$ dont les lettres sont des entiers
strictement positifs et qui est strictement plus petit (pour
l'ordre lexicographique) que toutes ses permutations
circulaires. Le {\it poids} d'un mot est le produit des
ind\'etermin\'ees de $X$ dont les indices apparaissent dans le
mot.

Le r\'esultat suivant, d\^u \`a Lyndon ({\it cf.}~[8]), est un
classique, bien connu des informaticiens. 

\th Proposition 7|Tout mot $w$ se factorise de mani\`ere unique
en produit de concat\'enation de mots de Lyndon $w^1w^2\cdots
w^k$ qui, dans cet ordre, vont en d\'ecroissant
lexicographiquement. \finth

Consid\'erons par exemple le mot suivant, de longueur 9 : 
$w=321231212$. On trouve la d\'ecomposition de Lyndon de $w$ en
isolant successivement  les facteurs droits minimaux de $w$
([8], prop.~5.1.6 p.~67). Les facteurs de $w$ sont donc : 
$w=3\ 2\ 123\ 12\ 12$.

Les longueurs des facteurs de Lyndon d'un mot $w$ de longueur
$n$ constituent une partition $\lambda$ de $n$, appel\'ee {\it
type} de $w$. Le type du mot de l'exemple pr\'e\-c\'e\-dent est
$\lambda=32211$. 

Exposons maintenant la {\it construction de Gessel} [7, 10].
Partons de la d\'ecomposition de Lyndon d'un mot
$w=w^1w^2\cdots w^k$. \`A la $i$-i\`eme lettre de $w$ qui
appara\^{\i}t dans le mot de Lyndon $w^r$, associons le mot
$p(i)$ infini obtenu en lisant circulairement $w^r$ \`a partir de
la $i$-i\`eme lettre de $p$. Le mot $w$ d\'efinit alors un ordre
total $\preceq$ sur ses $n$ positions comme suit : $i\prec j$ si
$p(i)$ est plus grand que $p(j)$ pour l'ordre lexicographique, ou
si $p(i)=p(j)$ et $i<j$. Soit $\tau$ le mot qui \`a $i$ associe sa
position dans l'ordre $\preceq$. On peut \`a son tour factoriser
$\tau$ en produit de mots de Lyndon pour l'ordre inverse de
l'ordre naturel. Chacun des facteurs peut alors \^etre
consid\'er\'e comme un cycle d'une permutation $\sigma$ de type
$\lambda$ dont l'\'ecriture en produit de cycles est
$\sigma=\sigma^1\sigma2\cdots\sigma^k$. Cette derni\`ere
partie n'est autre que la ``transformation fondamentale de
Foata'' ({\cf.}~[5], p.~15). 

On peut alors montrer que la suite d\'ecroissante des entiers 
qui figurent dans $w$ est compatible avec l'ensemble $\des
\sigma $ des descentes de $\sigma $, d'o\`u le th\'eor\`eme qui
suit. 

\th Proposition 8|Il y a une bijection entre l'ensemble des mots
$w$ de type $\lambda $ et l'ensemble des couples $(\sigma ,s)$
constitu\'es d'une permutation $\sigma \in \gos_n$ de type
$\lambda $ et d'une suite $s$ compatible avec $\des \sigma $. De
plus, les poids de $w$ et de $s$ sont \'egaux. 
\finth

Cette construction est illustr\'ee par la continuation de
l'exemple pr\'e\-c\'e\-dent. Soit
$$w=\biggl(\young{1&\ &2&\ &3&4&5&\ &6&7&\ &8&9\cr 
3&\ &2&\ &1&2&3&\ &1&2&\ &1&2\cr}\biggr),$$ 
o\`u l'on a indiqu\'e dans la premi\`ere ligne les indices $i$ et
dans la deuxi\`eme les facteurs de Lyndon de $w$ ; le type de
$w$ est $\lambda =32211$.

Pour ce mot,
$$\eqalign{&p(1)=333333\ldots \qquad p(2)=222222\ldots \cr 
&p(3)=123123\ldots \qquad p(4)=231231\ldots \cr 
&p(5)=312312\ldots \qquad p(6)=121212\ldots \cr 
&p(7)=212121\ldots \qquad p(8)=121212\ldots \cr 
&p(9)=212121\ldots \cr}$$ 
L'ordre sur les positions de $p$ est donc : 
$$1\prec5\prec4\prec2\prec7\prec9\prec3\prec6\prec8.$$ 
Par cons\'equent, 
$$\tau=\biggl(\young{1&2&3&4&5&6&7&8&9\cr 
1&4&7&3&2&8&5&9&6\cr}\biggr).$$ 
On en d\'eduit la d\'ecomposition de
$\sigma $ en produit de cycles :  
$$\sigma =(1)(4)(732)(85)(96),$$
soit, en indiquant simultan\'ement les descentes de $\sigma $ et
les  \'el\'ements correspondants de $s$ en gras : 
$$\eqalign{\sigma &=\biggl(\young{1&{\bf 2}&3&4&5&{\bf
6}&7&8&9\cr  1&{\bf 7}&2&4&8&{\bf 9}&3&5&6\cr}\biggr)\cr 
s&=\mathopen{\phantom{\biggl(}}\young{3&{\bf 3}&2&2&2&{\bf
2}&1&1&1\cr}.}$$ 
On remarque que la bijection inverse de celle d\'ecrite
consiste \`a \'ecrire les cycles de $\sigma$ avec leur plus 
grand \'el\'ement en t\^ete et par ordre croissant de ce plus
grand \'el\'ement, ce qui donne $\tau$, puis \`a remplacer dans
$\tau$ l'entier $k$ par le $k$-i\`eme \'el\'ement de la suite
$s$. 

Si $\lambda $ est une partition de $n$, notons $P_\lambda (X)$
la somme des poids de toutes les mots de type $\lambda $.
D'apr\`es la proposition~8 :  
$$P_\lambda (X)=\sum _\sigma \sum _{s\perp \des \sigma } w(s),$$ 
o\`u la premi\`ere somme est sur les permutations de type
$\lambda $. Un d\'evelop\-pe\-ment analogue \`a celui
mentionn\'e apr\`es la proposition~3 permet de faire le lien
entre les fonctions sym\'etriques $P_\lambda (X)$ et le
$q$-d\'enombrement des permutations de type donn\'e.
L'\'evaluation de $P_\lambda (X)$ peut se faire au moyen de la
formule d'\'enum\'eration de P\'olya (\cf. [7,~10]).

La somme des poids de tous les mots de longueur $n$ est
\'evidemment \'egale \`a $S_1(X)^n$. Avec la proposition~8, on
trouve donc :  $$S_1(X)^n=\sum _{\sigma \in \gos_n}\sum
_{s\perp\des\sigma }w(s)=  \sum _\lambda P_\lambda (X),$$ 
la derni\`ere somme \'etant \'etendue \`a
toutes les partitions de $n$. 

Le produit de deux fonctions $P$ se fait simplement lorsque
leurs types  n'ont aucune part en commun, en prenant la
r\'eunion des types : 
$$P_{3111}(X)P_{422}(X)=P_{4322111}(X).$$  
Cette propri\'et\'e
se voit directement sur les mots, en intercalant leurs facteurs
de Lyndon respectifs. La situation est moins simple lorsque les
types ont des parts en commun. Par exemple, il est clair que
$P_1(X)=S_1(X)$ ; d'autre part, un mot de type 111\dots\ est en
fait une suite faiblement d\'ecroissante d'entiers. Par
cons\'equent, $P_{1^k}(X)=S_k(X)$, la fonction sym\'etrique
\'el\'ementaire compl\`ete. 

Appelons maintenant $D_n(X)$ la somme des $P_\lambda (X)$ dont
le type ne contient pas de parts \'egales \`a 1. En d'autres
termes, les permutations associ\'ees $\sigma $ de la
proposition~8 sont des d\'erangements, soit : 
$$D_n(X)=\sum_{\sigma \in \god_n}\sum _{s\perp
\des\sigma }w(s).$$ 
Toute partition r\'esulte, d'une mani\`ere unique, de la r\'eunion
d'une partition sans parts \'egales \`a 1 et d'une partition dont
toutes les parts sont \'egales \`a 1. Dans ce cas, les types n'ont
pas de part en commun, ce qui, compte tenu de la convention
$D_0(X)=1$ nous donne la proposition suivante.

\th Proposition 9|La suite de fonctions sym\'etriques $D_n(X)$ 
est donn\'ee par la r\'ecurrence :
$$\eqalign{i\ &:\ D_0(X)=1;\cr
ii\ &:\ S_1(X)^n=\sum _{0\leq k\leq n}S_k(X)D_{n-k}(X), 
\qquad n\geq 1.\cr}$$
\finth

\titre 4. Le r\'esultat principal|
Comme corollaire aux propositions~6 et 9, on a bien entendu : 

\th Proposition 10|Les fonctions sym\'etriques $K_n(X)$ et
$D_n(X)$  sont \'egales.
\finth

Partons de la d\'efinition de $D_n(X)$ : 
$$\eqalign{D_n(X)&=\sum _{\sigma \in \god_n}
\sum _{s\perp\des\sigma }w(s)\cr 
&=\sum _{E\subset [n-1]}\sum _{\sigma \in \god_n^E}
\sum _{s\perp E}w(s)\cr  
&=\sum _{E\subset [n-1]}d_n^E\sum _{s\perp E}w(s).\cr}$$ 
Il en est de m\^eme pour
$K_n(X)$. On a donc :  
$$\sum _{E\subset [n-1]}(d_n^E-k_n^E)W(E)=0,\leqno{\hbox{(*)}}$$ 
o\`u, pour simplifier,
on a pos\'e : 
$$W(E)=\sum _{s\perp E}w(s).$$

\'Ecrivons les mon\^omes de degr\'e $n$ en $X$ par ordre
d\'ecroissant des indices des ind\'etermin\'ees, et ordonnons
ces mon\^omes ainsi \'ecrits par ordre lexicographique. Soit
maintenant $E=\{ i_1,i_2,\ldots ,i_k\} \subset [n-1]$. Le plus
petit mon\^ome qui appara\^{\i}t dans $W(E)$, appel\'e son {\it
terme dominant}, est : 
$$x_{k+1}^{i_1}x_k^{i_2-i_1}\!\cdots
x_2^{i_k-i_{k-1}}x_1^{n-i_k},
$$ 
correspondant \`a la suite $s$ constante sauf pour les indices
de $E$, o\`u la d\'ecroissance est d'une unit\'e. Par exemple, aux
ensembles $E=\emptyset $, $\{ 1\} $, $\{ 2\} $, $\{ 1,2\} $ et 
$\{1,3\} $ correspondent les termes dominants respectifs :  
$$
x_1^n,\quad x_2^{}x_1^{n-1},\quad x_2^2x_1^{n-2},\quad 
x_3^{}x_2^{}x_1^{n-2}\quad 
\hbox{et} \quad x_3^{}x_2^2x_1^{n-3}.
$$
En supposant les ensembles $E$ ordonn\'es par taille croissante
puis par ordre lexicographique de leurs \'el\'ements lorsqu'ils
ont m\^eme taille, le lemme suivant est donc vrai. 

\th Lemme 11|L'application qui \`a $E$ associe son terme
dominant est  strictement croissante.
\finth

L'identit\'e (*) implique donc, par l'argument triangulaire
habituel, que le coefficient de $W(E)$ est nul pour tout $E$, ce
qui est exactement le th\'eor\`eme~1.

\goodbreak\vskip 44pt
\eightpoint
\centerline{BIBLIOGRAPHIE}
\nobreak\vskip 6pt
\article 1|\pd D\'ESARM\'ENIEN (Jacques)|Fonctions sym\'etriques 
associ\'ees \`a des suites classiques de nombres|Ann. scient. 
\smash{\'E}cole normale sup\'erieure|16|1983|271--304| 
\divers 2|\pd D\'ESARM\'ENIEN (Jacques)|Une autre interpr\'etation  du
nombre de d\'eran\-ge\-ments, {S\'eminaire Lotharingien de
combinatoire}, B08a, {\oldstyle 1983}| 
\divers 3|\pd D\'ESARM\'ENIEN (Jacques)|Une autre
interpr\'etation\dots,  conf\'erence prononc\'ee au 28\emini~Colloque des
sciences math\'ematiques du Qu\'ebec, Universit\'e du Qu\'ebec \`a
Montr\'eal, 31~octobre 1987| 
\article 4|\pd D\'ESARM\'ENIEN (Jacques) et
\pd FOATA  (Dominique)|Fonctions sym\'etriques et s\'eries
hyperg\'eom\'etriques basiques multivari\'ees|Bull. Soc. math.
France|113|1985|3--22| 
\livre 5|\pd FOATA (Dominique) et \pd
SCH\"UTZENBERGER  (Marcel-Paul)|Th\'eorie g\'eom\'e\-trique des
polyn\^omes eul\'eriens|Berlin, Springer-Verlag (Lecture Notes in
Mathematics, vol.~{\bf 138}), {\oldstyle 1970}| 
\article 6|\pd FOATA
(Dominique) et \pd SCH\"UTZENBERGER  (Marcel-Paul)|Major index and
inversion number of permutations|Math. Nachr.|83|1978|143--159| 
\divers 7|\pd GESSEL (Ira)|Note non publi\'ee| 
\livre 8|\pd LOTHAIRE (M.)|Combinatorics on words|Reading, Addison-Wesley
(Encyclopedia of Mathematics and its Applications, vol.~{\bf 17}),
{\oldstyle 1983}|  
\livre 9|\pd MACDONALD (Ian G.)|Symmetric functions and Hall 
polynomials|Oxford, Clarendon Press, {\oldstyle 1979}| 
\divers 10|\pd WACHS (Michelle)|Communication orale| 
\divers 11|\pd WACHS (Michelle)|Communications \'ecrites| 

\bye
