DÉNOMBREMENT

1 - PRINCIPE ADDITIF

Définition

Soit $A$ un ensemble fini . Le nombre d'éléments de $A$ s'appelle le cardinal de $A$ et est noté $C a r d (A)$ .

Propriété admise

Si $A_{1}$ , $A_{2}$ , ... $A_{n}$ sont $n$ ensembles deux à deux disjoints, alors :

$C a r d (A_{1} \cup A_{2} \cup . . . \cup A_{n - 1} \cup A_{n}) = C a r d (A_{1}) + C a r d (A_{2}) + . . . + C a r d (A_{n - 1}) + C a r d (A_{n})$

Définition - Rappel

Si $A \cap B = \emptyset$ , on dit que les ensembles $A$ et $B$ sont disjoints.

Remarque

Si des ensembles forment une partition d'un autre ensemble, ils sont alors deux à deux disjoints.

Ainsi, si $A$ est une partie d'un ensemble $E$ , alors $C a r d (\overset{―}{A}) = C a r d (E) - C a r d (A)$

Exemple : Combien y a-t-il de carrés sur la figure ci-dessous ?
On note $E$ l'ensemble de tous ces carrés et $A_{1}$ , $A_{2}$ , $A_{3}$ et $A_{4}$ respectivement l'ensemble de ces carrés ayant pour côtés 1, 2, 3 et 4 carreaux.

