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 : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
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 : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).

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 : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
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 : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
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 : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
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 : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
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 : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).

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 : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
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 : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
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 : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
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 : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).