Dénombrement et combinatoire : fiche de révision
k-uplets, arrangements, permutations, combinaisons : savoir compter sans se tromper, choisir la bonne formule et éviter les doubles comptages.
1Les principes de base
Principe additif : si une situation se décompose en cas DISJOINTS, on additionne les nombres de possibilités. Principe multiplicatif : si une situation se construit par étapes successives INDÉPENDANTES en nombre de choix, on multiplie. Ces deux principes suffisent à retrouver toutes les formules.
Question clé avant tout calcul : l'ordre compte-t-il ? et les répétitions sont-elles autorisées ? Ces deux réponses déterminent la formule à employer.
2Les quatre formules
k-uplets d'un ensemble à n éléments (ordre, répétitions autorisées) : nᵏ. Exemple : nombre de codes PIN à 4 chiffres = 10⁴.
Arrangements de k éléments parmi n (ordre, SANS répétition) : n × (n−1) × … × (n−k+1) = n!/(n−k)!. Exemple : podiums possibles avec 8 coureurs = 8 × 7 × 6 = 336.
Permutations de n éléments (tous les éléments, ordonnés) : n! = n × (n−1) × … × 1. Exemple : anagrammes d'un mot à 5 lettres distinctes = 5! = 120.
Combinaisons de k éléments parmi n (SANS ordre, sans répétition) : C(n, k) = n! / (k!(n−k)!), lu « k parmi n ». Exemple : mains de 5 cartes dans un jeu de 32 = C(32, 5) = 201 376. Une combinaison est une PARTIE (un sous-ensemble) à k éléments.
3Propriétés des coefficients binomiaux
Symétrie : C(n, k) = C(n, n−k) — choisir k éléments revient à choisir les n−k éléments écartés. Valeurs particulières : C(n, 0) = C(n, n) = 1, C(n, 1) = n. Relation de Pascal : C(n, k) = C(n−1, k−1) + C(n−1, k), qui construit le triangle de Pascal (un élément donné est soit pris — reste k−1 à choisir parmi n−1 — soit écarté).
Somme d'une ligne : C(n, 0) + C(n, 1) + … + C(n, n) = 2ⁿ, le nombre total de parties d'un ensemble à n éléments.
4Méthode et pièges — exemple corrigé
Exemple : dans une classe de 25 élèves, combien de délégations de 3 élèves contenant au moins une fille, s'il y a 14 filles et 11 garçons ?
Méthode du complémentaire (réflexe pour « au moins un ») : total − aucune fille = C(25, 3) − C(11, 3) = 2 300 − 165 = 2 135.
Pièges classiques : utiliser un arrangement quand l'ordre ne compte pas (une délégation n'est pas un podium) ; compter deux fois les mêmes objets en découpant en cas NON disjoints ; traiter « au moins un » par addition de cas au lieu du complémentaire (possible mais périlleux) ; confondre nᵏ (répétitions autorisées) avec l'arrangement (sans répétition). Toujours annoncer le modèle choisi : « l'ordre ne compte pas, sans répétition : combinaisons ».
Définitions à connaître par cœur
Quiz : teste-toi sur dénombrement et combinatoire
8 questions corrigées. Réponds avant d'ouvrir la correction !
1. Nombre de codes à 4 chiffres (0-9) :
- A.4¹⁰
- B.10 × 9 × 8 × 7
- C.10⁴
- D.C(10, 4)
Voir la réponse
Réponse : C. 10⁴
Ordre et répétitions : ce sont des 4-uplets d'un ensemble à 10 éléments, soit 10⁴.
2. Nombre de podiums (1er, 2e, 3e) avec 8 coureurs :
- A.8³
- B.C(8, 3)
- C.8 × 7 × 6
- D.8!
Voir la réponse
Réponse : C. 8 × 7 × 6
Ordre sans répétition : arrangement de 3 parmi 8 = 336.
3. C(n, k) compte…
- A.les listes ordonnées de k éléments
- B.les sous-ensembles à k éléments
- C.les permutations de k éléments
- D.les k-uplets
Voir la réponse
Réponse : B. les sous-ensembles à k éléments
Une combinaison est une partie à k éléments : l'ordre ne compte pas.
4. C(n, k) = …
- A.n!/(n−k)!
- B.n!/(k!(n−k)!)
- C.k!/(n−k)!
- D.nᵏ/k!
Voir la réponse
Réponse : B. n!/(k!(n−k)!)
On divise l'arrangement n!/(n−k)! par k! pour effacer l'ordre des k éléments choisis.
5. C(n, k) = C(n, n−k) car…
- A.le triangle de Pascal est symétrique par hasard
- B.choisir k éléments revient à choisir les n−k écartés
- C.k = n−k toujours
- D.c'est une convention
Voir la réponse
Réponse : B. choisir k éléments revient à choisir les n−k écartés
La symétrie a une interprétation ensembliste directe.
6. C(n, 0) + C(n, 1) + … + C(n, n) = …
- A.n!
- B.n²
- C.2ⁿ
- D.nⁿ
Voir la réponse
Réponse : C. 2ⁿ
C'est le nombre total de parties d'un ensemble à n éléments.
7. Pour compter les tirages avec « au moins un as », le réflexe est…
- A.additionner tous les cas
- B.passer par le complémentaire « aucun as »
- C.multiplier par 4
- D.utiliser une permutation
Voir la réponse
Réponse : B. passer par le complémentaire « aucun as »
Total moins « aucun » évite les découpages en cas multiples et les doubles comptages.
8. La relation de Pascal s'écrit :
- A.C(n, k) = C(n−1, k) + C(n, k−1)
- B.C(n, k) = C(n−1, k−1) + C(n−1, k)
- C.C(n, k) = C(n+1, k) − C(n, k+1)
- D.C(n, k) = k C(n−1, k−1)
Voir la réponse
Réponse : B. C(n, k) = C(n−1, k−1) + C(n−1, k)
Fixe un élément : soit il est choisi (C(n−1, k−1)), soit il ne l'est pas (C(n−1, k)).
Questions fréquentes
Comment choisir entre arrangement et combinaison ?
Pose la question de l'ordre : si permuter les éléments choisis change l'objet compté (podium, mot, code), c'est un arrangement ; si non (équipe, main de cartes, délégation), c'est une combinaison.
Comment traiter les questions « au moins un » ?
Passe par l'événement complémentaire « aucun » : nombre cherché = total − nombre de cas sans l'objet. C'est plus court et plus sûr que d'additionner « exactement 1 » + « exactement 2 » + …
Que vaut 0! et pourquoi ?
0! = 1 par convention : elle rend les formules cohérentes (C(n, 0) = n!/(0!n!) = 1 — il y a bien une seule façon de ne rien choisir : la partie vide).
Faut-il savoir calculer les coefficients binomiaux à la main ?
Oui pour les petits cas (simplifier n!/(k!(n−k)!) en produit court : C(8, 3) = (8×7×6)/(3×2×1) = 56) ; la calculatrice les donne directement pour les grands.