Méthodes de dénombrement
Introduction
Après avoir défini les outils fondamentaux de la combinatoire (permutations, arrangements, combinaisons), nous allons maintenant nous concentrer sur les méthodes qui permettent de résoudre efficacement les problèmes de dénombrement. Savoir choisir la bonne technique est la clé pour réussir ces exercices.
1. Rappel des principes fondamentaux
Principe additif (OU) : Si un choix peut se faire selon plusieurs cas mutuellement exclusifs, le nombre total de possibilités est la somme des possibilités de chaque cas :
Nombre total = n₁ + n₂ + ⋯ + nₖ
Principe multiplicatif (ET) : Si un choix se décompose en étapes successives indépendantes, le nombre total de possibilités est le produit des possibilités de chaque étape :
Nombre total = n₁ × n₂ × ⋯ × nₖ
Attention : bien distinguer OU et ET :
- OU (cas exclusifs) → on additionne
- ET (étapes successives) → on multiplie
Confondre les deux est l'erreur la plus fréquente en dénombrement !
Exemple : Un menu propose 3 entrées, 5 plats et 4 desserts. On choisit une entrée OU un dessert, puis un plat.
- Choix entrée ou dessert : 3 + 4 = 7 (principe additif)
- Avec le plat : 7 × 5 = 35 menus possibles (principe multiplicatif)
2. Tirages ordonnés
2.1 Tirages ordonnés avec répétition (p-listes)
p-liste (ou p-uplet) : Une p-liste d'un ensemble E à n éléments est une suite ordonnée de p éléments de E, avec répétition possible.
Le nombre de p-listes d'un ensemble à n éléments est :
nᵖ
Quand utiliser nᵖ ? : On utilise cette formule quand :
L'ordre des éléments compte
La répétition est autorisée (on peut choisir plusieurs fois le même élément)
On effectue p choix parmi n possibilités à chaque étape
Exemple : codes et mots de passe : Code PIN à 4 chiffres (chiffres de 0 à 9, répétition autorisée) :
10⁴ = 10 000 codes possibles
Mot de passe de 6 caractères parmi 26 lettres minuscules :
26⁶ = 308 915 776 mots de passe
Exemple : plaques d'immatriculation : Une plaque est formée de 2 lettres (parmi 26), puis 3 chiffres (parmi 10), puis 2 lettres :
26² × 10³ × 26² = 456 976 000 plaques possibles
2.2 Tirages ordonnés sans répétition (arrangements)
Arrangement : Un arrangement de k éléments parmi n (avec k ≤ n) est un choix ordonné de k éléments distincts parmi n.
Aₙᵏ = (n!)/((n-k)!) = n × (n-1) × ⋯ × (n-k+1)
Quand utiliser les arrangements ? : On utilise les arrangements quand :
L'ordre des éléments compte
La répétition est interdite (chaque élément ne peut être choisi qu'une fois)
Exemple : podium : Dans une course de 12 athlètes, combien de podiums (or, argent, bronze) sont possibles ?
A₁₂³ = 12 × 11 × 10 = 1 320 podiums
L'ordre compte car les médailles sont distinctes, et un athlète ne peut pas occuper deux places.
Cas particulier : permutations : Quand k = n (on ordonne tous les éléments), l'arrangement devient une permutation :
Aₙⁿ = n!
3. Tirages non ordonnés (combinaisons)
Combinaison : Une combinaison de k éléments parmi n est un choix de k éléments sans tenir compte de l'ordre.
C(n,k) = Cₙᵏ = (n!)/(k!(n-k)!)
Quand utiliser les combinaisons ? : On utilise les combinaisons quand :
L'ordre ne compte pas (on forme un groupe, un sous-ensemble)
La répétition est interdite
Exemple : choix de délégués : De combien de façons peut-on choisir 4 délégués parmi 25 élèves ?
C(25,4) = (25!)/(4! × 21!) = (25 × 24 × 23 × 22)/(4 × 3 × 2 × 1) = 12 650
Tableau récapitulatif :
| Avec répétition | Sans répétition | |
|---|---|---|
| Ordonné | p-listes : nᵖ | Arrangements : Aₙᵏ = (n!)/((n-k)!) |
| Non ordonné | (hors programme) | Combinaisons : C(n,k) = (n!)/(k!(n-k)!) |
4. Méthode du complémentaire
Dénombrement par le complémentaire : Pour dénombrer les cas satisfaisant « au moins un », il est souvent plus simple de compter le complémentaire :
« au moins un » = total - « aucun »
Cette technique est particulièrement utile quand le cas « aucun » est simple à calculer.
Exemple : au moins une fille : On forme un groupe de 5 personnes parmi 10 garçons et 8 filles. Combien de groupes contiennent au moins une fille ?
Total de groupes (sans contrainte) :
C(18,5) = 8 568
Aucune fille (5 garçons parmi 10) :
C(10,5) = 252
Au moins une fille :
8 568 - 252 = 8 316
Exemple : mots de passe avec au moins un chiffre : Un mot de passe de 4 caractères est formé à partir de 26 lettres et 10 chiffres (36 caractères au total). Combien contiennent au moins un chiffre ?
Total : 36⁴ = 1 679 616
Aucun chiffre (4 lettres) : 26⁴ = 456 976
Au moins un chiffre : 1 679 616 - 456 976 = 1 222 640
Quand penser au complémentaire ? : Dès que vous voyez les mots :
- « au moins un / une »
- « pas tous identiques »
- « au moins deux éléments différents »
Pensez immédiatement au complémentaire !
5. Diagramme en arbre
Organiser un dénombrement avec un arbre : Un diagramme en arbre permet de visualiser toutes les issues possibles d'une expérience à plusieurs étapes :
Chaque nœud représente un choix
Chaque branche représente une option possible
Le nombre total d'issues = nombre de chemins de la racine aux feuilles
Pour compter : on multiplie le long des branches, on additionne entre les branches
Exemple : choix de tenue : On dispose de 3 hauts (H₁, H₂, H₃) et 2 bas (B₁, B₂).
L'arbre a 3 branches au premier niveau (choix du haut), chacune se divisant en 2 branches (choix du bas).
Nombre total de tenues : 3 × 2 = 6.
Les 6 tenues sont : (H₁,B₁), (H₁,B₂), (H₂,B₁), (H₂,B₂), (H₃,B₁), (H₃,B₂).
Quand utiliser un arbre ? : L'arbre est particulièrement utile quand :
- Le nombre de choix à chaque étape dépend des choix précédents
- On veut lister toutes les possibilités (petits effectifs)
- On combine des choix avec contraintes
6. Applications classiques
6.1 Codes et mots de passe
Exemple complet : mots de passe : Un mot de passe doit avoir exactement 8 caractères, composés de lettres majuscules (26) et de chiffres (10).
a) Nombre total de mots de passe (sans contrainte) :
36⁸ = 2 821 109 907 456
b) Nombre de mots de passe commençant par une lettre et finissant par un chiffre :
- 1ère position : 26 choix (lettre)
- Positions 2 à 7 : 36⁶ choix chacune
- 8ème position : 10 choix (chiffre)
26 × 36⁶ × 10 = 26 × 2 176 782 336 × 10 = 565 963 407 360
c) Nombre de mots de passe sans chiffre répété (mais lettres libres) :
Ce problème nécessite de distinguer les positions des chiffres et est plus complexe.
6.2 Mains de cartes
Jeu de 52 cartes : Un jeu standard contient 52 cartes :
- 4 couleurs (♠, ♥, ♦, ♣)
- 13 valeurs par couleur (As, 2, 3, ..., 10, Valet, Dame, Roi)
Exemple : mains de 5 cartes : Nombre total de mains de 5 cartes :
C(52,5) = (52!)/(5! × 47!) = 2 598 960
Mains contenant exactement 2 As :
- Choisir 2 As parmi 4 : C(4,2) = 6
- Choisir 3 cartes non-As parmi 48 : C(48,3) = 17 296
- Total : 6 × 17 296 = 103 776
Exemple : mains monochromes : Combien de mains de 5 cartes sont d'une même couleur (flush) ?
- Choisir la couleur : C(4,1) = 4
- Choisir 5 cartes dans cette couleur : C(13,5) = 1 287
4 × 1 287 = 5 148 mains monochromes
À retenir
Résumé :
Tirages ordonnés avec répétition (p-listes) : nᵖ possibilités
Tirages ordonnés sans répétition (arrangements) : Aₙᵏ = (n!)/((n-k)!)
Tirages non ordonnés sans répétition (combinaisons) : C(n,k) = (n!)/(k!(n-k)!)
Méthode du complémentaire : « au moins un » = total - « aucun »
Diagramme en arbre : multiplier le long des branches, additionner entre les branches
Questions clés pour choisir la bonne formule : l'ordre compte-t-il ? La répétition est-elle autorisée ?
Applications courantes : codes, mots de passe, mains de cartes, formation de comités