Dénombrement
1. Ensembles et cardinaux
Définition
Soit E un ensemble fini.
On appelle cardinal de l'ensemble E et on note card (E) le nombre d'éléments de E.
Exemple
Si E = {a; b; c; d}, alors card (E) = 4.
Définition
Soit E un ensemble quelconque. On dit que F est une partie de E (ou un sous-ensemble de E) si et seulement si tous les éléments de F appartiennent également à E.
On note alors F $ \subset $ E ( F « inlus » dans E).
Exemple
Si E = { a; b; c; d }, F = { b; c } et G = { d }
alors F $ \subset $ E, G $ \subset $ E mais G ⊄ F.
Remarque
L'ensemble vide $ \varnothing $ et l'ensemble E lui-même sont des parties de E.
Théorème
Le nombre de parties d'un ensemble de $ n $ éléments est $ 2^n $.
Exemple
L'ensemble E = { a; b; c } possède 2$ ^3 $ = 8 sous-ensembles :
$ \varnothing $, { a }, { b }, { c }, { a; b }, { a; c }, { b; c }, { a; b; c }.
Définition (Réunion de deux ensembles)
Soient A et B deux ensembles quelconques.
La réunion des ensembles A et B, notée A $ \cup $ B, est l'ensemble des éléments qui appartiennent à A ou à B (ou aux deux ensembles).
Exemple
Si A = { a; b; c } et B = { a; c; d; e }
alors A $ \cup $ B = { a; b; c; d; e }.
Définition (Intersection de deux ensembles)
Soient A et B deux ensembles quelconques.
L'intersection des ensembles A et B, notée A $ \cap $ B, est l'ensemble des éléments qui appartiennent à la fois à A et à B.
Exemple
Si on reprend l'exemple précédent : A = { a; b; c } et B = { a; c; d; e }
alors A $ \cap $ B = { a; c }.
Définition (Produit cartésien)
Soient A et B deux ensembles non vides.
Le produit cartésien de A par B, noté A $ \times $ B (A « croix » B), est l'ensemble des couples (a; b) où a $ \in $ A et b $ \in $ B.
Remarque
- un couple s'écrit avec des parenthèses et un ensemble avec des accolades.
- l'ordre a de l'importance dans un couple ( c'est à dire que les couples (a; b) et (b; a) sont différents ).
- on définit de même le produit cartésien de 3 ensemble ou plus. A $ \times $ B $ \times $ C est l'ensemble des triplets (a; b; c) où a $ \in $ A, b $ \in $ B et c $ \in $ C.
- on définit également A $ ^p $ = A $ \times $ A $ \times $...$ \times $ A (p fois). Cet ensemble est composé de toutes les listes ordonnées de p éléments de A.
Exemple
Si A = { a; b } et B = { 1; 2; 3 }
alors A $ \times $ B = { (a; 1); (a; 2); (a; 3); (b; 1); (b; 2); (b; 3)}
et A$ ^2 $ = { (a; a); (a; b); (b; a); (b; b) }.
Propriété (Principe additif)
Si A et B sont deux ensembles finis disjoints (c'est à dire que A $ \cap $ B = $ \varnothing $), alors :
card (A $\cup$ B) = card (A) + card (B)
Remarque
Dans le cas où A et B ne sont pas nécessairement disjoints, on a la formule plus générale :
card (A $ \cup $ B) = card (A) + card (B) - card (A $ \cap $ B)
Propriété (Principe multiplicatif)
Si A et B sont deux ensembles finis non vides, alors :
card (A $ \times $ B) = card (A) $ \times $ card (B)
Exemple
Si l'on reprend l'exemple précédent A = { a; b }, B = { 1; 2; 3 }
et A $ \times $ B = { (a; 1); (a; 2); (a; 3); (b; 1); (b; 2); (b; 3)}
alors :
card (A) = 2, card (B) = 3 et
card (A $ \times $ B) = 2 $ \times $ 3 = 6 ( A $ \times $ B contient 6 couples !)
2. Permutations et p-uplets
Définition
Soit E un ensemble fini de cardinal $ n $.
Une permutation de E est une liste ordonnée comportant les $ n $ éléments de E sans répétition.
Exemple
Soit E={ a; b; c}
E admet 6 permutations qui sont : (a; b; c), (a; c; b), (b; a; c), (b; c; a), (c; a; b) et (c; b; a).
Remarque
- dans les notations avec parenthèses du type ( a ; b ; c ) l'ordre est pris en compte. (il s'agit d'une liste ordonnée)
- dans les notations avec accolades du type { a ; b ; c } l'ordre n'est pas pris en compte. (il s'agit d'un ensemble)
Théorème
Le nombre de permutations d'un ensemble fini E à n éléments est le nombre n! ( factorielle n ) défini par :
$ n! = n\times \left(n - 1\right)\times . . .\times 1 $
Remarque
- par convention on pose 0! = 1
- pour tout entier $ n > 0 $ : $ n! = n\times \left(n - 1\right)! $
Exemple
Si l'on reprend l'exemple précédent on vérifie bien que :
$ 3! = 3\times 2\times 1=6 $
Définition
Soit E un ensemble quelconque.
Un p-uplet de E est une liste ordonnée de p éléments de E.
Exemple
Soit E = { a; b; c } :
( a; c; a; b; a ) est un 5-uplet de E.
Remarque
- un p-uplet de E est un élément de E$ ^p $ = E $ \times $ E $ \times $...$ \times $ E (p fois) ;
- un 2-uplet est un couple ;
- un 3-uplet est un triplet, etc.
Définition
Soit E un ensemble fini de cardinal n et p un entier naturel inférieur ou égal à n.
Un arrangement de p éléments de E est un p-uplet formé de p éléments distincts de E.
Exemple
Soit A = { a; b; c; d },
( a; b ; c ) et ( b; a; d ) sont deux arrangements de 3 éléments de A.
( a; b; a ) n'est pas un arrangement car il possède deux éléments identiques.
Remarque
Une permutation d'un ensemble de n éléments n'est autre qu'un arrangement de n éléments de cet ensemble ( par exemple ( b; a; d; c ) est une permutation de l'ensemble A de l'exemple précédent ).
Propriété
Soit E un ensemble fini de cardinal n et p un entier naturel inférieur ou égal à n.
Le nombre d'arrangements de p éléments de E est le nombre :
Exemple
8 coureurs participent à une course. Le nombre de podiums possibles ( un podium = les trois premières places en tenant compte de l'ordre d'arrivée ) est :
$ A_8^3 = 8 \times 7 \times 6 = 336. $
3. Combinaisons
Définition
Soit E un ensemble fini à $ n $ éléments et $ p $ un entier tel que $ 0\leqslant p\leqslant n $ .
Une combinaison de p éléments de E est une partie de E contenant p éléments.
Remarque
Une partie est un ensemble donc l'ordre n'est pas pris en compte
Exemple
Soit E={a;b;c}
E admet 3 combinaisons à 2 éléments qui sont : {a;b}, {a;c}, {b;c}
Théorème
Le nombre de combinaisons de p éléments d'un ensemble à n éléments est le nombre noté $ \begin{pmatrix} n \\ p \end{pmatrix} $ (on lit « $ p $ parmi $ n $ » ) égal à :
Exemple
- Dans l'exemple ci-dessus on a bien : $ \begin{pmatrix} 3 \\ 2 \end{pmatrix}=\dfrac{3!}{2!\times 1!}=\dfrac{6}{2}=3 $
- Au poker une "main" est formée de 5 cartes parmi 52. Il y a donc :
$ \begin{pmatrix} 52 \\ 5 \end{pmatrix}=\dfrac{52!}{47!\times 5!}=\dfrac{52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2\times 1}=2~598~960 $ combinaisons
Propriété
Pour tout entier naturel $ n $ :
$ \begin{pmatrix} n \\ 0 \end{pmatrix}=1 $et
$ \begin{pmatrix} n \\ n \end{pmatrix}=1 $.
Pour tout entier naturel $ n $ et tout entier naturel $ k $ ($ 0\leqslant k < n $) :
$ \begin{pmatrix} n \\ k \end{pmatrix}+\begin{pmatrix} n \\ k+1 \end{pmatrix}=\begin{pmatrix} n+1 \\ k+1 \end{pmatrix} $.
Remarque
Ces propriétés permettent de calculer les combinaisons de proches en proches, grâce au Triangle de Pascal.
La figure ci-dessous représente ce triangle pour $ n\leqslant 10 $
Pour construire ce triangle on procède de la manière suivante :
- On place des «1» dans la colonne $ k=0 $.
- On place des «1» sur la diagonale (qui correspond à $ k=n $).
- On utilise la formule $ \begin{pmatrix} n \\ k \end{pmatrix}+\begin{pmatrix} n \\ k+1 \end{pmatrix}=\begin{pmatrix} n+1 \\ k+1 \end{pmatrix} $ pour calculer les autres coefficients.
Par exemple, pour trouver $ \begin{pmatrix} 7 \\ 4 \end{pmatrix}=35 $ on fait la somme des deux coefficients $ \begin{pmatrix} 6 \\ 3 \end{pmatrix}=20 $ et $ \begin{pmatrix} 6 \\ 4 \end{pmatrix}=15 $ de la ligne précédente.
Propriété
Pour tout entier naturel $ n $ :
Démonstration
Soit E un ensemble de cardinal $ n $.
- $ \begin{pmatrix} 0 \\ n \end{pmatrix} $ représente le nombre de parties de E ayant 0 élément ;
- $ \begin{pmatrix} 1 \\ n \end{pmatrix} $ représente le nombre de parties de E ayant 1 élément ;
- $ \cdots $
- $ \begin{pmatrix} n \\ n \end{pmatrix} $ représente le nombre de parties de E ayant $ n $ éléments.
- Le total de ces combinaisons représente le nombre total de parties de E soit 2$ ^n $ d'après un résultat vu au paragraphe 1.