Sciences · Mathématiques
Combinaisons, arrangements et permutations
Pour compter des tirages, on se demande si l’ordre compte et si les répétitions sont possibles. Sans répétition, l’ordre compté donne un arrangement, l’ordre ignoré une combinaison.
Mis à jour le 4 min de lecture
Combien de codes à 4 chiffres ? Combien de façons de choisir 3 délégués dans une classe de 30 ? Combien de grilles possibles au Loto ? La combinatoire, ou dénombrement, répond à ces questions sans avoir à tout énumérer. Elle est indispensable pour calculer des probabilités avec la formule « cas favorables sur cas possibles », et elle intervient en informatique, en génétique et en cryptographie.
Le principe multiplicatif
Toutes les formules qui suivent découlent de ce principe.
Quelle formule choisir ?
| L’ordre compte | L’ordre ne compte pas | |
|---|---|---|
| Sans répétition | Arrangement : n! / (n − k)! | Combinaison : n! / (k! × (n − k)!) |
| Avec répétition | k-uplet (ou liste) : n^k | Combinaison avec répétition : C(n + k − 1, k) |
Deux questions suffisent : l’ordre importe-t-il ? (un podium : oui ; une main de cartes : non) et peut-on reprendre le même élément ? (un code : oui ; des personnes : non).
Les permutations
Une permutation de n éléments est une façon de les ranger dans un ordre. Il y en a :
n! = n × (n − 1) × … × 2 × 1 (lire « factorielle n »)
Par convention, 0! = 1. La factorielle croît extrêmement vite ; voir la fiche factorielle.
Les listes avec répétition
On choisit k éléments parmi n, dans l’ordre, avec répétition possible : n^k possibilités.
Les arrangements
On choisit k éléments distincts parmi n, dans l’ordre :
A(n, k) = n × (n − 1) × … × (n − k + 1) = n! / (n − k)!
Les combinaisons
On choisit k éléments distincts parmi n, sans tenir compte de l’ordre :
C(n, k) = n! / (k! × (n − k)!)
On lit « k parmi n ». Chaque combinaison correspond à k! arrangements (les k éléments peuvent être ordonnés de k! façons), d’où la division.
Propriétés des combinaisons
C(n, 0) = C(n, n) = 1etC(n, 1) = n.- Symétrie :
C(n, k) = C(n, n − k). Choisir les 3 qui partent revient à choisir les 17 qui restent. - Relation de Pascal :
C(n, k) = C(n − 1, k − 1) + C(n − 1, k), qui permet de construire le triangle de Pascal. - Somme :
C(n, 0) + C(n, 1) + … + C(n, n) = 2^n, le nombre total de sous-ensembles d’un ensemble à n éléments. - Binôme de Newton :
(a + b)^n = somme des C(n, k) × a^k × b^(n − k). D’où le nom de coefficients binomiaux, que l’on retrouve dans la loi binomiale.
Les combinaisons avec répétition
On choisit k éléments parmi n types, sans ordre, avec répétition : C(n + k − 1, k).
Erreurs fréquentes
- Utiliser un arrangement quand l’ordre ne compte pas : on compte alors chaque groupe plusieurs fois.
- Oublier les répétitions possibles (un code peut contenir deux fois le même chiffre).
- Additionner au lieu de multiplier : on multiplie pour des étapes successives (« et »), on additionne pour des cas qui s’excluent (« ou »).
Questions fréquentes
Quelle est la différence entre arrangement et combinaison ?
Dans un arrangement, l’ordre compte (un podium, un code) ; dans une combinaison, non (une équipe, une main de cartes). Il y a k! fois plus d’arrangements que de combinaisons.
Comment calculer « k parmi n » ?
n! / (k! × (n − k)!). Plus pratique : multiplier les k nombres décroissants à partir de n, puis diviser par k!. Par exemple, C(10, 3) = 10 × 9 × 8 / 6 = 120.
Combien y a-t-il de mains de 5 cartes dans un jeu de 52 ?
C(52, 5) = 2 598 960.
Pourquoi 0! vaut-il 1 ?
Parce qu’il y a une seule façon de ranger zéro objet (ne rien faire), et parce que cette convention rend les formules valables pour k = 0 ou k = n.