Les sous-ensembles $A_{1}$ , $A_{2}$ , $A_{3}$ , $A_{4}$ constituent une partition de E (puisqu'ils n'ont pas d'éléments en commun et que leur réunion est égale à E).

D'après le principe additif, on a :

$C a r d (E) = C a r d (A_{1}) + C a r d (A_{2}) + C a r d (A_{3}) + C a r d (A_{4}) = 16 + 9 + 4 + 1 = 30$

Remarque

Si $A$ et $B$ sont quelconques (c'est-à-dire pas nécessairement disjoints), alors :

C a r d (A \cup B) = C a r d (A) + C a r d (B) - C a r d (A \cap B)

2 - PRODUIT CARTÉSIEN

Définition

Soit $A$ et $B$ deux ensembles finis et non vides.

Le produit cartésien de $A$ par $B$ noté $A \times B$ est l'ensemble des couples $(x; y)$ formés d'un élément $x$ de $A$ suivi d'un élément $y$ de $B$ .

On définit de la même façon le produit cartésien de $3, 4, . . ., n$ ensembles.

Ce qui consiste à distribuer tous les éléments de $A$ par rapport à chaque élément de $B$ .

On peut écrire : $A \times B = {(x; y) | x \in A et y \in B}$

Exemple : Soit $A = {1; 2; 3}$ et $B = {a; b}$ .

On a $A \times B = {(1; a); (2; a); (3; a); (1; b); (2; b); (3; b)}$ et $B \times A = {(a, 1); (a; 2); (a; 3); (b, 1); (b; 2); (b; 3)}$

Remarques

$A \times B \neq B \times A$ : l'ordre d'un produit cartésien est important
Si $A = \emptyset$ ou $B = \emptyset$ , alors $A \times B = \emptyset$
Le produit d'un ensemble infini par un ensemble infini est infini. ( $R \times R = R^{2}$ représente l'ensemble de tous les couples de nombres réels)

Définition

Soit $A$ est un ensemble fini et non vide et $k$ est un entier naturel non nul.

On note :

$A^{k} = A \times A \times \dots \times A$ ( $k$ facteurs)

Les éléments de $A^{k}$ sont des couples, des triplets, des quadruplets...

De façon générale, on parle de k-uplet (ou k-listes) ordonnés.

Les coordonnées dans le plan ou dans l'espace offrent de bons exemples d'emploi.

Exemple: On dispose de trois dés tétraédriques (un bleu, un rouge, un jaune) dont les faces sont marquées de 1 à 4.

On jette les trois dés et on note dans l'ordre le résultat obtenu sur le dé bleu, puis rouge, puis jaune.

Si $A = {1; 2; 3; 4}$ alors , $A^{3}$ est l'ensemble de tous les résultats possibles.

3 - PRINCIPE MULTIPLICATIF

Propriétés

Soit $A$ et $B$ deux ensembles finis et non vides . On a alors $C a r d (A \times B) = C a r d (A) \times C a r d (B)$ .
Soit $A$ un ensemble fini et non vide et $k$ un entier naturel non nul. Si $C a r d (A) = n$ , alors $C a r d (A^{k}) = n^{k}$ .

Résultat immédiat en utilisant la distributivité

Exemple: On reprend l'exemple précédent.

$C a r d (A^{3}) = 4^{3} = 64$

Il y a donc 64 résultats possibles pour l'expérience envisagée.

Dans la pratique, ce principe s'applique souvent en utilisant un schéma à cases :

Si une situation comporte $k$ étapes offrant respectivement $n_{1}$ , $n_{2}$ ,... , $n_{k}$ possibilités alors le nombre total d'issues est :

n_{1} \times n_{2} \times \dots \times n_{k}

Exemple: Un code comporte deux lettres distinctes suivies d'un chiffre non nul. Combien peut-on former de codes distincts ?

D'après le principe multiplicatif, on a :

Lettre 1 Lettre 2 Chiffre

26 25 10

Exemple: Nombre de parties d'un ensemble à $n$ éléments (Exemple à connaître)

Soit $A$ un ensemble tel que $C a r d (A) = n$ . Combien de parties différentes contient $A$ ?

Il suffit pour chaque élément de se poser la question appartient-il ( noté 1 ) ou non ( noté 0 ) à la partie choisie.

D'après le principe multiplicatif, on a :

Élément 1 Élément 2 ... Élément $n$

2 2 ... 2

$2 \times 2 \times \dots \times 2 = 2^{n}$

On peut aussi faire l'analogie avec le nombre d'entiers écrits en binaire sur $n$ bits:

$\overset{n bits}{\overset{⏞}{1010. . .001}}$

4 - ARRANGEMENTS ET PERMUTATIONS

Définition

Soit un ensemble $A$ de cardinal $n$ et un entier $k ⩽ n$ .

Un arrangement de $k$ éléments choisis parmi $n$ est un $k$ -uplet d'éléments distincts de $A$ .

Exemple : Soit un ensemble $A = {1; 2; 3; 4; 5; 6}$

Un arrangement de 3 éléments de $A$ sera par exemple $(1; 4; 2)$ ou $(1; 6; 3)$ .

$(1; 4; 4)$ n'est pas un arrangement, c'est un 3-uplet (un triplet) dont les éléments qui le composent ne sont pas distincts.

Propriété

Soit un ensemble $A$ de cardinal $n$ et un entier $k ⩽ n$ .

Le nombre d'arrangements de $k$ éléments de $A$ est :

n \times (n - 1) \times . . . \times (n - k + 1)

On le note $A_{n}^{k}$ .

$A_{n}^{k}$ est le produit de $k$ entiers consécutifs décroissants à partir de $n$ .

Preuve :

Ce résultat se montre facilement avec un schéma à cases :

D'après le principe multiplicatif, si on compte le nombre de possibilités pour chaque élément, on a :

Élément 1	Élément 2	...	Élément $k$
$n$	$n - 1$	...	$n - k + 1$

Exemple : $A_{8}^{3} = 8 \times 7 \times 6 = 336$

Remarque

On utilise les arrangements en cas de choix successifs de $p$ éléments pris parmi $n$ , sans répétition.

Définition

Soit un ensemble $A$ de cardinal $n$ .

Une permutation de $A$ est un arrangement de $E$ ayant $n$ éléments.

Exemple : Soit un ensemble $A = {1; 2; 3; 4; 5; 6}$

$(1; 3; 2; 6; 5; 4)$ et $(6; 5; 4; 2; 1; 3)$ sont deux permutations de $A$ .

Définition

On note $n!$ (lire « factorielle n » ) le produit des $n$ premiers entiers naturels non nuls.

Par convention, on pose $0! = 1$ .

On a alors $A_{n}^{k} = \frac{n!}{(n - k)!}$

Propriété

Soit un ensemble $A$ de cardinal $n$ .

Le nombre de permutations de $A$ est $n!$ .

Immédiat, car une permutation est un arrangement de $A$ ayant $n$ éléments.

Remarques

On utilise les permutations dans les cas où on veut ordonner tous les éléments d'un ensemble sans répétition.

5 - COMBINAISONS

Définition

Soit $A$ un ensemble de cardinal $n$ .

Une partie à $k$ éléments de $A$ est une combinaison de $k$ éléments de $A$ .

Exemple : Soit un ensemble $A = {1; 2; 3; 4; 5; 6}$

${2; 5; 6}$ et ${1; 4; 5}$ sont deux combinaisons à 3 éléments de $A$ .

Remarque

Le fait d'utiliser des accolades signifie que l'ordre d'écriture n'est pas important.

Propriété

Soit un ensemble $A$ de cardinal $n$ et un entier $k ⩽ n$ .

Le nombre de combinaisons de $k$ éléments de $A$ est :

$\frac{n \times (n - 1) \times \dots \times (n - k + 1)}{k!} = \frac{n!}{(n - k)! k!}$

On le note $(\begin{matrix} n \\ k \end{matrix})$ (notation que nous utiliserons) ou parfois $C_{n}^{k}$ .

$(\begin{matrix} n \\ k \end{matrix})$ se lit " $k$ parmi $n$ ".

On l'appelle coefficient binomial.

Preuve :

Dénombrons les arrangements de $k$ éléments d'un ensemble fini $A$ de cardinal $n$ .

Un arrangement est caractérisé par :

Le choix d'une partie de $A$ à $k$ éléments (il y a $(\begin{matrix} n \\ k \end{matrix})$ choix de telles parties)
La façon d'ordonner les $k$ éléments de la partie choisie ( il y a $k!$ façons)

On en déduit que : $A_{n}^{k} = k! (\begin{matrix} n \\ k \end{matrix}) \Leftrightarrow (\begin{matrix} n \\ k \end{matrix}) = \frac{A_{n}^{k}}{k!}$

Exemple : Soit un ensemble $A = {1; 2; 3; 4; 5; 6}$

Il y a $(\begin{matrix} 6 \\ 3 \end{matrix}) = \frac{6!}{3! 3!} = 20$ combinaisons à 3 éléments de $A$ .

Remarques

L'ensemble des parties d'un ensemble $A$ à $n$ éléments est constitué des parties à 0 élément, 1 élément, 2 éléments, ..., $n$ éléments.

Ainsi le nombre de parties de $A$ est $\sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix})$ . Or nous avons déjà vu que le nombre de parties de $A$ est $2^{n}$ .

