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 inclus dans E).
Exemple
Si E = { a; b; c; d }, F = { b; c } et G = { d }
alors F \subset E, G \subset E mais G \not\subset 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.
Remarques
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\cupB) = 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\cupB) = card (A) + card (B) – card (A\capB)
Propriété (Principe multiplicatif)
Si A et B sont deux ensembles finis non vides, alors :
card (A\timesB) = 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 !)
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
Remarques
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.
Remarques
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 :
A_n^p = n \times (n – 1) \times \cdots \times (n – p+1) = \dfrac{ n! }{ (n – p) !}
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.
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 à :
\begin{pmatrix} n \\ p \end{pmatrix}=\dfrac{n!}{p!\left(n – p\right)!}
Exemples
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{aligned} \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 \text{ combinaisons} \end{aligned}
Propriétés
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 :
\begin{pmatrix} 0 \\ n \end{pmatrix} + \begin{pmatrix} 1 \\ n \end{pmatrix} + \cdots + \begin{pmatrix} n \\ n \end{pmatrix} = 2^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.