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


\catcode`\@=12

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

\def\maj{\mathop{\rm maj}\nolimits}
\def\majr{\mathop{{\rm maj}*}\nolimits}
\def\rec{\mathop{\rm rec}\nolimits}
\def\des{\mathop{\rm des}\nolimits}

\null 
\bigskip\bigskip
\centerline{{\bf DISTRIBUTION DE L'INDICE MAJEUR R\'EDUIT}} 
\smallskip
\centerline{{\bf SUR LES D\'ERANGEMENTS}} 
\bigskip
\centerline{{\petcap Jacques} 
D\'ESARM\'ENIEN\footnote{*}{Avec le soutien  du P.R.C.
Math.--Info.}}


\titre Introduction|
Le nombre de d\'erangements de $n$ objets, not\'e $d_n$ 
satisfait la relation de r\'ecurrence tr\`es simple :
$$d_n=n d_{n-1} +(-1)^n.\leqno(*)$$
Assez curieusement, il n'existe pas de d\'emonstration bijective 
\`a proprement parler imm\'ediate de cette formule.

Nous avons montr\'e dans [D1] comment un mod\`ele distinct de celui des
d\'erangements et en bijection avec celui-ci permet d'interpr\'eter
simplement cette r\'ecurrence. Ce travail a \'et\'e amplifi\'e dans
[D--W1, D--W2] et plac\'e dans le contexte des fonctions sym\'etriques.
Il est possible \'egalement d'en d\'eduire des formules explicites pour
les $q$-d\'erangements, formules obtenues aussi directement par
Michelle Wachs [W].

Dans un article r\'ecent [D2], nous nous sommes int\'eress\'e 
\`a la r\'eduction modulo $n$ des statistiques mahoniennes. Nous allons
montrer ici comment la notion d'indice majeur r\'eduit permet
d'interpr\'eter directement la formule $(*)$. 

\titre 1. Les $q$-d\'erangements|
\'Etant donn\'ee une permutation $\sigma$ de $[1,n]$,
consid\'er\'ee  comme un mot de longueur $n$, l'ensemble des
{\it descentes} de $\sigma$ est l'ensemble des indices $i$,
$1\leq i\leq n-1$ tels que $\sigma_i\geq \sigma_{i+1}$. L'{\it
indice majeur} de $\sigma$, not\'e $\maj \sigma$ est la somme
des \'el\'ements de cet ensemble.

Soit ${\cal D}_n$ l'ensemble des {\it d\'erangements} (ou
permutations  sans point fixe) de $[1,n]$. On peut \'evaluer la
fonction g\'en\'eratrice $d_n(q)=\sum_{\sigma \in {\cal D}_n}
q^{\maj \sigma}$ de l'indice majeur sur ${\cal D}_n$. Ce
polyn\^ome est appel\'e {\it $q$-d\'erangement}. Si l'on note
$[n]=1+q+q^2+\cdots+q^{n-1}$ et $[n]!=[1][2]\ldots [n]$, on
a la formule suivante, \'enonc\'ee par Ira Gessel et
d\'emontr\'ee combinatoirement par Michelle Wachs. C'est le
$q$-analogue de la formule classique donnant le nombre de
d\'erangements. 

\th Proposition 1.1|La fonction g\'en\'eratrice de l'indice majeur sur
l'ensemble des d\'erangements de $[1,n]$ vaut : 
$$d_n(q)=[n]!\sum_{0\leq
k\leq n}{(-1)^k \over [k]!} q^{k(k-1)/2}.$$ 
\finth

Cette proposition peut aussi se d\'eduire des formules donn\'ees dans 
[D--W1] pour les fonctions sym\'etriques associ\'ees aux d\'erangements
en sp\'ecialisant les ind\'etermin\'ees en les puissances successives de
$q$. 

\`A partir de la proposition pr\'ec\'edente, on v\'erifie sans peine que 
les $q$-d\'erangements satisfont la r\'ecurrence suivante. 

\th Proposition 1.2|Les $q$-d\'erangements sont donn\'es 
par la r\'ecur\-rence : 
$$\eqalign{(i)\ &:\ d_0(q)=1\ ;\cr
(ii)\ &:\ d_n(q)=[n]d_{n-1}(q)+(-1)^n q^{n(n-1)/2}.\cr}$$ 
\finth

La r\'ecurrence $(*)$ s'obtient bien en faisant $q=1$ dans la 
proposition pr\'ec\'edente.

\titre 2. L'indice majeur r\'eduit|
Dans [D2], nous avons introduit la notion suivante : lorsque $\sigma$ 
est une permutation de $[1,n]$, on appelle {\it indice majeur r\'eduit} de
$\sigma$, qu'on note $\majr \sigma$ le reste de l'indice majeur de
$\sigma$ modulo $n$. De la sorte, la fonction g\'en\'eratrice de $\majr$
sur un ensemble de permutations est le reste modulo $1-q^n$ de la
fonction g\'en\'eratrice de $\maj$ sur le m\^eme ensemble. 

En particulier, dans le cas des d\'erangements, si l'on note $d_n^k$ 
le nombre de d\'erangements de $[1,n]$ dont l'indice majeur r\'eduit vaut
$k$, ($0\leq k\leq n-1$), le polyn\^ome $d_n^*(q)=\sum_{0\leq k\leq
n-1}d_n^k q^k$ est le reste de $d_n(q)$ modulo $1-q^n$. 

On v\'erifie imm\'ediatement le lemme suivant. 

\th Lemme 2.1|Si $P(q)$ est un polyn\^ome, on a la congruence : 
$$
P(q)[n]\equiv P(1)[n] \pmod{1-q^n}.
$$
\finth

On peut alors r\'eduire modulo $1-q^n$ la r\'ecurrence de la 
proposition 1.2 : 
$$
d_n^*(q)=[n]d_{n-1}(1)+\cases{q^{n/2}, &si $n$ est pair,\cr 
-1, &si $n$ est impair,\cr}
$$
compte-tenu du reste de $q^{n(n-1)/2}$ modulo $1-q^n$. 

\goodbreak
Les coefficients de $d_n^*(q)$ sont donc tous \'egaux, sauf celui de 
$q^{n/2}$ si $n$ est pair et le terme constant si $n$ est impair.
Puisque $d_{n-1}(1)=d_{n-1}$, nombre de d\'erangements, il s'ensuit
qu'on a partitionn\'e l'ensemble ${\cal D}_n$ en $n$ parts, chacune de
cardinal $d_{n-1}$ sauf une qui vaut alternativement $d_{n-1}+1$ et
$d_{n-1}-1$. 

L'interpr\'etation de la r\'ecurrence $(*)$ est ainsi accomplie par le 
r\'esultat suivant.

\th Proposition 2.2|Le nombre $d_n^k$ de d\'erangements de $[1,n]$ dont l'indice majeur est congru \`a $k$ modulo $n$ vaut $d_{n-1}$ sauf $$
\eqalign{(i)\ &:\ \hbox{lorsque $n$ est pair et $k=n/2$ auquel cas 
$d_n^{n/2}=d_{n-1}+1$,}\cr
(ii)\ &:\ \hbox{lorsque $n$ est impair et $k=0$ auquel cas 
$d_n^0=d_{n-1}-1$.}
}$$
\finth

Il serait \'evidemment int\'eressant de d\'emontrer 
{\it directement et bijectivement} la proposition pr\'e\-c\'e\-dente. On
obtiendrait ainsi une d\'e\-mons\-tra\-tion et non plus seulement une
inter\-pr\'e\-ta\-tion de la r\'e\-cur\-rence $(*)$.

\bigskip

\eightpoint

\leftline{\pc R\'EF\'ERENCES BIBLIOGRAPHIQUES|} 

\nobreak\bigskip

\divers D1|\pd D\'ESARM\'ENIEN (J.)|Une autre interpr\'etation du
nombre de  d\'erangements, {\it S\'eminaire Lotharingien de
Combinatoire}, B08a, {\oldstyle 1983}| 

\divers D2|\pd D\'ESARM\'ENIEN (J.)|\'Etude modulo $n$ des
statistiques  mahoniennes, {\sl S\'eminaire Lotharingien de
Combinatoire}, B22a, $\oldstyle 1989$| 

\divers D--W1|\pd D\'ESARM\'ENIEN (J.) et \pd WACHS
(M.)|Descentes  sur les d\'erangements et mots circulaires, {\it
S\'eminaire Lotharingien de combinatoire}, B19a,
{\oldstyle 1988}| 

\divers D--W2|\pd D\'ESARM\'ENIEN (J.) et \pd WACHS (M.)|Derangements and 
necklaces, pr\'epublica\-tion, {\oldstyle 1989}| 

\article W|\pd WACHS (M.)|On $q$-derangement numbers|Proc. Amer. 
Math. Soc.|106|1989|273--279|

\rightline{\strut \vrule width 3cm height .4pt depth 0pt} 
\rightline{\it Institut Gaspard-Monge,} 
\rightline{\it Universit\'e Marne-la-Vall\'ee,}
\rightline{\it 93160-Noisy-le-Grand.} 

\bye

