$$\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 > Mathématiques discrètes > Dénombrement >
Dictionnaire de mathématiques > Probabilité et statistiques > Probabilité >

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

Théorème (formule du crible de Poincaré) : Soit $E$ un ensemble fini, et $(A_i)_{1\leq i\leq n}$ une famille de parties de l'ensemble $E$. Alors : \begin{eqnarray*} \textrm{card}\left(\bigcup_{i=1}^n A_i\right)&=&\sum_{i=1}^n \textrm{card}(A_i)-\sum_{1\leq i_1<i_2\leq n}\textrm{card}(A_{i_1}\cap A_{i_2}) \\ &&+\sum_{1\leq i_1<i_2<i_3\leq n}\textrm{card}(A_{i_1}\cap A_{i_2}\cap A_{i_3})+\dots\\ &&+(-1)^{k+1}\sum_{1\leq i_1<\cdots<i_k\leq n}\textrm{card}(A_{i_1}\cap\cdots\cap A_{i_k})+\dots\\ &&+(-1)^{n+1}\textrm{card}(A_{1}\cap \cdots \cap A_{n}). \end{eqnarray*}

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.

Application aux calculs du nombre de dérangements

On appelle dérangement d'un ensemble fini $E$ toute permutation de $E$ sans point fixe (i.e. 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 le 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 laissent $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$ induit une permutation quelconque des autres éléments. 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!}.$$

Consulter aussi...
Recherche alphabétique
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
Recherche thématique
  • Algèbre
  • Analyse
  • Applications
  • Arithmétique
  • Probabilité et statistiques
  • Géométrie
  • Fondements
  • Histoire
  • Mathématiques discrètes
  • Mathématiques interactives