Dénombrement et produit cartésien
Note préalable : cette page a été rédigée pour les élèves de terminale générale, spécialité maths.
Comment décompter le nombre d’éléments d’un ensemble ? Bien sûr, on peut les compter un par un, en s’aidant éventuellement d’un arbre de dénombrement. Opération fastidieuse et peu élégante. On peut aussi et surtout employer les techniques de l’analyse combinatoire.
Le cardinal
Le nombre d’éléments d’un ensemble \(E\) est son cardinal. Il se note \(Card(E).\)
Par exemple, si \(E\) est l’ensemble des entiers pairs compris entre 1 et 9, nous avons \(Card(E) = 4\) puisque \(E = \{2 ;4 ;6 ;8\}.\) Le cardinal de l’ensemble vide est égal à 0.
Réunions et principe additif
Si \(A\) et \(B\) sont deux ensembles disjoints alors \(Card (A ∪ B)\) \(= Card(A) + Card(B).\) Le principe ne se limite d’ailleurs pas à deux ensembles disjoints. Sinon, \(Card (A ∪ B)\) \(= Card(A) + Card(B) - Card(A ∩ B).\) Ceci doit d’ailleurs vous rappeler des souvenirs de seconde.
Par exemple, \(A = \{1 ;2 ;3\}\) et \(B = \{2 ;4\}\) donc \(A ∪ B = \{1 ;2 ;3 ;4\}\) et \(Card(A ∪ B) = 4.\)
En principe, on utilise le principe additif lorsque les ensembles sont disjoints (voir par exemple les démonstrations de combinatoires).
Produits cartésiens
Soit deux ensembles \(A\) et \(B.\)
\(Card(A × B) = Card(A) × Card(B)\)
Le produit cartésien de deux ensembles est l’ensemble des couples dont le premier élément appartient au premier ensemble et le second élément au second ensemble. Par exemple, l’ensemble \(A\) est celui des couleurs d’un jeu de 32 cartes (cœur, carreau, trèfle et pique) et \(B\) est celui des valeurs (as, roi, dame, valet, 10, 9, 8 et 7). Le nombre de cartes dans le jeu est bien de \(4 × 8 = 32.\)
Lorsque \(A\) et \(B\) sont un même ensemble, on parle de carré cartésien. Par exemple le plan cartésien est défini par \(\mathbb{R } × \mathbb{R }\) (l’ensemble des abscisses et celui des ordonnées sont tous deux l’ensemble des réels).
La formule s’étend là aussi à plus de deux ensembles.
On en déduit \(Card(A^n) = Card(A)^n.\)
On utilise le produit quand on peut déterminer le cardinal par étapes. Typiquement, la permutation utilise ce principe.
Prenons encore un exemple. Soit quatre lettres A, B, C et D. Combien a-t-on de façons de les disposer en les utilisant toutes une seule fois ?
Pour la première lettre, il y a 4 possibilités. Pour la deuxième, il n’y en a plus que 3 puisque la quatrième lettre est déjà prise. Pour la troisième il y en a 2. Lorsqu’on a les trois premières lettres, il n’y a plus de choix pour la quatrième.
Nous avons donc \(4 \times 3 × 2 × 1 = 24\) possibilités. Nous avons bien utilisé la multiplication.
On peut aussi écrire le résultat sous forme de factorielle : \(4 ! = 24\)
La réalisation d’un arbre est plus longue…
Nous visualisons bien les 24 possibilités.
Ceci nous amène à une propriété du cardinal d’un produit cartésien. Si un arbre comporte \(n\) branches de premier niveau se subdivisant chacune en \(p\) sous-branches, alors l’arbre comporte \(n × p\) feuilles. Ici, \(4 × 3 × 2 = 24.\)
Parties d’un ensemble fini
L’ensemble des parties d’un ensemble \(E\) est l’ensemble dont les éléments sont les sous-ensembles de \(E.\) On le note \(\mathcal{P}(E).\) C’est après le bac que l’on mesure la richesse de cette notion. En attendant, sachez que si \(E\) possède \(n\) éléments, alors le nombre de parties de \(E\) est \(Card(\mathcal{P}(E)) = 2^n.\)
Le nombre de parties de \(k\) éléments parmi \(n\) est une combinaison. Ce nombre est aussi appelé coefficient binomial.
Soit une main de cinq cartes d’un jeu de 52. Combien existe-t-il de mains différentes comportant une paire d’as ?
D’abord, combien y a-t-il de possibilités de paires d’as ? En d’autres termes, combien de parties de 2 as parmi 4 ? C’est une combinaison. On peut faire la liste des possibilités ou utiliser la calculatrice. On en trouve 6. Si on les liste : {♥ ;♦}, {♥ ;♣}, {♥ ;♠}, {♦ ;♣}, {♦ ;♠} et {♣ ;♠}.
Combien de possibilités pour les autres cartes ? Il y en a 3 parmi 48. \(\left( {\begin{array}{*{20}{c}}{48}\\3\end{array}} \right) = 17296.\) Cette fois, on aurait du mal à faire la liste...
Il nous reste à établir le cardinal du produit cartésien entre l’ensemble des paires d’as et celui des triplets de non-as. \(6 × 17296 = 103776.\)
