mathématiques MPSI · Chapitre 18 · Exercice de TD

Problème — La formule des dérangements

Dénombrement · D. Problèmes et doubles comptages · niveau 3 (difficile)

Énoncé

Une permutation $σ$ de ${1, \dots, n}$ est un dérangement si elle n'a aucun point fixe : $σ (i) \neq = i$ pour tout $i$ . On note $d_{n}$ le nombre de dérangements de ${1, \dots, n}$ , avec la convention $d_{0} = 1$ .

1) Calculer $d_{1}$ , $d_{2}$ , $d_{3}$ , puis $d_{4}$ en listant.

2) Classer les permutations de ${1, \dots, n}$ selon leur ensemble de points fixes ; en déduire $n! = k = 0 \sum n (k n) d_{n - k}$ .

3) Pour $m \geq 1$ , rappeler pourquoi $j = 0 \sum m (j m) (- 1)^{j} = 0$ . On pose $e_{n} = n! k = 0 \sum n \frac{( - 1 ) ^{k}}{k !}$ ; montrer que $k = 0 \sum n (k n) e_{n - k} = n!$ (on regroupera selon $m = k + j$ ).

4) En déduire, par récurrence forte, $d_{n} = e_{n}$ pour tout $n$ : c'est la formule des dérangements.

5) En déduire $d_{n} = n d_{n - 1} + (- 1)^{n}$ pour $n \geq 1$ , puis $d_{n} = (n - 1) (d_{n - 1} + d_{n - 2})$ pour $n \geq 2$ .

6) Montrer que $\frac{d _{n}}{n !} \to \frac{1}{e}$ , et interpréter.

Corrigé de la question 1

1) Les premières valeurs. $d_{1} = 0$ : la seule permutation de ${1}$ est l'identité, qui fixe $1$ . $d_{2} = 1$ : sur ${1, 2}$ , l'identité fixe tout et la transposition qui échange $1$ et $2$ ne fixe rien. $d_{3} = 2$ : les six permutations de ${1, 2, 3}$ sont l'identité, les trois transpositions, qui fixent chacune un élément, et les deux permutations circulaires $1 \mapsto 2 \mapsto 3 \mapsto 1$ et $1 \mapsto 3 \mapsto 2 \mapsto 1$ , sans point fixe. $d_{4} = 9$ : en écrivant une permutation par le mot $σ (1) σ (2) σ (3) σ (4)$ , les dérangements sont $2143, 2341, 2413, 3142, 3412, 3421, 4123, 4312, 4321.$ On les obtient sans en oublier : $σ (1) = 2$ donne $2143$ , $2341$ , $2413$ (si $σ (2) = 1$ , il reste à déranger ${3, 4}$ ; si $σ (2) = 3$ , alors $σ (3) \neq = 3$ impose $σ (3) = 4$ puis $σ (4) = 1$ ; si $σ (2) = 4$ , alors $σ (3) = 1$ et $σ (4) = 3$ ), et les cas $σ (1) = 3$ et $σ (1) = 4$ en donnent trois chacun, par symétrie : renommer $2$ en $3$ dans tout le tableau échange les deux premiers cas sans créer ni détruire de point fixe. Ce sont les trois doubles échanges et les six permutations circulaires d'ordre $4$ .

Question 2 : comment l'IA t'aide

2) Classer les permutations de ${1, \dots, n}$ selon leur ensemble de points fixes ; en déduire $n! = k = 0 \sum n (k n) d_{n - k}$ .

Élève

Je regroupe les permutations selon leur nombre $k$ de points fixes : $(k n)$ choix des points fixes, et ensuite le reste devrait être un dérangement des $n - k$ autres éléments. Mais je n'arrive pas à le justifier.

Fixe l'ensemble $F$ des points fixes et son complémentaire $G$ . Pour $i \in G$ , tu sais que $σ (i) \neq = i$ ; mais pourquoi $σ (i)$ ne peut-il pas tomber dans $F$ ?

Élève

Si $σ (i) = j$ avec $j \in F$ , alors $σ (j) = j = σ (i)$ , et l'injectivité donne $i = j$ , ce qui est impossible. Donc $σ$ envoie $G$ dans $G$ .

Ainsi $σ$ induit une permutation de $G$ sans point fixe. Réciproquement, comment reconstruis-tu $σ$ à partir d'un dérangement de $G$ , et pourquoi le nombre de dérangements de $G$ ne dépend-il que du cardinal de $G$ ?

L'IA ne donne pas la réponse : elle pose la question qui fait avancer. À toi de continuer.

Continue cet exercice avec l'IA

Reprends la question 2 là où le dialogue s'arrête, puis la suite de l'exercice.

Continuer avec l'IA — gratuit, sans inscription

Gratuit, sans inscription. L'IA te guide pas à pas, sans te donner la réponse.

Le cours du chapitre · Tous les exercices du chapitre

Continuer avec l'IA, gratuit →