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.
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$ \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$
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. $
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 à :
$\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.