Algèbre et géométrie · Tle
Dénombrement : principes additif et multiplicatif
Compter sans tout énumérer : deux principes suffisent, à eux seuls, à dénombrer des ensembles bien trop grands pour qu'on les liste à la main.
La démonstration en vidéo
Le vocabulaire à connaître
- k-uplet (ou k-liste)
- Une liste ORDONNÉE de k éléments (répétitions autorisées), notée (a₁, a₂, …, aₖ). Deux k-uplets sont différents dès que l'ORDRE change.
- produit cartésien
- L'ensemble de tous les couples, triplets ou k-uplets qu'on peut former en prenant un élément dans chacun de plusieurs ensembles.
- partie d'un ensemble
- Un sous-ensemble, sans ordre entre ses éléments : {a, b} et {b, a} désignent la MÊME partie.
Ce qu'on sait
- Principe ADDITIF : si deux ensembles sont disjoints (aucun élément commun), le nombre d'éléments de leur réunion est la SOMME de leurs effectifs.
- Principe MULTIPLICATIF : le nombre d'éléments d'un produit cartésien : L'ensemble de tous les couples, triplets ou k-uplets qu'on peut former en prenant un élément dans chacun de plusieurs ensembles. de plusieurs ensembles est le PRODUIT de leurs effectifs — chaque choix se fait indépendamment des autres.
- Le nombre de k-uplets d'un ensemble à n éléments (répétitions autorisées) est nᵏ ; le nombre de partie d'un ensemble : Un sous-ensemble, sans ordre entre ses éléments : {a, b} et {b, a} désignent la MÊME partie. à n éléments est 2ⁿ.
La méthode, étape par étape
1.Je repère si la situation demande d'ADDITIONNER (des cas qui s'excluent, on ne peut être que dans l'un ou dans l'autre) ou de MULTIPLIER (des choix successifs et indépendants).
2.Pour des choix indépendants dans plusieurs ensembles, j'utilise le principe multiplicatif : je multiplie les effectifs de chaque ensemble.
3.Pour des k-uplets avec répétitions autorisées d'un ensemble à n éléments, chaque position se choisit indépendamment parmi les n éléments : n × n × … × n = nᵏ.
4.Pour le nombre de parties d'un ensemble à n éléments, je vois chaque élément comme un choix binaire (en faire partie ou non) : 2 × 2 × … × 2 = 2ⁿ.
Cas disjoints : on ADDITIONNE. Choix indépendants : on MULTIPLIE. Un ensemble à n éléments a 2ⁿ parties, et nᵏ k-uplets (répétitions autorisées).
C.Q.F.D.
L'exemple au propre
1.Un digicode utilise 4 chiffres parmi 10 (de 0 à 9), avec répétitions possibles.
2.Chacune des 4 positions se choisit indépendamment parmi 10 chiffres : c'est un 4-uplet d'un ensemble à 10 éléments.
3.10 × 10 × 10 × 10 = 10⁴ = 10 000.
4.Il existe 10 000 codes possibles.