Dérangements d’un ensemble fini

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}{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} ?
Cliquer ici pour voir (ou cacher) la réponse
Il n’y a qu’une application de {E_1} dans lui-même, qui est bijective, mais n’est évidemment pas un dérangement! Autrement dit : {D_1=0}.

Il y a deux permutations de {E_2} : l’identité et {f} définie par {f(1)=2} et {f(2)=1}. Seule celle-ci est un dérangement. Ainsi {D_2=1}.

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)}.
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :
Question 3.
En déduire que : {\forall\,n\in\mathbb{N},\;D_n=n!\displaystyle\sum_{k=0}^n\dfrac{(-1)^k}{k!}}.
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :

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}}
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :
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}?).
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :
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}
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :
Question 4.(d)
Montrer que pour tout {n\ge0} : {D_n=(-1)^n\displaystyle\sum_{k=0}^n(-1)^k\dbinom{n}{k}k!}
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :
Question 4.(e)
Retrouver ainsi le résultat de la question {3}.
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :

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!}}
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :
Question 5.(b)
Exprimer la probabilité de l’événement {X\ge1}.
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :
Question 5.(c)
Montrer que l’espérance de {X} est égale à {1}.
On proposera deux méthodes.
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :
Question 5.(d)
Calculer la variance de {X}.
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :