Permutations et combinaisons expliquées

Le principe multiplicatif

Les problèmes de dénombrement demandent de combien de façons quelque chose peut se produire. La base est le principe multiplicatif : si un choix peut se faire de $m$ façons et un second choix, indépendant, de $n$ façons, les deux ensemble peuvent se faire de $m \times n$ façons. L’idée s’étend à n’importe quel nombre d’étapes.

Avec 3 chemises, 4 pantalons et 2 paires de chaussures, vous pouvez composer $3 \times 4 \times 2 = 24$ tenues différentes. Un code PIN à quatre chiffres utilisant les chiffres de 0 à 9, répétitions permises, offre $10 \times 10 \times 10 \times 10 = 10^4 = 10{,}000$ possibilités. Toutes les formules de cet article sont des raccourcis de cette multiplication : quand un problème vous paraît étrange, revenir à un dénombrement étape par étape est toujours une valeur sûre.

Les factorielles

Pour aligner $n$ objets distincts, il y a $n$ choix pour la première place, $n - 1$ pour la deuxième, et ainsi de suite jusqu’à 1. Ce produit s’appelle la factorielle de $n$ :

Ainsi, $5! = 120$ : cinq livres peuvent être rangés sur une étagère de 120 façons différentes. Par définition, $0! = 1$, ce qui garde les formules suivantes cohérentes, puisqu’il y a exactement une façon de ranger « rien ». Les factorielles croissent à une vitesse stupéfiante : $10! = 3{,}628{,}800$, et un jeu de cartes mélangé a $52!$ ordres possibles, un nombre de 68 chiffres.

Permutations et arrangements : l’ordre compte

Un arrangement, que l’on appelle aussi permutation partielle, est une liste ordonnée de $r$ objets choisis parmi $n$ objets distincts. Comme l’ordre compte, premier-deuxième-troisième diffère de troisième-deuxième-premier. Le nombre d’arrangements est

Placer des personnes autour d’une table ronde est un cas particulier. Décaler tout le monde d’un siège donne la même disposition, donc $n$ personnes peuvent s’asseoir de $(n-1)!$ façons différentes. Six personnes autour d’une table ronde ont $5! = 120$ dispositions, et non 720.

Combinaisons : l’ordre ne compte pas

Une combinaison est un choix où seule compte l’identité des éléments retenus. Choisir Anne, Ben et Clara pour un comité donne le même comité, quel que soit l’ordre. Chaque groupe de $r$ objets correspond à $r!$ arrangements, on divise donc par ce nombre :

Les combinaisons sont symétriques : $\binom{n}{r} = \binom{n}{n-r}$, car choisir les 3 personnes retenues revient à choisir les 5 qui restent de côté. Ce sont aussi les nombres du triangle de Pascal et les coefficients du développement du binôme $(a + b)^n$.

Comment savoir laquelle utiliser

Posez-vous une seule question : si j’échange deux des éléments choisis, est-ce que j’obtiens un résultat différent ? Si oui, l’ordre compte et il faut des arrangements. Sinon, utilisez des combinaisons.

• Places, classements, mots de passe, plans de table et emplois du temps : arrangements.
• Équipes, comités, mains de cartes, grilles de loto et garnitures de pizza : combinaisons.
• Des fonctions au sein d’un groupe, comme président et trésorier, font compter l’ordre même si les personnes viennent d’un même groupe.

Une vérification rapide : le nombre d’arrangements vaut toujours $r!$ fois le nombre de combinaisons. Si vos deux résultats ne respectent pas cette relation, l’un d’eux est faux.

Dénombrer avec répétition et lettres répétées

Quand les éléments peuvent se répéter, les formules changent. Les choix ordonnés avec répétition sont au nombre de $n^r$, comme dans l’exemple du code PIN. Les choix non ordonnés avec répétition, comme prendre 3 boules de glace parmi 5 parfums en pouvant répéter un parfum, sont au nombre de

Ranger des lettres comportant des répétitions demande un ajustement de plus : diviser par la factorielle de chaque nombre de répétitions, car échanger des lettres identiques ne change rien. Le mot MISSISSIPPI compte 11 lettres, dont 4 lettres I, 4 lettres S et 2 lettres P : il a donc $\frac{11!}{4!\,4!\,2!} = 34{,}650$ anagrammes distinctes.

Dénombrer pour calculer des probabilités

Quand les issues sont équiprobables, une probabilité est le nombre de cas favorables divisé par le nombre de cas possibles : les arrangements et les combinaisons font donc l’essentiel du travail. Les bases de ce quotient sont expliquées dans les bases des probabilités.

Les jeux de cartes offrent d’autres exercices. Il y a $\binom{52}{5} = 2{,}598{,}960$ mains possibles de cinq cartes. Une main contenant les quatre as n’a besoin que d’une carte de plus, choisie parmi les 48 autres, donc la probabilité vaut $\frac{48}{2{,}598{,}960} = \frac{1}{54{,}145}$.

Erreurs fréquentes

• Utiliser des arrangements pour une équipe ou un comité, ce qui surcompte d’un facteur $r!$.
• Oublier que $0! = 1$, ce qui fausse des formules comme $\binom{n}{n}$.
• Ne pas tenir compte des éléments identiques, comme dans les anagrammes avec lettres répétées.
• Multiplier des étapes qui ne sont pas indépendantes sans ajuster les dénombrements suivants.

La calculatrice de permutations et combinaisons évalue ${}_nP_r$ et ${}_nC_r$ en détaillant les étapes avec les factorielles, et la calculatrice de probabilités transforme ces dénombrements en probabilités.

Le triangle de Pascal et les sous-ensembles

Chaque nombre du triangle de Pascal est la somme des deux nombres situés au-dessus, et la ligne $n$ contient les valeurs $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$. La ligne 4 est 1, 4, 6, 4, 1, exactement les coefficients de $(a + b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4$. La règle qui construit le triangle, la formule de Pascal, est elle-même un résultat de dénombrement :

Pour comprendre pourquoi, fixez un élément particulier. Tout choix de $r$ éléments soit le contient, et il reste $r - 1$ éléments à choisir parmi les $n - 1$ autres, soit l’exclut, et il reste les $r$ éléments à choisir parmi les $n - 1$ autres. La somme d’une ligne entière vaut $2^n$, le nombre total de sous-ensembles d’un ensemble à $n$ éléments, puisque chaque élément est dedans ou dehors. Une pizzeria proposant 8 garnitures peut donc préparer $2^8 = 256$ pizzas différentes, en comptant celle sans aucune garniture.

Exercices

1. De combien de façons peut-on ranger sur une étagère 4 livres choisis parmi 7 livres différents ? Solution : ${}_7P_4 = 7 \times 6 \times 5 \times 4 = 840$.
2. De combien de façons peut-on choisir 4 garnitures parmi 10 ? Solution : $\binom{10}{4} = 210$.
3. Combien le mot BANANA a-t-il d’anagrammes distinctes ? Solution : $\frac{6!}{3!\,2!} = 60$.
4. Combien de codes de cinq lettres peut-on former avec 26 lettres si les répétitions sont permises ? Solution : $26^5 = 11{,}881{,}376$.

Questions fréquentes