Problème — La formule des dérangements

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 $\sigma (1)\sigma (2)\sigma (3)\sigma (4)$, les dérangements sont $$2143,2341,2413,3142,3412,3421,4123,4312,4321.$$ On les obtient sans en oublier : $\sigma (1)=2$ donne $2143$, $2341$, $2413$ (si $\sigma (2)=1$, il reste à déranger $\{3,4\}$ ; si $\sigma (2)=3$, alors $\sigma (3)\ne 3$ impose $\sigma (3)=4$ puis $\sigma (4)=1$ ; si $\sigma (2)=4$, alors $\sigma (3)=1$ et $\sigma (4)=3$), et les cas $\sigma (1)=3$ et $\sigma (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$.

2) La relation triangulaire. Classons les $n!$ permutations de $\{1,\dots ,n\}$ selon leur ensemble de points fixes $F=\{i\mid \sigma (i)=i\}$, qui est une partie de $\{1,\dots ,n\}$ ; les classes sont disjointes et recouvrent tout, une permutation ayant un ensemble de points fixes et un seul.

La classe de $F$. Soit $\sigma$ dont l'ensemble des points fixes est exactement $F$, et $G=\{1,\dots ,n\}\setminus F$ son complémentaire. Pour $i\in G$, on a $\sigma (i)\ne i$, et $\sigma (i)\in G$ : si l'on avait $\sigma (i)=j\in F$, alors $\sigma (j)=j=\sigma (i)$ et l'injectivité donnerait $i=j\in F$, contradiction. Donc $\sigma$ induit une permutation de $G$, sans point fixe : un dérangement de $G$. Réciproquement, un dérangement de $G$, prolongé par l'identité sur $F$, est une permutation de $\{1,\dots ,n\}$ dont l'ensemble des points fixes est exactement $F$. Cette correspondance est bijective : la classe de $F$ a $d_{|G|}=d_{n-|F|}$ éléments — le nombre de dérangements ne dépend que du cardinal, $G$ étant en bijection avec $\{1,\dots ,n-|F|\}$.

Le comptage. Il y a $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ parties $F$ à $k$ éléments, chacune de classe de cardinal $d_{n-k}$. Par le principe d'addition, $$n!=\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)d_{n-k}.$$ Contrôle pour $n=4$ : $d_4+4d_3+6d_2+4d_1+d_0=9+8+6+0+1=24$.

3) La même relation pour $e_n$. Pour $m\ge 1$, la formule du binôme avec $a=-1$ et $b=1$ donne $\sum _{j=0}^m\left(\genfrac{}{}{0ex}{}{m}{j}\right)(-1{)}^j=(-1+1{)}^m=0$ ; pour $m=0$, la somme vaut $1$. Calculons maintenant, en utilisant $\left(\genfrac{}{}{0ex}{}{n}{k}\right)(n-k)!=\frac{n!}{k!}$ : $$\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)e_{n-k}=\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)(n-k)!\sum _{j=0}^{n-k}\frac{(-1{)}^j}{j!}=n!\sum _{k=0}^n\sum _{j=0}^{n-k}\frac{(-1{)}^j}{k!j!}.$$ La somme double porte sur les couples $(k,j)$ d'entiers naturels avec $k+j\le n$. Regroupons-les selon $m=k+j$, qui varie de $0$ à $n$ — une partition de l'ensemble des couples, sommation par diagonales du chapitre 2 : $$\sum _{k=0}^n\sum _{j=0}^{n-k}\frac{(-1{)}^j}{k!j!}=\sum _{m=0}^n\sum _{k=0}^m\frac{(-1{)}^{m-k}}{k!(m-k)!}=\sum _{m=0}^n\frac{1}{m!}\sum _{k=0}^m\left(\genfrac{}{}{0ex}{}{m}{k}\right)(-1{)}^{m-k}=\sum _{m=0}^n\frac{(1-1{)}^m}{m!}.$$ Tous les termes sont nuls sauf $m=0$, qui vaut $1$. Donc $\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)e_{n-k}=n!$ : la suite $(e_n)$ vérifie la même relation triangulaire que $(d_n)$.

4) La récurrence forte. Montrons $d_n=e_n$ pour tout $n$. Initialisation : $d_0=1$ et $e_0=0!\cdot 1=1$. Hérédité : soit $n\ge 1$ tel que $d_i=e_i$ pour tout $i<n$. Isolons le terme $k=0$ dans les deux relations : $$n!=d_n+\sum _{k=1}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)d_{n-k},n!=e_n+\sum _{k=1}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)e_{n-k}.$$ Pour $k\ge 1$, on a $n-k<n$, donc $d_{n-k}=e_{n-k}$ par hypothèse de récurrence : les deux sommes sont égales, et par différence $d_n=e_n$. D'où, pour tout $n$, $$d_n=n!\sum _{k=0}^n\frac{(-1{)}^k}{k!}=n!\left(1-\frac{1}{1!}+\frac{1}{2!}-\cdots +\frac{(-1{)}^n}{n!}\right).$$ Le point délicat. La relation triangulaire détermine la suite : $d_n$ s'exprime en fonction des $d_i$ précédents, et deux suites qui la vérifient avec le même terme initial coïncident. On n'a jamais compté les dérangements directement, on a exhibé une suite candidate et vérifié qu'elle satisfait la même relation. Contrôle : $e_4=24\left(1-1+\frac{1}{2}-\frac{1}{6}+\frac{1}{24}\right)=12-4+1=9=d_4$.

