Compter sans tout lister
La combinatoire répond à « combien ? » lorsque lister chaque arrangement serait impossible. Trois questions classiques dominent le dénombrement introductif : permutations (l’ordre compte), combinaisons (l’ordre ne compte pas) et arrangements / permutations partielles (l’ordre compte mais vous ne remplissez que k cases sur n). Chaque question a une variante avec répétition et une sans répétition.
Un point de départ concret est combinaisons sans répétition—le coefficient binomial « n parmi k »—puis bifurquer vers les variantes ordonnées ou avec répétition selon le problème.
Guide de décision
Posez les questions dans l’ordre :
- L’ordre compte-t-il ? Si oui → permutations / arrangements. Si non → combinaisons.
- Le même élément peut-il apparaître plusieurs fois ? Si oui → formules « avec répétitions ». Si non → « sans répétitions ».
- Arrangez-vous les n éléments ou seulement k d’entre eux ? Les permutations complètes utilisent n! ; les sélections partielles utilisent des factorielles décroissantes ou n^k.
Mal interpréter l’un de ces trois axes est la source habituelle d’erreurs d’un facteur en devoirs et en entretiens.
Famille de calculateurs
- Permutations sans répétition — n! arrangements ordonnés de n éléments distincts.
- Permutations avec répétition — permutations de multiensembles n! / (r₁! r₂! …) lorsqu’il existe des copies identiques.
- Combinaisons sans répétition — C(n, k) = n! / (k! (n − k)!) sous-ensembles k non ordonnés.
- Combinaisons avec répétition — C(n + k − 1, k) multiensembles de taille k parmi n types.
- Arrangements sans répétition — P(n, k) = n! / (n − k)! k-uplets ordonnés sans réutilisation.
- Arrangements avec répétition — n^k k-uplets ordonnés avec réutilisation autorisée.
Les entrées sont des entiers non négatifs avec les garde-fous habituels (k ≤ n lorsque la répétition est interdite, etc.). Les factorielles qui débordent apparaissent comme erreurs de calcul plutôt que comme infini silencieux.
Factorielles comme moteur commun
Les formules sans répétition s’appuient sur n!—le produit 1 × 2 × … × n, avec 0! = 1 par convention. Les combinaisons divisent les ordres internes de chaque sous-ensemble (k!) et parfois la queue inutilisée ((n − k)!). Les permutations partielles conservent l’ordre, elles ne divisent donc que par (n − k)!.
Les combinaisons avec répétition utilisent l’identité « stars and bars » C(n + k − 1, k). Les arrangements avec répétition sont encore plus simples : chacune des k positions choisit indépendamment l’un des n symboles → n^k.
Micro-exemples
Jeu de 52 cartes, main de 5 (ordre irrelevant, sans remise) : C(52, 5).
Course avec 8 coureurs distincts, or/argent/bronze : P(8, 3) = 8 × 7 × 6.
Code PIN à 4 chiffres, chiffres répétables : 10^4 = 10000.
Arrangements des lettres de « BOOK » : 4! / 2! à cause des deux O—permutation de multiensemble.
Acheter 3 boules parmi 5 parfums, répétitions autorisées, ordre ignoré : C(5 + 3 − 1, 3).
Associer un énoncé au bon calculateur est la compétence ; l’arithmétique est secondaire.
Relations qui évitent les erreurs
- P(n, k) = C(n, k) × k! — choisir l’ensemble, puis l’ordonner.
- n! = P(n, n) — les permutations complètes sont des permutations partielles avec k = n.
- C(n, k) = C(n, n − k) — symétrie des coefficients binomiaux.
- Interdire la répétition quand l’énoncé l’autorise sous-estime ; l’autoriser quand il l’interdit surestime.
Où ces dénombrements apparaissent
- Dénominateurs de probabilité (jeux équitables, échantillonnage)
- Esquisses de robustesse des mots de passe et identifiants (avec réserves claires sur le modèle de menace)
- Analyse d’algorithmes (espaces de recherche, énumération d’états)
- Plans expérimentaux (combinaisons de traitements)
- « Façons de finir » en sport et énigmes de classement similaires—en tant que mathématiques, pas conseil de pari
Un grand n croît plus vite que l’intuition. C(60, 6) représente déjà des millions ; les factorielles au-delà d’un n modeste débordent les flottants à précision fixe—d’où des helpers dédiés et des bibliothèques de grands entiers en production.
Séquence pédagogique
- Compter les permutations d’un petit n par listage, puis introduire n!.
- Introduire P(n, k) avec des exemples de podium.
- Montrer C(n, k) en divisant l’ordre.
- Ajouter la répétition : d’abord n^k (positions indépendantes), puis stars and bars.
- Seulement ensuite les permutations de multiensembles avec lettres répétées.
Passer directement à six formules similaires sans le guide de décision produit un branchement mécanique sans compréhension.
Notes d’implémentation
Calculer C(n, k) via trois factorielles complètes est simple mais déborde tôt. Les algorithmes multiplicatifs réduisent la taille intermédiaire. Les helpers de ce hub utilisent une division factorielle avec garde-fous de finitude adaptés à l’éducation interactive—pas pour des n à l’échelle cryptographique. Rejeter les non-entiers et les paires (n, k) impossibles avec des raisons d’erreur stables.
Pièges courants
- Traiter « comité de 5 » comme une permutation
- Utiliser n^k pour des tirages sans remise quand l’ordre n’importe pas
- Oublier de diviser par les factorielles des lettres identiques dans les problèmes de mots
- Confondre combinaisons avec répétition et sans répétition lors d’achats « jusqu’à k articles »
Résumé
Ce hub regroupe six outils élémentaires de dénombrement : permutations complètes et de multiensembles, combinaisons avec et sans répétition, et arrangements partiels avec et sans répétition. Décidez si l’ordre et la réutilisation s’appliquent, choisissez la formule correspondante et vérifiez avec un petit listage. Les calculateurs automatisent l’arithmétique pour que vous puissiez vous concentrer sur la modélisation correcte de l’énoncé.