Combinatoire et Dénombrement

Cours · mathématiques (terminale), chapitre 7 · terminale, spécialité mathématiques · le début du chapitre, la suite sur Adloun

Le triangle de Pascal, où 3 + 3 = 6 illustre la relation de Pascal.

Ce chapitre traite du dénombrement, c'est-à-dire de l'art de compter le nombre d'éléments d'un ensemble fini sans pour autant les énumérer tous. Les outils développés ici (permutations, arrangements, combinaisons) sont fondamentaux pour le calcul des probabilités.

7.1 Principes Fondamentaux du Dénombrement

Soit $E$ un ensemble fini. On note $Card (E)$ (ou $# E$ ) le cardinal de $E$ , c'est-à-dire le nombre d'éléments de $E$ .

7.1.1 Principe additif

Le principe additif concerne la réunion d'ensembles disjoints.

◆Théorème 7.1Principe additif

Si $A$ et $B$ sont deux sous-ensembles d'un ensemble $E$ , disjoints ( $A \cap B = \emptyset$ ), alors :

$Card (A \cup B) = Card (A) + Card (B)$

Plus généralement, si $A_{1}, A_{2}, \dots, A_{k}$ sont deux à deux disjoints :

$Card (A_{1} \cup A_{2} \cup \dots \cup A_{k}) = Card (A_{1}) + Card (A_{2}) + \dots + Card (A_{k})$

Enfin, si $A$ et $B$ sont quelconques :

$Card (A \cup B) = Card (A) + Card (B) - Card (A \cap B)$

7.1.2 Produit cartésien et principe multiplicatif

Définition 7.2Couple,

k

-uplet, produit cartésien

Un couple $(x, y)$ est la donnée de deux éléments dans un ordre déterminé ; un $k$ -uplet $(x_{1}, \dots, x_{k})$ est la donnée ordonnée de $k$ éléments.
Le produit cartésien de deux ensembles $E$ et $F$ , noté $E \times F$ , est l'ensemble des couples $(x, y)$ avec $x \in E$ et $y \in F$ . On définit de même $E_{1} \times E_{2} \times \dots \times E_{k}$ (ensemble des $k$ -uplets).
On note $E^{k} = E \times E \times \dots \times E$ ( $k$ facteurs) l'ensemble des $k$ -uplets d'éléments de $E$ .

◆Théorème 7.3Principe multiplicatif

Si $E$ et $F$ sont finis :

$Card (E \times F) = Card (E) \times Card (F)$

Plus généralement, pour une succession de choix où le premier choix offre $n_{1}$ possibilités, le deuxième $n_{2}$ possibilités, ..., et le $k$ -ième choix $n_{k}$ possibilités, le nombre total de configurations est :

$N = n_{1} \times n_{2} \times \dots \times n_{k}$

Deux images rendent ce principe évident, et il faut savoir passer de l'une à l'autre : le produit cartésien $E \times F$ est un rectangle de couples (autant de lignes que d'éléments de $E$ , autant de colonnes que d'éléments de $F$ ) ; la même situation vue comme une succession de choix devient un arbre, dont on compte les feuilles.

Définition 7.4

p

-uplet ou liste d'un ensemble

Soit $E$ un ensemble à $n$ éléments. Un $p$ -uplet (ou liste de longueur $p$ ) d'éléments de $E$ est une suite ordonnée de $p$ éléments de $E$ , avec répétitions possibles — c'est un élément de $E^{p}$ . D'après le principe multiplicatif, le nombre de $p$ -uplets d'un ensemble à $n$ éléments est :

$Card (E^{p}) = n^{p}$

7.1.3 Nombre de parties d'un ensemble

◆Théorème 7.5Nombre de parties

Un ensemble $E$ à $n$ éléments possède exactement $2^{n}$ parties (sous-ensembles), y compris l'ensemble vide $\emptyset$ et $E$ lui-même.

Exercices du chapitre

Calculs de coefficients binomiaux et propriétés corrigé
Résolution d'équations avec coefficients binomiaux corrigé
Démonstration de la formule de Pascal corrigé
Anagrammes avec répétitions de lettres corrigé
Nombre de sous-ensembles (Somme des coefficients binomiaux) corrigé
Problème — Identités binomiales combinatoires et algébriques corrigé

La suite du cours · Tous les exercices du chapitre