La question centrale : l'ordre compte-t-il ?
Les permutations et les combinaisons comptent toutes deux le nombre de façons de choisir r éléments parmi un groupe de n éléments distincts, mais elles répondent à deux questions différentes. Une permutation compte le nombre de façons de choisir et d'arranger r éléments, de sorte que deux sélections contenant les mêmes éléments dans un ordre différent sont comptées comme deux résultats distincts. Une combinaison ne compte que le nombre de façons de choisir r éléments, de sorte que deux sélections contenant les mêmes éléments sont comptées comme un seul et même résultat, quel que soit l'ordre dans lequel ils ont été choisis.
Un moyen simple de trancher : imaginez deux sélections utilisant exactement les mêmes éléments mais les listant ou les arrangeant différemment. Si ces deux sélections représentent des résultats réels véritablement différents — classements différents, mots de passe différents, ordres d'arrivée différents dans une course — l'ordre compte et une permutation est le bon calcul. Si ces deux sélections représentent le même résultat réel — le même comité, la même main de cartes, le même ensemble de numéros de loterie — l'ordre ne compte pas et une combinaison est le bon calcul.
Les formules : nPr et nCr, avec un exemple vérifié
Le nombre de permutations de r éléments choisis parmi n éléments distincts est nPr = n! / (n − r)!, et le nombre de combinaisons est nCr = n! / [r! (n − r)!] — la formule de combinaison est la formule de permutation divisée par r!, car diviser par r! élimine les r! arrangements différents de chaque groupe d'éléments identiques que le calcul de permutation traite comme distincts.
Exemple résolu : choisir 3 éléments parmi un groupe de 7. Permutations : 7P3 = 7! / (7−3)! = 7 × 6 × 5 = 210. Combinaisons : 7C3 = 7! / (3! × 4!) = (7 × 6 × 5) / (3 × 2 × 1) = 210 / 6 = 35. Le nombre de combinaisons est exactement le nombre de permutations divisé par 3! = 6, ce qui confirme la relation nCr = nPr / r!.
| Quantité | Formule | Valeur pour n=7, r=3 |
|---|---|---|
| Permutations (l'ordre compte) | nPr = n! / (n − r)! | 7P3 = 7 × 6 × 5 = 210 |
| Combinaisons (l'ordre ne compte pas) | nCr = n! / [r!(n − r)!] | 7C3 = 210 / 3! = 35 |
Avec répétition ou sans répétition
Les deux formules ci-dessus supposent que chacun des n éléments ne peut être sélectionné qu'une seule fois — échantillonnage sans répétition. Lorsque les éléments peuvent être réutilisés (échantillonnage avec répétition, aussi appelé échantillonnage avec remise), les formules de comptage changent. Les permutations avec répétition autorisée élèvent simplement n à la puissance r, puisque chacune des r positions dispose indépendamment de tous les n choix, quel que soit ce qui a été choisi auparavant : n^r.
Les combinaisons avec répétition autorisée utilisent une formule différente, C(n + r − 1, r), qui compte le nombre de façons de choisir r éléments parmi n types lorsque les répétitions sont autorisées et que l'ordre ne compte toujours pas — c'est un cas moins fréquemment nécessaire, mais qui se présente par exemple lorsqu'on choisit des boules de glace parmi n parfums, la même saveur pouvant être choisie plus d'une fois.
| Cas | Formule | Exemple typique |
|---|---|---|
| Permutations, sans répétition | n! / (n − r)! | Classer 3 gagnants parmi 7 finalistes |
| Permutations, avec répétition | n^r | Un code PIN à 4 chiffres où les chiffres peuvent se répéter |
| Combinaisons, sans répétition | n! / [r!(n − r)!] | Choisir 6 numéros pour un billet de loterie |
| Combinaisons, avec répétition | (n + r − 1)! / [r!(n − 1)!] | Choisir 3 boules parmi 5 parfums de glace, répétitions autorisées |
Exemples résolus : un code PIN et un billet de loterie
Un code PIN à 4 chiffres, où chacune des 4 positions peut être n'importe quel chiffre de 0 à 9 et où les chiffres peuvent se répéter (la règle habituelle pour les codes PIN bancaires), est un exemple de permutation avec répétition : l'ordre compte (1234 et 4321 sont des codes différents) et la répétition est autorisée, ce qui donne 10^4 = 10 000 codes PIN possibles. Si les chiffres répétés n'étaient pas autorisés, le nombre tomberait à la valeur de permutation sans répétition, 10P4 = 10 × 9 × 8 × 7 = 5 040 — moins de possibilités, car chaque chiffre utilisé élimine une option pour les positions restantes.
Un format de loterie classique qui tire 6 numéros parmi un ensemble de 49, sans numéro répété et où l'ordre du tirage n'a aucune incidence sur le fait qu'un billet gagne, est un exemple de combinaison sans répétition : C(49, 6) = 49! / (6! × 43!) = 13 983 816. Ce chiffre élevé explique précisément pourquoi de tels formats de loterie sont décrits comme des jeux à très longues cotes — un calcul de combinaisons augmente très rapidement à mesure que n croît par rapport à r, puisqu'il compte des groupes non ordonnés parmi un vaste ensemble plutôt qu'un petit nombre fixe d'arrangements.
Un moyen mnémotechnique pour savoir quelle formule utiliser
« Permutation » et « position » commencent toutes deux par le son P, et un moyen mnémotechnique utile est que les permutations se soucient de la position — l'endroit où chaque élément se place dans la séquence. « Combinaison » décrit un groupe combiné, comme le contenu d'un sac ou d'un comité, où seule l'appartenance compte, pas l'ordre dans lequel les membres ont été ajoutés.
Les mots de passe, les codes PIN, les classements de course, et tout arrangement de sièges ou de planning sont des problèmes de permutation, car changer l'ordre change le résultat. Les mains de cartes, les ensembles de numéros de loterie, les compositions de comités, et toute sélection de groupe non ordonnée sont des problèmes de combinaison, car seuls les membres comptent, pas l'ordre dans lequel ils ont été choisis.
Questions fréquentes
Quelle est la différence entre une permutation et une combinaison ?
Une permutation compte les arrangements où l'ordre compte, de sorte que choisir les mêmes éléments dans un ordre différent compte comme un résultat différent. Une combinaison compte les sélections où l'ordre ne compte pas, de sorte que les mêmes éléments dans n'importe quel ordre comptent comme un seul résultat. Les deux partent du même groupe de n éléments et impliquent d'en choisir r, mais un calcul de permutation est toujours supérieur ou égal au calcul de combinaison correspondant pour les mêmes n et r.
Que vaut 7P3 et comment le calcule-t-on ?
7P3 vaut 210, le nombre de façons de choisir et d'arranger 3 éléments parmi un groupe de 7 éléments distincts où l'ordre compte. Il se calcule ainsi : 7P3 = 7! / (7 − 3)! = 7 × 6 × 5 = 210, en multipliant les trois plus grands facteurs de 7! puisque les facteurs plus petits s'annulent avec (7−3)! au dénominateur.
Que vaut 7C3 et comment le calcule-t-on ?
7C3 vaut 35, le nombre de façons de choisir 3 éléments parmi un groupe de 7 éléments distincts où l'ordre ne compte pas. Il se calcule ainsi : 7C3 = 7! / (3! × 4!) = (7 × 6 × 5) / (3 × 2 × 1) = 210 / 6 = 35 — exactement le nombre de permutations, 7P3 = 210, divisé par 3! (le nombre de façons de réordonner chaque groupe de 3), puisque les combinaisons regroupent tous les arrangements d'un même groupe en un seul résultat.
Pourquoi les codes PIN utilisent-ils des permutations et les loteries des combinaisons ?
Un code PIN traite 1234 et 4321 comme des codes différents, donc l'ordre des chiffres change le résultat, ce qui en fait un cas de permutation — avec répétition autorisée pour un code PIN typique à 4 chiffres, donnant 10^4 = 10 000 possibilités. Un billet de loterie gagne uniquement selon les numéros tirés, pas selon l'ordre de leur sortie, donc deux tirages avec les mêmes numéros dans un ordre différent constituent le même résultat gagnant, ce qui en fait un cas de combinaison — pour un format à 6 numéros parmi 49, C(49,6) = 13 983 816 ensembles de numéros possibles.
Que signifie « avec répétition » dans une formule de permutation ou de combinaison ?
Cela signifie qu'un élément peut être sélectionné plus d'une fois dans le même résultat. Les permutations avec répétition autorisée utilisent n^r (chacune des r positions dispose indépendamment de tous les n choix), tandis que les combinaisons avec répétition autorisée utilisent (n + r − 1)! / [r!(n − 1)!]. Sans répétition, chaque élément ne peut être utilisé qu'une seule fois, ce que supposent les formules standard nPr et nCr.
Références
- NIST Digital Library of Mathematical Functions (DLMF), §26 Combinatorial Analysis. dlmf.nist.gov.
- Rosen KH. Discrete Mathematics and Its Applications. 8th ed. McGraw-Hill, 2018 (permutations, combinations, and counting with repetition).
- Ross SM. A First Course in Probability. Pearson (combinatorial counting methods).
- Weisstein EW. "Permutation" and "Combination." MathWorld — A Wolfram Web Resource. mathworld.wolfram.com.