On en déduit que $\sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) = 2^{n}$

Propriété

Pour tout entier naturel $n$ , et pour tout entier $k$ tel que $0 \leq k \leq n$ , on a : $(\begin{matrix} n \\ k \end{matrix}) = (\begin{matrix} n \\ n - k \end{matrix})$
De plus, si $n \geq 1$ et $1 \leq k \leq n - 1$ , alors : $(\begin{matrix} n + 1 \\ k + 1 \end{matrix}) = (\begin{matrix} n \\ k \end{matrix}) + (\begin{matrix} n \\ k + 1 \end{matrix})$

Preuve : deuxième point exigible

Pour chacune de ces propriétés, deux démonstrations sont proposées : une démonstration par le calcul et une démonstration par une méthode combinatoire.

Démonstration par une méthode combinatoire :

$(\begin{matrix} n \\ k \end{matrix})$ représente le nombre parties de $k$ éléments d'un ensemble A à $n$ éléments.

Or, à chaque partie on peut associer de façon unique une autre partie : son complémentaire.

Et le complémentaire d'une partie à $k$ éléments comporte $n - k$ éléments.

Donc dénombrer les parties à $k$ éléments revient à dénombrer les parties complémentaires à $n - k$ éléments et il y en a $(\begin{matrix} n \\ n - k \end{matrix})$ .

Démonstration par le calcul :

$(\begin{matrix} n \\ n - k \end{matrix}) = \frac{n!}{(n - k)! (n - (n - k))!} = \frac{n!}{(n - k)! k!} = (\begin{matrix} n \\ k \end{matrix})$

Démonstration par une méthode combinatoire :

Soit $A$ un ensemble à $n + 1$ éléments avec $n ⩾ 1$ .

Soit $a$ un élément fixé de $A$ . Remarquons que les parties à $k + 1$ éléments de $A$ se partagent en deux catégories :

celles ne contenant pas $a$ (il y en $(\begin{matrix} n \\ k + 1 \end{matrix})$ ), car fabriquer une telle partie revient à choisir $k + 1$ éléments parmi $n$ .
celles contenant $a$ (il y en a $(\begin{matrix} n \\ k \end{matrix})$ ), car fabriquer une telle partie revient à choisir $k$ éléments parmi $n$ .

Or ces deux catégories constituent une partition de l'ensemble des parties à $k$ éléments de $A$ .

D'après le principe additif, on a donc : $(\begin{matrix} n + 1 \\ k + 1 \end{matrix}) = (\begin{matrix} n \\ k \end{matrix}) + (\begin{matrix} n \\ k + 1 \end{matrix})$

Démonstration par le calcul :

$(\begin{matrix} n \\ k \end{matrix}) + (\begin{matrix} n \\ k + 1 \end{matrix}) = \frac{n!}{k! (n - k)!} + \frac{n!}{(k + 1)! (n - k - 1)!}$

$= \frac{(n + 1)!}{(k + 1)! (n - k)!} \times (\frac{k + 1}{n + 1} + \frac{n - k}{n + 1})$

$= \frac{(n + 1)!}{(k + 1)! (n - k)!} \times \frac{n + 1}{n + 1}$

$= \frac{(n + 1)!}{(k + 1)! (n - k)!}$

$= \frac{(n + 1)!}{(k + 1)! (n + 1 - (k + 1))!}$

$= (\begin{matrix} n + 1 \\ k + 1 \end{matrix})$

6 - TRIANGLE DE PASCAL

La deuxième formule permet de calculer les nombres $(\begin{matrix} n \\ k \end{matrix})$ de proche en proche en formant le tableau suivant appelé triangle de Pascal.

$(\begin{matrix} n \\ k \end{matrix})$ n'est différent de $0$ que pour $k ⩽ n$ ; on ne remplit donc pas les cases situées au-dessus de la diagonale.
Tous les nombres de la diagonale sont obtenus en utilisant le résultat $(\begin{matrix} n \\ n \end{matrix}) = 1$ .
Tous les nombres de la première colonne sont obtenus en utilisant la formule $(\begin{matrix} n \\ 0 \end{matrix}) = 1$ .
Tous les autres nombres sont obtenus en utilisant le résultat :

« Tout nombre du tableau est la somme du nombre placé au-dessus de lui et du nombre précédant ce dernier dans le tableau »

ou encore :

$(\begin{matrix} n + 1 \\ k + 1 \end{matrix}) = (\begin{matrix} n \\ k \end{matrix}) + (\begin{matrix} n \\ k + 1 \end{matrix})$