Terminale générale Mathématiques Combinatoire et dénombrement

Décrire un ensemble d'objets à l'aide de réunions, de produits ou de parties d'ensembles permet de les dénombrer rigoureusement.

I Réunion de deux ensembles

Définition : La réunion de deux ensembles $A$ et $B$ est l'ensemble des éléments appartenant à $A$ ou à $B$ ; elle est notée $A \cup B$ .

À noter

L'intersection de deux ensembles $A$ et $B$ est l'ensemble des éléments appartenant à $A$ et à $B$ ; elle est notée $A \cap B$ .

Principe additif : Soient A et B deux ensembles disjoints (d'intersection vide). Si m et n sont les nombres d'éléments respectifs de A et de B, alors la réunion de A et B comporte $m + n$ éléments.

À noter

Si les deux ensembles ne sont pas disjoints, il faut ôter au résultat le nombre d'éléments $r$ de leur intersection.

II Produit cartésien

Définitions : Le produit cartésien de deux ensembles $A$ et $B$ est l'ensemble des couples $(a, b)$ tels que $a \in A$ et $b \in B$ . Il est noté $A \times B$ .

On note $A^{k}$ l'ensemble $\underset{k termes}{\underset{︸}{A \times A \times \dots \times A}}$ , ces éléments sont des $k$ -uplets.

Principe multiplicatif : Si $m$ et $n$ (entiers naturels non nuls) sont les nombres d'éléments respectifs de deux ensembles $A$ et $B$ , alors le produit cartésien $A \times B$ comporte $m \times n$ éléments.

Soit $A$ un ensemble à $n$ éléments et $k$ un entier naturel non nul. L'ensemble $A^{k}$ des $k$ -uplets ( $k$ -listes) d'éléments de $A$ comporte $n^{k}$ éléments.

III Parties d'un ensemble

Définition : Un ensemble $A$ est une partie d'un ensemble $E$ si et seulement si tous les éléments de $A$ sont des éléments de $E$ . On écrit alors $A \subset E$ .

On dit également que A est un sous-ensemble de E.

Théorème : Le nombre de parties d'un ensemble à $n$ éléments est $2^{n}$ .

À noter

C'est également le nombre de $n$ -uplets de l'ensemble $\{0; 1\}$ .

Méthodes

1 Déterminer le nombre d'éléments d'une réunion d'ensembles

Déterminer le nombre d'entiers naturels inférieurs à 199 dont l'écriture décimale comporte le chiffre 0.

Conseils

Regroupez les nombres considérés en plusieurs ensembles facilement dénombrables.

Solution

On considère les ensembles disjoints suivants :

$A = \{0; 10; \dots; 90\}$ , le sous-ensemble de ces entiers inférieurs à 99 ;

$B = \{100; \dots; 109\}$ , le sous-ensemble de ces entiers compris entre 100 et 109 et $C = \{110; \dots; 190\}$ le sous-ensemble de ces entiers supérieurs à 109.

$A$ et $B$ ont chacun 10 éléments et $C$ en a 9. Il y a donc en tout 29 entiers naturels inférieurs à 199 dont l'écriture décimale comporte le chiffre 0.

2 Utiliser le produit cartésien

Les cartes d'un jeu sont numérotées de 1 à 3 et coloriées en rouge, vert, bleu, jaune ou noir. Toutes les cartes de ce jeu sont différentes et ce jeu contient toutes les cartes possibles.

Combien y a-t-il de cartes dans ce jeu ?

Conseils

Caractérisez chaque carte par un couple.

Solution

Considérons $N = \{1; 2; 3\}$ et $C = \{rouge; vert; bleu; jaune; noir\}$ . Alors chaque couple de $N \times C$ définit une unique carte du jeu complet.

Il y a donc $3 \times 5$ = 15 cartes dans ce jeu.

3 Dénombrer le nombre de parties d'un ensemble

Un caractère Braille est représenté par deux colonnes de trois points chacune, chaque point étant ou non en relief.

Combien peut-on former de caractères différents, sachant qu'au moins un des points doit être en relief ?

Conseils

Considérez un caractère comme une partie d'un ensemble à six éléments.

Solution

Considérons l'ensemble B des six points des deux colonnes, tous ces points étant en relief. Fabriquer un caractère braille, c'est choisir les points qui seront en relief, c'est-à-dire choisir une partie de B différente de la partie vide (un au moins des points est en relief) : il y a donc $2^{6} - 1$ choix possibles, soit 63 caractères brailles.

Réunion, produit et parties d'ensembles

I Réunion de deux ensembles

À noter

À noter

II Produit cartésien

III Parties d'un ensemble

À noter

Méthodes

1 Déterminer le nombre d'éléments d'une réunion d'ensembles

Conseils

Solution

2 Utiliser le produit cartésien

Conseils

Solution

3 Dénombrer le nombre de parties d'un ensemble

Conseils

Solution

Pour lire la suite