Accéder à mon compte > Accéder à ma feuille d'exercices >

Nombre de dérangements - Bibm@th.net

Exercice 1

- Nombre de dérangements [Signaler une erreur] [Ajouter à ma feuille d'exos]

Enoncé

Pour tous les entiers $k$ et $n$ tels que $n\geq 1$ et $0\leq k\leq n$, on note $D_{n,k}$ le nombre de bijections (ou permutations) $s$ de l'ensemble $\{1,\dots,n\}$ ayant $k$ points fixes, c'est-à-dire telles que $$k=\textrm{card}\big\{i\in\{1,\dots,n\};\ s(i)=i\big\}.$$ On pose $D_{0,0}=1$ et $d_n=D_{n,0}$. $d_n$ désigne le nombre de dérangements, c'est-à-dire de permutations sans point fixe.

Dresser la liste de toutes les permutations de $\{1,2,3\}$ et en déduire la valeur de $D_{3,0}$, $D_{3,1}$, $D_{3,2}$ et $D_{3,3}$.
Montrer que $n!=\sum_{k=0}^n D_{n,k}$.
Montrer que $D_{n,k}=\binom{n}{k}D_{n-k,0}$.
Montrer que la série entière $\sum_{n\geq 0}\frac{d_n}{n!}z^n$ a un rayon de convergence supérieur ou égal à 1.
On pose $f(x)=\sum_{n=0}^{+\infty}\frac{d_n}{n!}x^n$. Montrer que $(\exp x)f(x)=\frac{1}{1-x}$ pour $|x|<1$.
En déduire que $d_n=n!\sum_{k=0}^n\frac{(-1)^k}{k!}$.
Soit $p_n$ la probabilité pour qu'une permutation prise au hasard soit un dérangement. Quelle est la limite de $p_n$ quand $n$ tend vers $+\infty$?

Indication

Corrigé

Puisque $\{1,2,3\}$ a trois éléments, il existe exactement 6 bijections différentes de $\{1,2,3\}$ dans lui-même :
- l'identité;
- les 3 transpositions $(1\ 2)$, $(1\ 3)$, $(2\ 3)$.
- les 2 cycles $(1\ 2\ 3)$ et $(1\ 3\ 2)$.
L'identité a 3 points fixes, les transpositions en ont 1 et les cycles n'en ont pas. On en déduit que $$D_{3,0}=2,\ D_{3,1}=3,\ D_{3,2}=0\textrm{ et }D_{3,3}=1.$$
Si on note $A_k$ l'ensemble des permutations de $\{1,\dots,n\}$ ayant $k$ point fixes, alors les ensembles $A_0,\dots,A_n$ sont deux à deux disjoints et leur réunion est égale à l'ensemble des permutations de $\{1,\dots,n\}$. Ainsi, on a bien $n!=\sum_{k=0}^n\textrm{card}(A_k)=\sum_{k=0}^n D_{n,k}$.
Pour chaque permutation ayant $k$ points fixes, il y a
- $\binom{n}{k}$ choix possibles de ces $k$ points fixes (choisir $k$ éléments parmi $n$);
- ce choix effectué, la permutation agit comme une permutation sans point fixe sur les $n-k$ éléments restants. Il y a $D_{n-k,0}$ telles permutations.
Le nombre de permutations ayant $k$ points fixes vaut donc $\binom{n}{k}D_{n-k,0}$.
Clairement, on a $0\leq d_n\leq n!$, soit $\frac{|d_n||z|^n}{n!}\leq |z|^n$. La série converge absolument si $|z|<1$, son rayon de convergence est au moins égal à 1.
Puisque les séries entières définissant $\exp x$ et $f(x)$ ont un rayon de convergence supérieur ou égal à 1, leur produit de Cauchy est absolument convergent pour $|x|<1$. De plus, on a $$(\exp x)f(x)=\sum_{n=0}^{+\infty}b_nx^n\textrm{ avec }b_n=\sum_{k=0}^n\frac{d_{n-k}}{(n-k)!}\times\frac{1}{k!}.$$ Mais $$\sum_{k=0}^n\frac{d_{n-k}}{k!(n-k)!}=\frac{1}{n!}\sum_{k=0}^n \binom{n}{k}d_{n-k}=\frac{1}{n!}\sum_{k=0}^n D_{n,k}=1.$$ On obtient $$(\exp x)f(x)=\sum_{n=0}^{+\infty}x^n=\frac{1}{1-x}.$$
De l'égalité $(\exp x)f(x)=\frac{1}{1-x}$, on tire $$f(x)=\frac{e^{-x}}{1-x}.$$ On réalise le produit de Cauchy des deux séries entières obtenues à droite et on trouve $$f(x)=\sum_{n=0}^{+\infty}c_n x^n\textrm{ avec }c_n=\sum_{k=0}^n \frac{(-1)^k}{k!}.$$ Par identification, on obtient bien $d_n=n!\sum_{k=0}^n\frac{(-1)^k}{k!}$.
La probabilité recherchée est $p_n=d_n/n!=\sum_{k=0}^n \frac{(-1)^k}{k!}$. Utilisant le développement en série entière de $\exp(-x)$, on trouve que cette probabilité converge vers $\exp(-1)=1/e$.