Combien de codes de carte bancaire existe-t-il ? De combien de façons peut-on former une équipe de 5 joueurs parmi 12 ? Combien de mains différentes au poker ? Le dénombrement est l’art de compter sans énumérer un à un. En Terminale, c’est l’outil indispensable pour calculer des probabilités en situation d’équiprobabilité, et il prépare la loi binomiale. Prends ton temps : la difficulté n’est pas le calcul, c’est de choisir le bon modèle (ordre ou non, répétition ou non).
1. Ensembles finis et cardinal
Un ensemble E est fini s’il a un nombre fini d’éléments. Ce nombre est son cardinal, noté Card(E) ou |E|. Le cardinal de l’ensemble vide ∅ est 0.
Pour deux parties A et B d’un ensemble E, on rappelle : la réunion A ∪ B (éléments de A ou de B), l’intersection A ∩ B (éléments à la fois dans A et dans B), et le complémentaire de A dans E, noté A̅ (éléments de E qui ne sont pas dans A). Deux ensembles sont disjoints si A ∩ B = ∅.
- Si A et B sont disjoints : |A ∪ B| = |A| + |B| (principe additif).
- En général : |A ∪ B| = |A| + |B| − |A ∩ B|.
- Complémentaire : |A̅| = |E| − |A|.
Démonstration. Dans |A| + |B|, les éléments de A ∩ B sont comptés deux fois : on les retire une fois pour obtenir |A ∪ B|. Pour le complémentaire, E est la réunion disjointe de A et A̅, donc |E| = |A| + |A̅|.
Dans un club de 30 adhérents, 17 pratiquent le tennis, 12 le badminton et 5 les deux. Combien pratiquent au moins un de ces sports ? Aucun ?
|T ∪ B| = 17 + 12 − 5 = 24 adhérents pratiquent au moins un des deux sports. Aucun : 30 − 24 = 6.
Les parties A1, …, Ap forment une partition de E si elles sont non vides, deux à deux disjointes, et si leur réunion est E. Alors |E| = |A1| + … + |Ap|. C’est la technique des « cas séparés » : on découpe un problème en cas qui ne se chevauchent pas, puis on additionne.
2. Produit cartésien et k-uplets
Le produit cartésien de deux ensembles E et F est l’ensemble E × F des couples (x ; y) avec x ∈ E et y ∈ F. Plus généralement, E1 × … × Ek est l’ensemble des k-uplets (x1 ; … ; xk) avec xi ∈ Ei. Dans un k-uplet, l’ordre compte et les éléments peuvent se répéter.
|E1 × … × Ek| = |E1| × … × |Ek|. En particulier, le nombre de k-uplets d’un ensemble E à n éléments est nk.
Pourquoi ? Si l’on choisit d’abord x1 (n1 façons) puis x2 (n2 façons, quel que soit x1), on obtient n1 × n2 couples : l’arbre ci-dessous le montre.
Un cadenas a 4 molettes numérotées de 0 à 9. Un code est un 4-uplet de {0 ; … ; 9} : il y a 104 = 10 000 codes possibles.
Le principe multiplicatif exige que le nombre de choix à une étape ne dépende pas du résultat des étapes précédentes. Sinon, on le fait varier étape par étape (voir les arrangements) ou on sépare en cas.
3. Arrangements et permutations
Pour n ∈ ℕ*, n ! = 1 × 2 × 3 × … × n, et par convention 0 ! = 1. Ainsi 5 ! = 120 et 7 ! = 5 040.
Un arrangement de k éléments d’un ensemble E à n éléments est un k-uplet d’éléments deux à deux distincts de E (0 ≤ k ≤ n). L’ordre compte, pas de répétition.
Le nombre d’arrangements de k éléments parmi n est n × (n − 1) × … × (n − k + 1) = n ! / (n − k) !. On le note Ank.
En effet : n choix pour le premier élément, n − 1 pour le deuxième (il doit être différent), …, n − k + 1 pour le k-ième.
Dans une course de 12 coureurs, combien de podiums (1er, 2e, 3e) existe-t-il ? On choisit 3 coureurs distincts dans un ordre précis : A123 = 12 × 11 × 10 = 1 320.
Une permutation de E (n éléments) est un arrangement des n éléments, c’est-à-dire une façon de ranger tous les éléments dans un ordre. Il y en a n !.
Les 3 lettres A, B, C se rangent de 3 × 2 × 1 = 3 ! = 6 façons, comme le montre l’arbre.
Si un mot de n lettres contient la lettre répétée a fois, une autre b fois, etc., le nombre d’anagrammes distinctes est n ! / (a ! × b ! × …). Exemple : « SOLEIL » (6 lettres dont deux L) donne 6 ! / 2 ! = 360 anagrammes.
4. Combinaisons et coefficients binomiaux
Une combinaison de k éléments de E (n éléments) est une partie de E à k éléments : l’ordre ne compte pas, et il n’y a pas de répétition. Le nombre de ces parties est le coefficient binomial « k parmi n », noté (nk) ou Cnk. On écrira ici C(n, k).
Pour 0 ≤ k ≤ n : C(n, k) = Ank / k ! = n ! / (k ! × (n − k) !).
Démonstration. Chaque partie à k éléments peut être rangée dans k ! ordres différents. Il y a donc k ! fois plus d’arrangements que de combinaisons : Ank = k ! × C(n, k).
Choisir 3 délégués dans une classe de 25 : C(25, 3) = (25 × 24 × 23) / (3 × 2 × 1) = 2 300. Si les trois délégués avaient des rôles distincts (président, secrétaire, trésorier), ce serait un arrangement : 13 800.
- C(n, 0) = C(n, n) = 1 ; C(n, 1) = C(n, n − 1) = n.
- Symétrie : C(n, k) = C(n, n − k). (Choisir les k éléments qu’on prend revient à choisir les n − k qu’on laisse.)
Pour C(10, 7), utilise la symétrie : C(10, 7) = C(10, 3) = (10 × 9 × 8) / 6 = 120. On simplifie toujours avant de multiplier.
5. Triangle de Pascal et formule du binôme
Pour 1 ≤ k ≤ n − 1 : C(n, k) = C(n − 1, k − 1) + C(n − 1, k).
Démonstration. Fixons un élément a de E (n éléments). Les parties à k éléments se séparent en deux cas disjoints : celles qui contiennent a (on choisit les k − 1 autres parmi n − 1 : C(n − 1, k − 1)) et celles qui ne contiennent pas a (on choisit k éléments parmi n − 1 : C(n − 1, k)). On additionne : principe additif.
Cette relation permet de construire le triangle de Pascal : chaque nombre est la somme des deux nombres au-dessus de lui. La ligne n contient les C(n, k) pour k de 0 à n.
Sur la figure, 15 = 5 + 10 : C(6, 2) = C(5, 1) + C(5, 2).
Pour tous réels a et b et tout entier n : (a + b)n = Σk=0n C(n, k) ak bn−k. Les coefficients sont ceux de la ligne n du triangle.
(a + b)4 = a4 + 4a3b + 6a2b2 + 4ab3 + b4 (ligne 4 : 1, 4, 6, 4, 1).
6. Parties d’un ensemble
Un ensemble à n éléments possède 2n parties (∅ et E compris). En d’autres termes : Σk=0n C(n, k) = 2n.
Démonstration. Pour former une partie, chaque élément est soit pris, soit non pris : 2 choix par élément, donc 2 × 2 × … × 2 = 2n (principe multiplicatif). D’autre part, en regroupant les parties selon leur nombre d’éléments k, on trouve C(n, k) parties de chaque taille, d’où la somme. On retrouve aussi ce résultat avec le binôme pour a = b = 1.
Pour E = {a ; b ; c} : 23 = 8 parties : ∅, {a}, {b}, {c}, {a ; b}, {a ; c}, {b ; c}, E. Ligne 3 du triangle : 1 + 3 + 3 + 1 = 8.
Avec a = 1 et b = −1 dans le binôme : Σ(−1)k C(n, k) = 0, donc les parties de taille paire et de taille impaire sont aussi nombreuses : 2n−1 chacune (pour n ≥ 1).
7. Méthode : résoudre un problème de dénombrement
- Que compte-t-on exactement ? Définis l’objet (un mot, un tirage, une main, un chemin…).
- L’ordre compte-t-il ?
- Y a-t-il des répétitions possibles (avec remise) ?
- Le problème se décompose-t-il en étapes successives (produit) ou en cas disjoints (somme) ?
| Ordre | Répétition | Modèle | Nombre (n éléments, k choisis) |
|---|---|---|---|
| oui | oui | k-uplet | nk |
| oui | non | arrangement | n ! / (n − k) ! |
| oui | non (k = n) | permutation | n ! |
| non | non | combinaison | C(n, k) |
Un sac contient 9 jetons dont 4 rouges. On tire simultanément 3 jetons. Combien de tirages contiennent au moins un jeton rouge ? Total : C(9, 3) = 84. Sans aucun rouge (3 jetons parmi les 5 non rouges) : C(5, 3) = 10. Donc 84 − 10 = 74 tirages.
Choisir 3 personnes parmi 5 femmes et 4 hommes avec exactement 2 femmes : C(5, 2) × C(4, 1) = 10 × 4 = 40 (deux étapes : on choisit les femmes, puis l’homme).
- « Tirage simultané » ou « sans ordre » : combinaison. « Tirages successifs » : l’ordre compte (arrangement sans remise, nk avec remise).
- Ne jamais additionner des cas qui se chevauchent : vérifie qu’ils sont disjoints.
- « Au moins un » : pense au complémentaire (« aucun »).
On va de A à B en ne faisant que des pas vers la droite (D) ou vers le haut (H). Sur un quadrillage de 5 colonnes et 3 lignes, tout chemin comporte 5 D et 3 H, soit 8 pas ; il est déterminé par la position des 3 pas H parmi les 8 : C(8, 3) = 56 chemins.
8. Lien avec les probabilités
Si l’univers Ω est fini et que toutes les issues sont équiprobables, la probabilité d’un événement A est P(A) = |A| / |Ω| = (nombre de cas favorables) / (nombre de cas possibles).
On tire simultanément 2 cartes d’un jeu de 32. Probabilité d’obtenir deux as ? Univers : C(32, 2) = 496 mains. Cas favorables : C(4, 2) = 6. P = 6 / 496 = 3248.
Dans ce chapitre, le travail consiste donc à bien compter |A| et |Ω| avec le même modèle : si tu comptes l’univers avec l’ordre, compte les cas favorables avec l’ordre aussi (ou, dans les deux, sans ordre).
Pour deux dés discernables, les 36 couples sont équiprobables, mais pas les 21 sommes ni les 21 « paires non ordonnées » : les doubles sont deux fois moins probables que les autres paires.
9. Dénombrer avec Python
Le module math fournit factorial, comb et perm ; le module itertools génère et permet de vérifier les listes.
from math import factorial, comb, perm
from itertools import combinations, permutations, product
print(factorial(5)) # 120
print(perm(12, 3)) # 1320 arrangements
print(comb(8, 3)) # 56 combinaisons
print(len(list(product(range(10), repeat=4)))) # 10000 codes
print(len(list(combinations(range(6), 3)))) # 20 parties à 3 éléments
print(len(set(permutations("SOLEIL")))) # 360 anagrammes
Pour programmer la relation de Pascal, on peut construire une ligne à partir de la précédente :
def ligne_suivante(L):
return [1] + [L[i] + L[i + 1] for i in range(len(L) - 1)] + [1]
L = [1]
for n in range(6):
L = ligne_suivante(L)
print(L) # [1, 6, 15, 20, 15, 6, 1]
Quand tu hésites sur ton calcul, vérifie avec une petite version du problème (3 ou 4 éléments) : liste tout à la main, puis compare avec ta formule. Si ça marche en petit, ça marchera en grand !
À retenir
- |A ∪ B| = |A| + |B| − |A ∩ B| ; |A̅| = |E| − |A|.
- Principe multiplicatif : on multiplie les nombres de choix d’étapes successives ; k-uplets d’un ensemble à n éléments : nk.
- Arrangements (ordre, sans répétition) : n ! / (n − k) ! ; permutations : n !.
- Combinaisons (sans ordre) : C(n, k) = n ! / (k ! (n − k) !) ; symétrie C(n, k) = C(n, n − k).
- Pascal : C(n, k) = C(n − 1, k − 1) + C(n − 1, k) ; binôme : (a + b)n = Σ C(n, k) ak bn−k.
- Un ensemble à n éléments a 2n parties ; Σ C(n, k) = 2n.
- Équiprobabilité : P(A) = |A| / |Ω|, avec un modèle de comptage cohérent.
- « Au moins un » : passer par le complémentaire.