\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