Dénombrement
I. Ensemble fini – Cardinal d'un ensemble fini
a. Définition
Définition : Soit $n \in \mathbb{N}$. Si $E$ est un ensemble qui contient $n$ éléments, on dit que $E$ est un ensemble fini. Le nombre $n$ s'appelle le cardinal de $E$. On note :
$$ card(E) = n $$
Par convention, le cardinal de l'ensemble vide est nul : $card(\emptyset) = 0$.
b. Exemple
Soit $E = \{ a, b, c, f \}$. Alors $card(E) = 4$.
Les ensembles $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{R}$ et l'intervalle $[0, 1]$ sont des ensembles infinis.
Les ensembles $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{R}$ et l'intervalle $[0, 1]$ sont des ensembles infinis.
c. Propriétés
Soient $E$ et $F$ deux ensembles finis.
- Si $E \cap F = \emptyset$ (ensembles disjoints), alors : $$ card(E \cup F) = card(E) + card(F) $$
- En général (principe d'inclusion-exclusion) : $$ card(E \cup F) = card(E) + card(F) - card(E \cap F) $$
- Pour le produit cartésien ($E \neq \emptyset$ et $F \neq \emptyset$) : $$ card(E \times F) = card(E) \times card(F) $$
- Si $A \subset E$ (A est une partie de E), on note le complémentaire de A dans E par $E \setminus A$ ou $\overline{A}$. On a : $$ card(E \setminus A) = card(E) - card(A) $$
d. Exemple d'application
Soit $E = \{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 \}$. Soit $A = \{ 1, 2, 3, 5, 7, 8, 9 \}$ et $B = \{ 2, 4, 6, 8, 10, 11 \}$.
- $card(A) = 7$
- $card(B) = 6$
- $A \cap B = \{ 2, 8 \}$ donc $card(A \cap B) = 2$
- $card(A \cup B) = 7 + 6 - 2 = 11$
- $card(E \setminus A) = 11 - 7 = 4$
II. Principe fondamental de dénombrement
a. Activité
On veut déterminer tous les nombres constitués par deux chiffres différents parmi les chiffres 3, 4 et 5.
- Méthode 1 (Liste) : 34, 35, 43, 45, 53, 54. On obtient 6 nombres.
- Méthode 2 (Principe) :
- Choix du chiffre des unités : 3 possibilités (3, 4 ou 5).
- Choix du chiffre des dizaines : 2 possibilités (car les chiffres doivent être différents).
b. Principe général (Principe du produit)
On considère une expérience comportant $p$ choix (étapes) successifs.
- Si le choix n°1 se fait avec $n_1$ manières différentes.
- Si le choix n°2 se fait avec $n_2$ manières différentes.
- ...
- Si le choix n°$p$ se fait avec $n_p$ manières différentes.
c. Exemples
Exemple 1 : On lance un dé (à 6 faces) deux fois successives.
- 1er lancer : 6 choix.
- 2ème lancer : 6 choix.
- Nombre de cas possibles : $6 \times 6 = 36$.
- Chaque lancer a 2 choix.
- Nombre de cas possibles : $2 \times 2 \times 2 = 8$.
III. Arrangement avec répétition
a. Activité (Tirage avec remise)
Une urne contient 6 boules rouges et 3 boules vertes (Total 9 boules). On tire 2 boules l'une après l'autre avec remise.
- 1ère boule : 9 manières d'être tirée.
- 2ème boule : 9 manières d'être tirée (car remise).
- Nombre de tirages possibles : $9 \times 9 = 9^2 = 81$.
b. Propriété
Le nombre d'arrangements avec répétition de $p$ éléments parmi $n$ éléments est :
$$ n^p $$
Remarque : L'ordre compte et la répétition est autorisée.
IV. Arrangement sans répétition
a. Activité
Course de marathon entre 4 athlètes (A, B, C, D). Deux prix sont distribués (1ère et 2ème place).
Un résultat possible est (D, B) signifiant D premier et B deuxième. Le résultat (B, D) est différent.
Chaque résultat est un arrangement sans répétition de 2 éléments parmi 4.
b. Définition
Ordonner $p$ éléments distincts choisis parmi $n$ éléments distincts ($p \leq n$) s'appelle un arrangement sans répétition.
c. Propriété
Le nombre d'arrangements sans répétition de $p$ éléments parmi $n$ éléments, noté $A_n^p$, est :
$$ A_n^p = n \times (n-1) \times \dots \times (n-p+1) = \frac{n!}{(n-p)!} $$
Avec $0 \leq p \leq n$ et $n \in \mathbb{N}$.
Rappel Factorielle : $n! = 1 \times 2 \times \dots \times n$. Par convention $0! = 1$ et $1! = 1$.
Rappel Factorielle : $n! = 1 \times 2 \times \dots \times n$. Par convention $0! = 1$ et $1! = 1$.
d. Modèle (Tirage sans remise)
Une urne contient $n$ boules. On tire $p$ boules l'une après l'autre sans remise.
Exemple : Urne avec 6 rouges et 3 vertes (9 total). On tire 2 boules sans remise.
Exemple : Urne avec 6 rouges et 3 vertes (9 total). On tire 2 boules sans remise.
- Nombre de tirages possibles : $A_9^2 = 9 \times 8 = 72$.
- Nombre de tirages de 2 vertes : $A_3^2 = 3 \times 2 = 6$.
V. Permutation de $n$ éléments
a. Définition
Ordonner $n$ éléments distincts parmi $n$ éléments (cas particulier où $p=n$) s'appelle une permutation.
b. Propriété
Le nombre de permutations de $n$ éléments, noté $P_n$, est :
$$ P_n = A_n^n = n! $$
c. Exemple
Distribuer 4 prix distincts à 4 athlètes (A, B, C, D).
Le nombre de façons de distribuer les prix est $P_4 = 4! = 24$.
VI. Combinaison de $p$ éléments parmi $n$
a. Activité
Soit $E = \{ a, b, c, d, f \}$.
La partie $A = \{ b, d \}$ est une combinaison de 2 éléments parmi 5. L'ordre n'a pas d'importance ($\{b, d\} = \{d, b\}$).
b. Définition
Soit $E$ un ensemble fini de cardinal $n$. Toute partie $A$ de $E$ contenant $p$ éléments ($p \leq n$) s'appelle une combinaison de $p$ éléments parmi $n$.
c. Propriété
Le nombre de combinaisons de $p$ éléments parmi $n$, noté $C_n^p$ ou $\binom{n}{p}$, est :
$$ C_n^p = \frac{A_n^p}{p!} = \frac{n!}{p!(n-p)!} $$
d. Propriétés des combinaisons
- $C_n^0 = 1$ et $C_n^n = 1$.
- $C_n^1 = n$ et $C_n^{n-1} = n$.
- Symétrie : $C_n^p = C_n^{n-p}$.
- Relation de Pascal : $C_n^p + C_n^{p+1} = C_{n+1}^{p+1}$.
e. Modèle (Tirage simultané)
Une urne contient 6 boules rouges et 3 boules vertes (9 total). On tire simultanément 2 boules.
- Nombre de tirages possibles : $C_9^2 = \frac{9 \times 8}{2 \times 1} = 36$.
- Nombre de tirages de 2 couleurs différentes (1 Rouge et 1 Verte) : $$ C_6^1 \times C_3^1 = 6 \times 3 = 18 $$
VII. Binôme de Newton
a. Théorème
Soient $a$ et $b$ deux réels et $n \in \mathbb{N}^*$. On a :
$$ (a + b)^n = \sum_{k=0}^{n} C_n^k a^{n-k} b^k $$
$$ (a + b)^n = C_n^0 a^n + C_n^1 a^{n-1}b + \dots + C_n^n b^n $$
b. Triangle de Pascal
Le triangle de Pascal permet de trouver les coefficients $C_n^p$.
| n \ p | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 0 | 1 | ||||||
| 1 | 1 | 1 | |||||
| 2 | 1 | 2 | 1 | ||||
| 3 | 1 | 3 | 3 | 1 | |||
| 4 | 1 | 4 | 6 | 4 | 1 | ||
| 5 | 1 | 5 | 10 | 10 | 5 | 1 | |
| 6 | 1 | 6 | 15 | 20 | 15 | 6 | 1 |
c. Exemple de développement
Développons $(x + 2)^4$ :
$$ (x + 2)^4 = C_4^0 x^4 2^0 + C_4^1 x^3 2^1 + C_4^2 x^2 2^2 + C_4^3 x^1 2^3 + C_4^4 x^0 2^4 $$
$$ = 1 \cdot x^4 + 4 \cdot 2x^3 + 6 \cdot 4x^2 + 4 \cdot 8x + 1 \cdot 16 $$
$$ = x^4 + 8x^3 + 24x^2 + 32x + 16 $$