5) Deux récurrences. De la formule, pour $n\ge 1$, en isolant le dernier terme : $$d_n=n\cdot (n-1)!\sum _{k=0}^{n-1}\frac{(-1{)}^k}{k!}+n!\frac{(-1{)}^n}{n!}=n{d}_{n-1}+(-1{)}^n.$$ Puis, pour $n\ge 2$, écrivons $d_n=(n-1)d_{n-1}+d_{n-1}+(-1{)}^n$ et remplaçons $d_{n-1}$ par $(n-1)d_{n-2}+(-1{)}^{n-1}$ dans le second : $d_{n-1}+(-1{)}^n=(n-1)d_{n-2}+(-1{)}^{n-1}+(-1{)}^n=(n-1)d_{n-2}$. Donc $$d_n=(n-1)d_{n-1}+(n-1)d_{n-2}=(n-1)(d_{n-1}+d_{n-2}).$$ Elle permet un calcul rapide : $d_4=3(2+1)=9$, $d_5=4(9+2)=44$, $d_6=5(44+9)=265$, $d_7=6(265+44)=1854$. (Cette seconde récurrence a une lecture combinatoire, qu'on indique sans la détailler : un dérangement envoie $n$ sur l'un des $n-1$ autres éléments, disons $i$ ; ou bien $\sigma (i)=n$, et $\sigma$ échange $i$ et $n$ tout en dérangeant les $n-2$ autres ; ou bien $\sigma (i)\ne n$, et en envoyant l'antécédent de $n$ sur $i$ au lieu de $n$, on obtient un dérangement de $\{1,\dots ,n\}\setminus \{n\}$, de façon bijective.)

6) La limite. D'après 4), $\frac{d_n}{n!}=\sum _{k=0}^n\frac{(-1{)}^k}{k!}$, somme partielle de la série exponentielle en $z=-1$ : par le théorème du chapitre 17, $e^z=\sum _{k\ge 0}\frac{z^k}{k!}$, elle converge vers $e^{-1}$. Donc $$\frac{d_n}{n!}\underset{n\to +\infty }{\to }\frac{1}{e}\approx 0,3679.$$ Mieux : la série est alternée et $\frac{1}{k!}$ décroît vers $0$, donc l'écart entre $\frac{d_n}{n!}$ et $\frac{1}{e}$ est majoré par le premier terme négligé, $\frac{1}{(n+1)!}$ ; en multipliant par $n!$, $\left|d_n-\frac{n!}{e}\right|\le \frac{1}{n+1}<\frac{1}{2}$ dès que $n\ge 2$ : $d_n$ est l'entier le plus proche de $\frac{n!}{e}$. Contrôle : $\frac{5!}{e}\approx 44,15$ et $d_5=44$ ; $\frac{7!}{e}\approx 1854,1$ et $d_7=1854$.

L'interprétation. Si l'on rend au hasard $n$ chapeaux à leurs $n$ propriétaires, la proportion des façons de le faire où personne ne retrouve son chapeau est $\frac{d_n}{n!}$ : $\frac{1}{2}$ pour $n=2$, $\frac{1}{3}$ pour $n=3$, $\frac{9}{24}=0,375$ pour $n=4$, $0,367$ pour $n=5$, puis $0,368$ à trois décimales près pour tout $n\ge 6$. Contrairement à l'intuition, cette proportion ne tend pas vers $0$ quand le nombre de chapeaux grandit : elle se stabilise à $\frac{1}{e}$, plus d'un tiers, quel que soit $n\ge 4$.

Le théorème obtenu — la formule des dérangements. Le nombre de permutations de $n$ objets sans point fixe est $d_n=n!\sum _{k=0}^n\frac{(-1{)}^k}{k!}$, entier le plus proche de $\frac{n!}{e}$ ; la proportion $\frac{d_n}{n!}$ tend vers $\frac{1}{e}$. C'est le problème des rencontres, posé par Montmort en 1708 à propos d'un jeu de cartes, et résolu par lui et par Euler.

Ce que le problème installe. Deux idées. Une partition selon un invariant — ici l'ensemble des points fixes — donne une relation entre les nombres cherchés et les coefficients binomiaux, et cette relation triangulaire suffit à les déterminer : on ne compte pas, on identifie. Et le binôme évalué en $(1-1{)}^m$, qui vaut $0$ sauf pour $m=0$, est l'outil qui « inverse » ce type de relation — c'est, sous une forme élémentaire, ce que la formule du crible, hors programme, systématise. Le chapitre 19 reprendra ce problème mot pour mot, comme la probabilité qu'une permutation aléatoire n'ait aucun point fixe.