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.

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}=\frac{n!}{p!\left(n - p\right)!}$

Exemples

Dans l'exemple ci-dessus on a bien : $\begin{pmatrix} 3 \\ 2 \end{pmatrix}=\frac{3!}{2!\times 1!}=\frac{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}&=\frac{52!}{47!\times 5!} \\ \\ &=\frac{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$

triangle de Pascal

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.

Maths-cours

Dénombrement

1. Ensembles et cardinaux

Définition

Exemple

Définition

Exemple

Remarque

Théorème

Exemple

Définition (Réunion de deux ensembles)

Exemple

Définition (Intersection de deux ensembles)

Exemple

Définition (Produit cartésien)

Remarques

Exemple

Propriété (Principe additif)

Remarque

Propriété (Principe multiplicatif)

Exemple

2. Permutations et p-uplets

Définition

Exemple

Remarque

Théorème

Remarques

Exemple

Définition

Exemple

Remarques

Définition

Exemple

Remarque

Propriété

Exemple

3. Combinaisons

Définition

Remarque

Exemple

Théorème

Exemples

Propriétés

Remarque

Propriété

Démonstration

Dans ce chapitre :

Cours

Exercices