Souvent redouté des lycéens et des préparationnaires, le dénombrement peut s’avérer très utile et même indispensable pour déterminer une probabilité. En réalité le plus difficile est de reconnaître la situation à laquelle on est confronté pour pouvoir (comme souvent !) utiliser la bonne formule.
Définition du dénombrement
Soit \(E\) un ensemble fini, on appelle cardinal de \(E\) le nombre d’éléments de \(A\), noté \(Card(E)=n\) (\(n\in\mathbb{N}\)). Dénombrer un ensemble c’est déterminer son nombre d’éléments. Ainsi, par exemple, \(Card(\emptyset)=0\).
Quelques propriétés
Soit \(E\) un ensemble de référence fini, et \(A,B,C \in\mathcal{P}(E)\)
Si \(A \subset B\), alors \(Card(A) \le Card(A\cup B)\)
Si \(A\subset B\) et \(Card(A)=Card(B)\), alors \(A=B\)
Si \(A\) et \(B\) sont disjoints, alors \(Card(A\cup B)=Card(A) + Card(B)\)
Si les \((A_{i})_{i \in I}\) sont deux à deux disjoints, alors \(Card (\displaystyle \bigcup_{i\in I} A_{i})= \sum_{i \in I} Card(A_i)\)\(Card(A \backslash B)= Card(A) – Card(B)\)\(Card(A\cup B)=Card(A) + Card(B) – Card(A \cap B)\) \(Card (A \times B)= Card(A) \times Card(B)\)
Formule du Crible :
\(Card(A \cup B \cup C)= Card(A) + Card(B) + Card(C) – Card(A\cap B) – Card(A\cap C) – Card (B \cap C) + Card(A\cap B \cap C)\)
Analyse combinatoire
En pratique, pour savoir quelle formule utiliser lorsqu’on recherche le nombre de façons de choisir \(k\) éléments dans un ensemble \(E\) à \(n\) éléments, il faut se demander si le choix est ordonné ou non ordonné et s’il se fait sans répétition possible ou avec répétition possible. On peut alors déterminer quelles formules on peut utiliser dans celles qui suivent.
\(p\)-listes
Soit \(E\) un ensemble à \(n\) éléments (\(n\in\mathbb{N}\)). Choisir une \(p\)-liste d’éléments parmi les \(n\) éléments de E c’est choisir \(p\) éléments de E avec ordre (successivement) avec répétition possible.
NB : on peut donc retrouver \(p\) fois le même élément de \(E\).
Avec \(Card(E)=n\), il y a donc \(n^p\) listes de \(p\) éléments de \(E\).
Par exemple, si on choisit \(3\) boules successivement et avec remise dans une urne qui contient \(n\) boules numérotées de \(1\) à \(n\) (\(n\ge 3\)), il y a \(3^n\) listes de tirages possibles.
\(p\)-listes d’éléments distincts
si \(p\le n\), il y a \(n(n-1)…(n-p+1)\)\(=\frac{n!}{(n-p)!}\) listes (ordonnées) de \(p\) éléments distincts d’un ensemble \(E\) de cardinal \(n\).
En reprenant l’exemple précédent sans la notion de remise, on a donc \(\frac{n!}{(n-3)!}=n(n-1)(n-2)\) listes de tirages de 3 boules distinctes possibles.
Permutations
Soit \(E\) un ensemble fini. Une permutation de \(E\) est une bijection de \(E\) dans \(E\).
Il y a \(n!\) permutations d’un ensemble \(E\) à \(n\) éléments. Autrement dit, il y a \(n!\) manières d’arranger avec un ordre différent une liste de \(n\) numéros.
Combinaisons
Une combinaison de \(p\) éléments choisis parmi \(n\) est une partie à \(p\) éléments d’un ensemble à \(n\) à n éléments (avec \(p\le n\)).
Le nombre de combinaisons de \(p\) éléments choisis parmi \(n\) est égal à \({n}\choose{p}\), ce qui se prononce “\(p\) parmi \(n\)” et ce nombre vaut :
\(
\begin{cases}
\frac {n!}{(n-p)!} &\text{si} \; 0\le p\le n \\
0 &\text{sinon}\
\end{cases}
\)
Ce nombre se retrouve notamment pour les lois suivant une loi binomiale. Par exemple, si on choisit simultanément \(3\) boules dans la même que précédemment, il y a \({n}\choose{3}\) tirages possibles.
Quelques relations à connaître sur le dénombrement..
\(\forall (k,n) \in
\mathbb{N}\)
\({n}\choose{0}\)=\({n}\choose{n}\)\(=1\)
\({n}\choose{1}\)\(=1\)
\({n}\choose{k}\)\(=\)\({n}\choose{n-k}\) (symétrie du coefficient binomial)
\({n}\choose{k}\)\(+\)\({n}\choose{k+1}\)\(=\)\({n+1}\choose{k+1}\) (triangle de Pascal)
\(\displaystyle \sum_{k=0}^{n}{{n}\choose{k}}=2^n\)
