Dénombrement en Terminale : permutations, combinaisons et méthodes

Commencer par identifier les objets

Avant toute formule, il faut répondre à quelques questions : l’ordre compte-t-il ? Peut-on répéter un élément ? Combien de positions faut-il remplir ? Les choix sont-ils indépendants ou existe-t-il des contraintes ?

Cette analyse distingue par exemple une liste ordonnée de $k$ éléments d’une partie contenant $k$ éléments. Les deux problèmes peuvent utiliser les mêmes données mais ne comptent pas les mêmes objets.

Principes additif et multiplicatif

Si plusieurs cas sont disjoints, on peut additionner leurs nombres de possibilités. Si une construction se fait en étapes successives avec un nombre connu de choix à chaque étape, on multiplie les nombres de choix.

Ces deux principes sont plus fondamentaux que les formules spécialisées. Ils permettent de reconstruire de nombreux dénombrements et de vérifier qu’un résultat est plausible.

$k$-uplets : quand l’ordre compte

Un $k$-uplet est une liste ordonnée de $k$ éléments. Deux listes qui contiennent les mêmes éléments dans un ordre différent sont donc considérées comme différentes.

Si chaque position peut être remplie par l’un des $n$ éléments d’un ensemble, avec répétition autorisée, le nombre de $k$-uplets est

$$n^k.$$

En effet, il y a $n$ choix pour la première position, puis encore $n$ pour la deuxième, et ainsi de suite jusqu’à la $k$-ième position.

Si les répétitions sont interdites, il reste successivement $n$, puis $n-1$, puis $n-2$ choix. Pour $k\leq n$, le nombre de listes ordonnées de longueur $k$ sans répétition est donc

$$n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}.$$

Exemple 1 — former un code

Un code comporte 4 chiffres, chacun choisi parmi les 10 chiffres de $0$ à $9$. Si les répétitions sont autorisées, il existe

$$10^4=10\,000$$

codes possibles. L’ordre compte : $1234$ et $4321$ sont deux codes différents.

Exemple 2 — attribuer trois rôles

Parmi 10 élèves, on choisit successivement un président, un secrétaire et un trésorier, sans qu’un même élève puisse occuper deux rôles. Il y a

$$10\times 9\times 8=720$$

attributions possibles. Ici encore, l’ordre des choix compte, puisque les trois rôles sont différents.

Permutations et combinaisons

Le nombre de permutations d’un ensemble à $n$ éléments est $n!$. Une permutation correspond au cas particulier où l’on ordonne tous les éléments : c’est donc un $n$-uplet sans répétition utilisant chacun des $n$ éléments exactement une fois.

Le nombre de parties à $k$ éléments parmi $n$ est le coefficient binomial

$$\binom nk=\frac{n!}{k!(n-k)!}.$$

Une combinaison ne tient pas compte de l’ordre. Choisir trois élèves parmi dix et désigner successivement un président, un secrétaire et un trésorier sont donc deux problèmes différents.

Choisir la bonne formule

On peut résumer les trois situations les plus fréquentes ainsi :

• l’ordre compte et les répétitions sont autorisées : pour une liste de longueur $k$ construite avec $n$ possibilités à chaque position, on obtient $n^k$ ;
• l’ordre compte et les répétitions sont interdites : on obtient $\frac{n!}{(n-k)!}$ ;
• l’ordre ne compte pas et l’on choisit $k$ éléments distincts parmi $n$ : on obtient $\binom nk$.

Le point essentiel est donc de ne pas choisir une formule à partir des seuls nombres présents dans l’énoncé. Il faut d’abord décider quels objets sont considérés comme différents.

Le triangle de Pascal

Les coefficients binomiaux vérifient la relation de Pascal

$$\binom nk=\binom{n-1}{k-1}+\binom{n-1}{k}.$$

Elle possède une interprétation combinatoire : pour compter les parties de taille $k$, on sépare celles qui contiennent un élément fixé et celles qui ne le contiennent pas.

Dénombrement et probabilités

Le dénombrement intervient naturellement dans les univers équiprobables et dans la loi binomiale. Mais compter les cas favorables sur les cas possibles n’est valable directement que lorsque les issues considérées sont équiprobables. La combinatoire fournit le nombre d’objets ; le modèle probabiliste détermine ensuite comment leur attribuer des probabilités.