Pour tout {n\in\mathbb{N}^*}, on pose {E_n=\{1,2,\ldots,n\}}.
Soit {S_n} l’ensemble des permutations} de {E_n}, c’est-à-dire l’ensemble des bijections de {E_n} dans lui-même.
Pour tout {f} de {S_n} et pour tout {k} de {E_n}, on dit que {k} est un point fixe} de {f} si {f(k)=k}.
On dit qu’un élément {f} de {S_n} est un dérangement} de {E_n} si {f} ne possède aucun point fixe.
On note {D_n} le nombre de dérangements de {E_n}.
Par convention, on pose {D_0=1}.
On généralise en disant qu’une bijection {f} de {A=\{a_1,a_2,\ldots,a_n\}} sur {B=\{b_1,b_2,\ldots,b_n\}} est un dérangement de {A} sur {B} (ainsi ordonnés) si pour tout {i\in\{1,\ldots,n\}}, on a {f(a_i)=b_j} où {j\ne i}.
Il est clair qu’il y a autant de dérangements de {A} sur {B} que de {E_n} dans lui-même.
Question 1. Que valent {D_1} et {D_2} ? |
Question 2. Montrer que pour tout entier {n\ge0}, on a : {(E_n):D_{n+2}=(n+1)(D_{n+1}+D_{n})}Indication : si {f} est dérangement de {E_{n+2}} considérer {k=f(n+2)} et {f(k)}. |
Question 3. En déduire que : {\forall\,n\in\mathbb{N},\;D_n=n!\displaystyle\sum_{k=0}^n\dfrac{(-1)^k}{k!}}. |
Dans les questions 4.(a) à 4.(e), on va retrouver le résultat de la question {3} mais par une autre méthode.
Pour tout entier {k\ge1}, et pour tout {q} de {\{0,\ldots,k\}}, on note {D_{k,q}} le nombre des permutations de {E_k} qui ont exactement {q} points fixes. Ainsi {D_{k,0}=D_k}.
Par convention on pose encore {D_{0,0}=1}.
Question 4.(a) Montrer que :{0\leq q\leq k\leq n\Rightarrow\dbinom nk\dbinom kq =\dbinom nq\dbinom{n-q}{k-q}} |
Question 4.(b) En déduire que, si {0\leq q\lt n}, alors :{\displaystyle\sum_{k=q}^n(-1)^k\dbinom nk\dbinom kq=0}(et si {q=n}?). |
Question 4.(c) Prouver que pour tout {k\ge0}, on a {k!=\displaystyle\sum_{r=0}^k D_{k,r}=\displaystyle\sum_{q=0}^k\dbinom{k}{q}D_q} |
Question 4.(d) Montrer que pour tout {n\ge0} : {D_n=(-1)^n\displaystyle\sum_{k=0}^n(-1)^k\dbinom{n}{k}k!} |
Question 4.(e) Retrouver ainsi le résultat de la question {3}. |
On place {n} boules discernables, dans {n} tiroirs distincts, à raison d’une boule par tiroir.
On extrait les {n} boules, puis on les replace aléatoirement (toujours une par tiroir).
On note {X} la variable aléatoire discrète représentant le nombre de boules ayant retrouvé leur tiroir d’origine.
Question 5.(a) Montrer que {\mathbb{P}(X=q)=\dfrac1{q!}\displaystyle\sum_{k=0}^{n-q}\dfrac{(-1)^k}{k!}} |
Question 5.(b) Exprimer la probabilité de l’événement {X\ge1}. |
Question 5.(c) Montrer que l’espérance de {X} est égale à {1}. On proposera deux méthodes. |
Question 5.(d) Calculer la variance de {X}. |