$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th
Dictionnaire de mathématiques > Dénombrements et probabilités > Dénombrement >
Dictionnaire de mathématiques > Dénombrements et probabilités > Probabilités >

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

Théorème : Soit $E$ un ensemble fini, et une famille de parties de l'ensemble $E$. Alors :
En particulier, si est une partition de $E$, on a :
La formule du crible de Poincaré peut aussi s'interpréter en termes de probabilité, en remplaçant partie par événements, et card par P. Elle est aussi connue sous le nom de principe d'inclusion-exclusion.

Application aux calculs du nombre de dérangements
Définition : 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$).
Problème : 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 :
On va appliquer la formule du crible pour calculer ce cardinal. On a :
où
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 :
Par conséquent : $$S_k=\binom nk(n-k)!=\frac{n!}{k!}.$$ On en déduit que le nombre de dérangements vaut :
Consulter aussi...