
\catcode'32=9
\magnification=1200

%\voffset=1cm
%\hoffset=0cm

\font\tenpc=cmcsc10

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

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

% Chargement des fontes AMS
\font\tengoth=eufm10
\font\tenbboard=msbm10
\font\eightgoth=eufm7 at 8pt
\font\eightbboard=msbm7 at 8pt
\font\sevengoth=eufm7
\font\sevenbboard=msbm7
\font\sixgoth=eufm5 at 6 pt
\font\fivegoth=eufm5

\font\tengoth=eufm10
\font\tenbboard=msbm10
\font\eightgoth=eufm7 at 8pt
%%%%%%%%%%%%\font\eightbboard=msbm8%%%%% manque
\font\eightbboard=msbm7 at 8pt
\font\sevengoth=eufm7
\font\sevenbboard=msbm7
%%%%%%%%%%%%\font\sixgoth=eufm6%%%%%%%%% manque
\font\sixgoth=eufm5 at 6 pt
\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

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


%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}, vol.\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\cqfd{\penalty 500 \hbox{\qed}\par\smallskip}

\catcode`\@=12

%fin du format

%Quelques macros
%%%%%%%%%%%%%%%%%%%%%%%%\input tex8bits

\def\L{\mathop{\rm L\kern 0pt}}
\titrecourant={INTERPR\'ETATION DU NOMBRE DE D\'ERANGEMENTS}
\auteurcourant={J. D\'ESARM\'ENIEN}

{\eightpoint
\noindent
S\'eminaire Lotharingien de Combinatoire, B08b, 1982, 6 pp.

\noindent
[Formerly: Publ. I.R.M.A. Strasbourg, 1984, 229/S-08

\noindent
Actes 8e S\'eminaire Lotharingien, p. 11-16.]

}

\vglue 1.5cm
\vskip0pt  minus 12pt
\centerline{\bf  UNE AUTRE INTERPR\'ETATION}
\vskip1.8mm
\centerline{\bf DU NOMBRE DE D\'ERANGEMENTS}
\vskip 2.8mm
\centerline{\sevenrm PAR}
\vskip 2.8mm
\centerline{{\petcap Jacques} D\'ESARM\'ENIEN}

\vskip .6cm
\section 1. Introduction|L'\'enum\'eration des d\'erangements (ou
permutations sans points fixes) est un exercice classique de
combinatoire remontant au 18e si\`ecle (le probl\`eme des rencontres de
Montmort [7]), expos\'e en d\'etail par exemple par Comtet [1]. Deux
articles r\'ecents de Garsia et Remmel et de Remmel [4, 9] ont
renouvel\'e l'int\'er\^et pour ce probl\`eme ; le premier en fournissant un
mod\`ele pour une $q$-extension du nombre de d\'erangements, le second
en montrant comment ce mod\`ele permet d'interpr\'eter la formule de
r\'ecurrence $d_n = nd_{n-1} + (-1)^n$ pour laquelle le mod\`ele
classique des permutations sans points fixes ne fournit pas de
d\'emonstration bijective imm\'ediate.

Nous fournissons un mod\`ele diff\'erent de celui de Garsia et Remmel
pour lequel la r\'ecurrence mentionn\'ee est imm\'ediate et qui pr\'esente
d'autres int\'er\^ets : il est constitu\'e de permutations de {\it forme}
({\it up-down sequence}) donn\'ee ; on sait gr\^ace \`a Foata et
Sch\"utzenberger [3] que les
$q$-d\'enombrements des inversions et de l'indice majeur inverse
co\"\i ncident dans ce cas, et, comme nous l'avons d\'evelopp\'e dans [2],
donnent naissance \`a des fonctions de Schur d'o\`u d\'erivent \`a leur
tour de nombreuses propri\'et\'es alg\'ebriques et arithm\'etiques. De plus,
contrairement au mod\`ele de Garsia et Remmel, il est susceptible
d'\^etre \'etendu aux permutations quelconques, prenant en charge le
param\`etre suppl\'ementaire nombre de points fixes.

Finalement, comme nous a fait remarquer Knuth, il existe une similitude
entre notre mod\`ele et un probl\`eme de g\'en\'eration de variables
al\'eatoires de distribution exponentielle \'etudi\'e par von Neumann, dont une
g\'en\'eralisation est d\'ecrite par Knuth [5]. Le lien entre notre mod\`ele
et le probl\`eme de von Neumann est \'etabli au moyen d'un codage classique des
permutations d\^u \`a Lehmer.

\section   2. Le probl\`eme des d\'erangements|Notons ${\cal D}_n$
l'ensemble des permutations de $[n]$ sans point fixe. Il s'agit de
calculer le nombre d'\'el\'ements $d_n$ de ${\cal D}_n$

\goodbreak
On obtient tr\`es facilement, par un argument
d'inclusion-exclusion, la formule explicite suivante :
$$
\eqalign{
d_n&= n!-n(n-1)! +{n\choose 2} (n-2)!-\cdots
+(-1)^n{n\choose n} 0!\cr
&=\sum_{0\le k\le n}(-1)^k{n!\over k!},\cr}
$$
\`a partir de laquelle on obtient le r\'esultat asymptotique bien connu :
$$
\lim_{n\rightarrow +\infty} {d_n\over n!}={1\over e}.
$$
dont une interpr\'etation est que la probabilit\'e qu'une permutation
choisie uniform\'ement parmi toutes les permutations soit un
d\'erangement est asymptotiquement \'egale \`a $1/e$.

On en d\'eduit aussi la fonction g\'en\'eratrice :
$$
D(x)=\sum_{n\ge 0} d_n{x^n\over n!}={e^{-x}\over 1-x}
$$
ainsi que
la formule de r\'ecurrence de la proposition suivante.

\th Proposition 1|Le nombre de d\'erangements sur $n$ lettres est
donn\'e par la r\'ecurrence :
$$\eqalign{d_0&= 1,\cr
d_n& = nd_{n-1} + (-1)^n\qquad (n\ge 1).\cr}
$$
\finth

Il semble curieux qu'une formule de r\'ecurrence aussi simple ne
puisse \^etre interpr\'et\'ee de fa\c con directe \`a partir de la
d\'efinition des d\'erangements.

\section 2. Le mod\`ele|Garsia et Remmel [4] \'etudient une classe de
permutations, dont ils montrent qu'elles sont en bijection avec
les d\'erangements et dont Remmel [9] a montr\'e que leur nombre
satisfaisait la r\'ecurrence de la proposition 1 par des m\'ethodes
purement bijectives. N\'eanmoins, la classe de permutations ainsi mise
en \'evidence est caract\'eris\'ee par leur bijection avec les
d\'erangements.

Le mod\`ele que nous proposons, qui est diff\'erent de celui de Garsia et
Remmel, peut \^etre en revanche d\'efini {\it a priori}.

Soit $\sigma =\sigma (1)\sigma (2)\ldots \sigma (n)$ une permutation.
On appelle {\it creux} de $\sigma $ un entier $i$, $1\le i\le n$ tel que
$$
\sigma (i-1) > \sigma (i) < \sigma (i + 1).
$$
(Par convention, on convient que $\sigma (0) = \sigma (n + 1) = +\infty $ .)

On note alors ${\cal K}_n$ l'ensemble des permutations de $[n]$ dont le plus
petit creux (que nous appellerons {\it premier creux}) est {\it pair}.

D\'efinissons maintenant une application $f$ de ${\cal D}_n$ sur l'ensemble
${\cal S}_n$ de toutes les permutations. Pour cela, partons d'un d\'erangement
$\delta $, que nous d\'ecomposons en produit de cycles. Ces cycles sont
\'ecrits par ordre {\it d\'ecroissant} de leur plus petit \'el\'ement ; ce plus
petit \'el\'ement est plac\'e dans chaque cycle en {\it seconde} position.
(On remarque que ceci est possible,
puisque $\delta $ n'a aucun cycle de longueur 1.) La permutation
$f(\delta )$ est obtenue en enlevant les parenth\`eses dans ce dernier mot.

\rem Exemple|Partons du d\'erangement :
$$
\delta = 974382651
$$
dont la d\'ecomposition en cycles est :
$$
(19)(276)(34)(58).
$$
Apr\`es r\'eordonnement des cycles, on obtient :
$$
(85)(43)(627)(91)
$$
Par cons\'equent,
$$
f(\delta ) = 854362791.
$$

\th Proposition 2|L'application f est une bijection de ${\cal D}_n$ sur
${\cal K}_n$.
\finth

On remarque tout d'abord qu'un creux de $f(\delta )$ correspond
n\'eces\-sai\-re\-ment au plus petit \'el\'ement d'un cycle de $\delta $.
R\'eciproquement, au plus petit \'el\'ement d'un cycle de $\delta $
correspond un creux de $f(\delta )$ sauf s'il se trouve dans un cycle
de longueur 2 et est plus petit que le premier \'el\'ement du cyle suivant
apr\`es r\'eordonnement.

Il s'ensuit que les cycles de $\delta $ qui pr\'ec\`edent l'\'el\'ement
correspondant au premier creux de $f(\delta )$ sont de longueur 2. Par
cons\'equent, le premier creux de $f(\delta )$ est pair.

Pour voir que $f$ est une bijection, il suffit de v\'erifier que
l'application $g$ d\'efinie ci-apr\`es est l'inverse de $f$, ce qui ne pose
pas de difficult\'es particuli\`eres.

Pour d\'efinir $g$, on part d'un \'el\'ement $\tau $ de ${\cal K}_n$.
On lit $\tau $ de droite \`a gauche jusqu'\`a lire 1. Le cycle de $g(\tau )$
auquel 1 appartient est constitu\'e de l'\'el\'ement \`a gauche de 1,
de 1 et de tous les \'el\'ements suivant 1 \`a droite de celui-ci,
dans cet ordre. On r\'ep\`ete cette op\'eration sur ce qui reste de $\tau $
apr\`es qu'on en a enlev\'e le cycle pr\'ec\'edemment d\'etect\'e, en
rempla\c cant 1 par le plus petit \'el\'ement restant. On remarque ici
que le fait que le premier creux de $\tau $ soit pair assure que ce plus
petit \'el\'ement ne se trouve jamais en premi\`ere position.

Si on note $k_n$ le nombre d'\'el\'ements de ${\cal K}_n$, on sait
maintenant que l'on a $k_n = d_n$. On va alors interpr\'eter bijectivement
la r\'ecurrence de la proposition~1 \'ecrite pour les entiers $k_n$.

\rem Interpr\'etation de la proposition $1$|Partons d'une
permutation $\tau  = \tau (1)\tau (2)\ldots \tau (n)$ dans ${\cal K}_n$.
On lui associe la permutation $\varphi (\tau )$ dans ${\cal S}_{n-1}$ par :
$$
\varphi (\tau )(k) = \cases{\tau (k) &si $\tau (k) < \tau (n)$,\cr
                            \tau (k)-1 &si $\tau (k) > \tau (n)$,\cr}
$$
o\`u $1\le k\le n-1$.

On remarque que, en g\'en\'eral, le premier creux de $\tau $ reste le premier
creux de $\varphi (\tau )$. Le seul cas o\`u il n'en est pas ainsi est
lorsque $n$ est pair et $\tau = n\,n-1\ldots 2\,1$. Dans ce cas, le premier creux
de $\varphi (\tau )$ vaut $n-1$ qui est impair. Dans tous les autres cas,
$\varphi (\tau )$ est dans ${\cal K}_n$.

L'application $\psi $ qui \`a $\tau \in{\cal K}_n$ associe le couple
$(\varphi (\tau ), \tau (n))$ envoie donc ${\cal K}_n$ dans
${\cal K}_{n-1}\times [n]$ si $n$ est impair et dans
${\cal K}_{n-1}\times[n]\cup \{((n-1\ldots 2\,1),1)\}$ si $n$ est pair.

R\'eciproquement, partant d'un couple dans ${\cal K}_{n-1}\times [n]$,
on peut reconstruire l'unique permutation $\tau $ auquel il correspond par 
$\psi $, sauf lorsque $n$ est impair et qu'on part du couple
$((n-1\ldots 2\,1),1)$ qui devrait provenir de $\tau = n\,n-1\ldots 2\,1$
lequel a son premier creux en $n$ qui est ici impair.

On a donc \'etabli que $\psi $ est une bijection entre un ensemble de $k_n$
\'el\'ements et un ensemble de $nk_{n-1}+1$ (resp. de $nk_{n-1}-1$)
\'el\'ements si $n$ est pair (resp. si $n$ est impair).

Ceci \'etablit l'interpr\'etation combinatoire annonc\'ee de la
proposition~1.

\section 3. Le codage de Lehmer et le probl\`eme de von Neumann|Von
Neumann a indiqu\'e dans une courte note [8] une m\'ethode pour
obtenir une variable al\'eatoire de loi exponentielle \`a partir d'une
variable al\'eatoire de loi uniforme sur l'intervalle $[0,1]$. Cette
m\'ethode a \'et\'e g\'en\'eralis\'ee et est expos\'ee par exemple par
Knuth [5].
\`A l'origine, cette m\'ethode s'applique \`a des variables al\'eatoires
r\'eelles. Nous allons en pr\'esenter une version discr\`ete.

Soit une suite $T = (T_i)_{i\ge 1}$ de variables al\'eatoires ind\'ependantes
telles que $T_i$ soit \'equir\'epartie sur l'ensemble $[i]$ des entiers entre
1 et $i$. Soit $k(T)$ le plus petit entier tel que $T_i\not =1$.

\th Proposition 3|La probabilit\'e que $k(T)$ soit impair est \'egale \`a
$1/e$.
\finth

En effet, la probabilit\'e :
$$
\eqalign{P(k(T) = n) &= 1\times {1\over 2}\times \cdots \times {1\over n-1}
          \times {n-1\over n},\cr
                     &= {1\over (n-1)!}-{1\over n!}.\cr}
$$
La probabilit\'e que $k(n)$ soit impair est donc :
$$
\sum _{i\ge 0}\left({1\over (2i)!}-{1\over (2i+1)!}\right)={1\over e}.
$$

Le lien entre ce r\'esultat et notre ensemble ${\cal K}_n$ est obtenu au moyen
d'un codage de Lehmer. Celui-ci a introduit un tel codage pr\'ecis\'ement
pour produire une permutation al\'eatoire \'equir\'epartie sur ${\cal S}_n$.

Soit donc $\sigma \in {\cal S}_n$ On note :
$$
\L\sigma (i) = \mathop{\rm card}\{j : 1\le j\le i, \sigma (j)\le \sigma (i)\},
\qquad 1\le i\le n.
$$




Le mot $\L\sigma  = \L\sigma (1) \L\sigma (2)\ldots \L\sigma (n)$ est le {\it
codage de Lehmer} de $\sigma $. On constate sans peine qu'il s'agit bien l\`a d'une
bijection de ${\cal S}_n$ sur l'ensemble des suites d'entiers de longueur
$n$ dont le $i$-\`eme \'el\'ement est compris entre 1 et $i$.

\rem Exemple|Partons de la permutation :
$$
\tau = 854362791.
$$
Son codage de Lehmer est :
$$
\L\tau = 111141681.
$$

La proposition suivante est imm\'ediate, et fait le lien entre ${\cal K}_n$
et le probl\`eme de von Neumann.

\th Proposition 4|Les permutations dans ${\cal K}_n$ sont exactement celles
dont le codage de Lehmer commence par un nombre pair de $1$.
\finth

Une des applications possibles de notre mod\`ele est d'obtenir par
l'interm\'ediaire de son codage de Lehmer un \'el\'ement al\'eatoire
\'equir\'eparti de ${\cal K}_n$ et, par notre application inverse de $f$, un
d\'erangement al\'eatoire \'equir\'eparti dans ${\cal D}_n$.

\goodbreak
{\eightpoint

\centerline{BIBLIOGRAPHIE}

\bigskip
%Probleme d'espace du \'E en 8pts, reference 2
\newbox\EE \newbox\E \setbox\E=\hbox{\sl E} \setbox\EE=\hbox{\sl \'E}
\ht\EE=\ht\E

\livre 1|Comtet (L.)|Advanced combinatorics|D. Reidel, Dordrecht,
1974|

\article 2|D\'esarm\'enien (J.)|Fonctions de Schur associ\'ees \`a
des suites classiques de nombres|Ann. Scient. \box\EE cole Normale
Sup\'erieure|16|1983|271-304|

\article 3|Foata (D.) et Sch\"utzenberger
(M.-P.)|Major index and inversion number
of permutations|Math. Nachr.|83|1978|143-159|

\article 4|Garsia  (A. M.) et Remmel (J.)|A combinatorial
interpretation of $q$-derangements and $q$-Laguerre
numbers|Europ. J. Combinatorics|1|1980|47-59|

\livre 5|Knuth (D. E.)|The art of computer programming, {\rm vol. 2}:
Seminumerical algorithms|2e \'ed., Addison-Wesley, Reading, Mass.,
1981|

\divers 6|Lehmer (D. H.)|The machine tools of combinatorics,
{\sl Applied combinatorial mathematics} [E. F. Beckenbach, \'ed.], p.
5-31\pointir J. Wiley and Sons, New York,
1964, Univ. of California Engeneering and Physical Sciences
Extension Series|

\livre 7|Montmort (P.-R.)|Essai d'analyse sur les
jeux de hazard|Paris, 1708|

\article 8|von Neumann (J.)|Various
techniques used in connection with random digits|J. Res. Nat. Bur.
Stand. Appl. Math. Series|3|1951|36-38 (={\sl Collected
works}, [A. H. Taub, \'ed.], vol.~5, p.~768-770)|

\article 9|Remmel (J.)|A note on a recursion for the number of
derangements|Europ. J. Combinatorics|4|1983|371-374|

}

\bigskip\bigskip
\newbox\signe
\setbox\signe=\vtop{
\hbox{Jacques D\'ESARM\'ENIEN,}
\hbox{D\'epartement de math\'ematique,}
\hbox{Universit\'e Louis-Pasteur,}
\hbox{7, rue Ren\'e-Descartes,}
\hbox{F-67084 Strasbourg, France.}
}
\line{\hfill\box\signe\quad}

\bye
