mathématiques (terminale) · Chapitre 7 · Exercice de TD

Problème — Le problème des dérangements (du vestiaire)

Combinatoire et Dénombrement · niveau 3 (difficile)

Énoncé

Problème — Le problème des dérangements (du vestiaire).

Quatre personnes déposent leur chapeau au vestiaire d'un restaurant. En repartant, le responsable leur remet au hasard un chapeau parmi les quatre. On s'intéresse au nombre de façons de distribuer les quatre chapeaux de telle sorte que personne ne reçoive son propre chapeau. Une telle configuration s'appelle un dérangement de l'ensemble ${1, 2, 3, 4}$ .

Justifier que le nombre total de façons de distribuer les 4 chapeaux aux 4 personnes est $4!$ .
Pour tout entier $i \in {1, 2, 3, 4}$ , on note $A_{i}$ l'ensemble des distributions dans lesquelles la personne $i$ récupère son propre chapeau.

Déterminer $Card (A_{1})$ .
Déterminer $Card (A_{1} \cap A_{2})$ .
De manière générale, pour $k$ personnes fixées ( $1 \leq k \leq 4$ ), quel est le cardinal de l'intersection de leurs ensembles $A_{i}$ correspondants ?

On souhaite utiliser le principe d'inclusion-exclusion pour calculer le nombre de distributions dans lesquelles au moins une personne récupère son chapeau, soit $Card (A_{1} \cup A_{2} \cup A_{3} \cup A_{4})$ . La formule pour 4 ensembles est :

$Card (A_{1} \cup A_{2} \cup A_{3} \cup A_{4}) = i = 1 \sum 4 Card (A_{i}) - 1 \leq i < j \leq 4 \sum Card (A_{i} \cap A_{j}) + 1 \leq i < j < k \leq 4 \sum Card (A_{i} \cap A_{j} \cap A_{k}) - Card (A_{1} \cap A_{2} \cap A_{3} \cap A_{4})$

Calculer le nombre de termes dans la deuxième somme et dans la troisième somme.
Calculer la valeur numérique de chacun des termes de la formule et montrer que :

$Card (A_{1} \cup A_{2} \cup A_{3} \cup A_{4}) = 15$

En déduire le nombre de dérangements possibles pour $n = 4$ personnes.
Généralisation : On admet que pour $n$ personnes, le nombre de dérangements est donné par la formule :

$D_{n} = n! k = 0 \sum n \frac{( - 1 ) ^{k}}{k !}$

Vérifier que la formule donne bien la même valeur pour $n = 4$ .

Corrigé

Distribuer 4 chapeaux distincts à 4 personnes distinctes correspond à ordonner les chapeaux, ce qui équivaut à une permutation des 4 éléments. Le nombre total de distributions est :

$4! = 24$

Calculons les cardinaux :

Dans $A_{1}$ , la personne 1 reçoit son chapeau 1. Il reste à distribuer les 3 autres chapeaux aux 3 autres personnes de manière quelconque. Il y a donc $3! = 6$ façons. D'où $Card (A_{1}) = 6$ . (Par symétrie, c'est aussi le cas pour $A_{2}, A_{3}, A_{4}$ ).

Dans $A_{1} \cap A_{2}$ , la personne 1 reçoit son chapeau 1 et la personne 2 reçoit son chapeau 2. Il reste à distribuer les 2 chapeaux restants aux 2 personnes restantes. Il y a $2! = 2$ façons. D'où $Card (A_{1} \cap A_{2}) = 2$ .

De manière générale, si $k$ personnes reçoivent leur propre chapeau, les positions de ces $k$ chapeaux sont fixées. Il reste alors à distribuer librement les $4 - k$ chapeaux restants aux $4 - k$ personnes restantes. Le nombre de distributions correspondantes est donc :

$(4 - k)!$

Calculons la réunion par le principe d'inclusion-exclusion :

Le nombre de termes dans la première somme est $(1 4) = 4$ . La deuxième somme porte sur les couples d'indices ${i, j}$ tels que $1 \leq i < j \leq 4$ : elle compte $(2 4) = 6$ termes. La troisième somme porte sur les triplets ${i, j, k}$ tels que $1 \leq i < j < k \leq 4$ : elle compte $(3 4) = 4$ termes.

Évaluons chaque somme :

$\sum_{i = 1}^{4} Card (A_{i}) = (1 4) \times 3! = 4 \times 6 = 24$ ;
$\sum_{1 \leq i < j \leq 4} Card (A_{i} \cap A_{j}) = (2 4) \times 2! = 6 \times 2 = 12$ ;
$\sum_{1 \leq i < j < k \leq 4} Card (A_{i} \cap A_{j} \cap A_{k}) = (3 4) \times 1! = 4 \times 1 = 4$ ;
$Card (A_{1} \cap A_{2} \cap A_{3} \cap A_{4}) = (4 4) \times 0! = 1 \times 1 = 1$ .

En injectant ces valeurs dans la formule :

$Card (A_{1} \cup A_{2} \cup A_{3} \cup A_{4}) = 24 - 12 + 4 - 1 = 15$

Un dérangement est une distribution où personne ne reçoit son propre chapeau. C'est l'ensemble complémentaire de l'événement « au moins une personne reçoit son propre chapeau ». Le nombre de dérangements est donc :

$D_{4} = Total - Card (A_{1} \cup A_{2} \cup A_{3} \cup A_{4}) = 24 - 15 = 9$

Il y a 9 dérangements possibles.

Pour $n = 4$ , la formule donne :

$D_{4} = 4! k = 0 \sum 4 \frac{( - 1 ) ^{k}}{k !} = 24 (\frac{( - 1 ) ^{0}}{0 !} + \frac{( - 1 ) ^{1}}{1 !} + \frac{( - 1 ) ^{2}}{2 !} + \frac{( - 1 ) ^{3}}{3 !} + \frac{( - 1 ) ^{4}}{4 !}) = 24 (1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24}) = 24 (\frac{12 - 4 + 1}{24}) = 9$

La formule donne bien 9, ce qui confirme son exactitude.

100 % gratuit

Essaie le suivant avec le tuteur

Faire l'exercice suivant avec le tuteur

Sans compte : le cours, le premier QCM, 2 minutes de podcast et de vidéo et un exercice avec le tuteur. Pour tout le reste : inscription gratuite en 30 secondes, sans carte bancaire.

Le cours du chapitre · Tous les exercices du chapitre

Exercice suivant avec le tuteur →