Crible de Poincaré, et application aux calculs du nombre de dérangements

En particulier, si $(A_i)_{1\leq i\leq n}$ est une partition de $E$, on a $$\textrm{card}(E)=\sum_{i=1}^n \textrm{card}(A_i).$$ La formule du crible de Poincaré peut aussi s'interpréter en termes de probabilité, en remplaçant partie par événements, et $\textrm{card}$ par $P.$ Elle est aussi connue sous le nom de principe d'inclusion-exclusion.

On appelle dérangement d'un ensemble fini $E$ toute permutation de $E$ sans point fixe (ie toute bijection $s$ de $E$ dans $E$ telle que, si $x$ est dans $E$, $s(x)$ est différent de $x$). On se pose alors l problème suivant : si $E$ a $n$ éléments, quel est le nombre de dérangements de $E$?

On note $E=\{1,…,n\}$, et $A_i$ l'ensemble des permutations qui laisse $i$ invariant. Le cardinal recherché est : $$\textrm{card}(\overline{A_i}\cap\cdots\cap \overline{A_n})=n!-\textrm{card}(A_1\cup\cdots\cup A_n).$$ On va appliquer la formule du crible pour calculer ce cardinal. On a : $$\textrm{card}(A_1\cup\cdots\cup A_n)=\sum_{k=1}^n (-1)^{k-1}S_k$$ où $$S_k=\sum_{1\leq i_1<\cdots<i_k\leq n}\textrm{card}(A_{i_1}\cap\cdots\cap A_{i_k}).$$ Maintenant, toute permutation qui laisse fixe les $k$ éléments $i_1,\dots,i_k$ agit comme elle veut sur les autres. Il y a donc autant de permutations de $E$ qui fixent $i_1,\dots,i_k$ que de permutations d'un ensemble à $n-k$ éléments. On a donc : $$\textrm{card}(A_{i_1}\cap\cdots\cap A_{i_k})=(n-k)!.$$ Par conséquent : $$S_k=\binom nk(n-k)!=\frac{n!}{k!}.$$ On en déduit que le nombre de dérangements vaut $$D_n=n!\sum_{k=0}^n \frac{(-1)^k}{k!}.$$