Exercice 18

1. Pour $n = 1$, la seule permutation est l'identité, qui a un point fixe. Pour $n = 2$, la transposition est le seul dérangement. Pour $n = 3$, une permutation sans point fixe a pour seule orbite $\llbracket 1\,,3 \rrbracket$ : c'est l'un des deux $3$-cycles $(1\,2\,3)$ et $(1\,3\,2)$. $$\boxed{D_{1} = 0, \qquad D_{2} = 1, \qquad D_{3} = 2}$$

2. Soit $F$ une partie à $k$ éléments de $\llbracket 1\,,n \rrbracket$. Si $\sigma$ est une permutation dont l'ensemble des points fixes est exactement $F$, alors $\sigma(F) = F$, donc $\sigma$ envoie aussi le complémentaire $\overline{F}$ sur lui-même, puisqu'elle est bijective ; sa restriction à $\overline{F}$ est une permutation de $\overline{F}$ sans point fixe. Réciproquement, un dérangement de $\overline{F}$, prolongé par l'identité sur $F$, est une permutation dont l'ensemble des points fixes est $F$. Il y a donc $D_{n-k}$ telles permutations, puisque $\overline{F}$ a $n - k$ éléments, et $\binom{n}{k}$ choix de $F$. $$\boxed{\binom{n}{k}D_{n-k} \text{ permutations de } \llbracket 1\,,n \rrbracket \text{ ont exactement } k \text{ points fixes}}$$

3. Les permutations se répartissent selon leur nombre $k \in \llbracket 0\,,n \rrbracket$ de points fixes. La proposition 2 (i), puis le changement d'indice $j = n - k$ et la symétrie $\binom{n}{n - j} = \binom{n}{j}$ donnent $$\boxed{n! = \sum_{k=0}^{n} \binom{n}{k}D_{n-k} = \sum_{j=0}^{n} \binom{n}{j}D_{j}}$$ La relation détermine $D_{n}$ à partir de $D_{0}$, …, $D_{n-1}$, puisque le coefficient de $D_{n}$ vaut $1$ : $$D_{4} = 24 - \big(1 + 4 \times 0 + 6 \times 1 + 4 \times 2\big) = 9, \qquad D_{5} = 120 - \big(1 + 0 + 10 \times 1 + 10 \times 2 + 5 \times 9\big) = 44.$$

4. Posons $E_{n} = \sum_{k=0}^{n} (-1)^{n-k}\binom{n}{k}k!$ pour $n \in \mathbb{N}$, et montrons d'abord que la suite $(E_{n})$ vérifie la même relation que $(D_{n})$. Soit $n \in \mathbb{N}$. En intervertissant les sommes triangulaires (chapitre 3, proposition 8), puis en utilisant l'égalité de l'énoncé, qui se vérifie en écrivant les deux membres avec des factorielles, $$\sum_{k=0}^{n} \binom{n}{k}E_{k} = \sum_{k=0}^{n}\,\sum_{j=0}^{k} (-1)^{k-j}\binom{n}{k}\binom{k}{j}j! = \sum_{j=0}^{n} j!\binom{n}{j}\sum_{k=j}^{n} (-1)^{k-j}\binom{n - j}{k - j}.$$ Avec $i = k - j$ et $m = n - j$, la somme intérieure vaut $\sum_{i=0}^{m} (-1)^{i}\binom{m}{i} = (1 - 1)^{m}$ par la formule du binôme : elle est nulle pour $m \geqslant 1$ et vaut $1$ pour $m = 0$, c'est-à-dire $j = n$. Il reste $$\sum_{k=0}^{n} \binom{n}{k}E_{k} = n!\binom{n}{n} = n!.$$ On montre alors par récurrence forte que $D_{n} = E_{n}$. On a $D_{0} = 1 = E_{0}$. Si $D_{k} = E_{k}$ pour tout $k \leqslant n - 1$, avec $n \geqslant 1$, les relations vérifiées par les deux suites donnent $$D_{n} = n! - \sum_{k=0}^{n-1} \binom{n}{k}D_{k} = n! - \sum_{k=0}^{n-1} \binom{n}{k}E_{k} = E_{n}.$$

$$\boxed{D_{n} = \sum_{k=0}^{n} (-1)^{n-k}\binom{n}{k}k! = n!\sum_{i=0}^{n} \frac{(-1)^{i}}{i!}}$$ La seconde forme s'obtient en écrivant $\binom{n}{k}k! = \frac{n!}{(n - k)!}$ et en posant $i = n - k$. Pour $n = 4$, on retrouve $24 - 24 + 12 - 4 + 1 = 9$ ✓. La remarque de la section 21.6.3 obtient la même probabilité $\frac{D_{n}}{n!}$ par la formule du crible. Le passage d'une relation $a_{n} = \sum \binom{n}{k}b_{k}$ à $b_{n} = \sum (-1)^{n-k}\binom{n}{k}a_{k}$, que l'on vient de démontrer dans un cas particulier, s'appelle l'inversion de Pascal.

5. On numérote les hommes et les femmes de $1$ à $5$, de sorte que l'homme $i$ et la femme $i$ forment un couple légitime. Une association des danseurs est une permutation $\sigma$ de $\llbracket 1\,,5 \rrbracket$, l'homme $i$ dansant avec la femme $\sigma(i)$ ; on prend $\Omega = \mathfrak{S}_{5}$, muni de la probabilité uniforme, puisque toutes les associations sont également probables. Le nombre de couples légitimes reconstitués est le nombre de points fixes de $\sigma$, et la question 2 donne la probabilité qu'il vaille $k$ : $\frac{1}{120}\binom{5}{k}D_{5-k}$. Avec $k$ couples légitimes et $5 - k$ illégitimes, il y a plus de couples illégitimes que de légitimes si et seulement si $5 - k > k$, c'est-à-dire $k \leqslant 2$. $$\boxed{\mathrm{P}(\text{aucun couple légitime}) = \frac{D_{5}}{120} = \frac{11}{30}, \qquad \mathrm{P}(\text{un seul}) = \frac{5D_{4}}{120} = \frac{3}{8}}$$

$$\boxed{\mathrm{P}(\text{plus de couples illégitimes que de légitimes}) = \frac{D_{5} + 5D_{4} + 10D_{3}}{120} = \frac{44 + 45 + 20}{120} = \frac{109}{120}}$$ La probabilité $\frac{11}{30} \approx 0{,}367$ est déjà très proche de sa limite $\frac{1}{\mathrm{e}} \approx 0{,}368$, comme le notait le cours. Celle de l'événement contraire de la dernière question, $\frac{11}{120}$, se lit directement : il faut au moins trois couples légitimes, soit $\binom{5}{3}D_{2} + \binom{5}{4}D_{1} + D_{0} = 10 + 0 + 1 = 11$ associations.

Piège. L'erreur la plus répandue, à la question 2, est d'écrire $\binom{n}{k}(n - k)!$ : on choisit les $k$ points fixes, puis on permute les autres éléments n'importe comment. Mais une permutation quelconque des $n - k$ autres éléments peut avoir des points fixes supplémentaires, et l'on compterait les permutations ayant au moins $k$ points fixes, chacune plusieurs fois. Il faut un dérangement du complémentaire.