Combinatoire & dénombrement

Compter sans énumérer : permutations, arrangements, combinaisons et coefficients binomiaux.

1 L'idée

Le dénombrement consiste à compter le nombre de façons de réaliser un choix, sans tout énumérer. La question décisive : l'ordre compte-t-il ? Y a-t-il répétition ?

Principe multiplicatif : si un choix se fait en plusieurs étapes indépendantes offrant $n_1, n_2,\dots, n_p$ possibilités, le nombre total de résultats est $n_1\times n_2\times\cdots\times n_p$.

2 Les trois outils

Permutations (tout ranger)

$n! = n\times(n-1)\times\cdots\times 2\times 1$

k-listes / arrangements (ordre, sans répétition)

$\dfrac{n!}{(n-k)!}$

Combinaisons (k parmi n, sans ordre)

$\binom{n}{k}=\dfrac{n!}{k!\,(n-k)!}$

On lit $\binom{n}{k}$ « $k$ parmi $n$ » : c'est le nombre de parties à $k$ éléments d'un ensemble à $n$ éléments (l'ordre ne compte pas). Convention : $0!=1$, donc $\binom{n}{0}=\binom{n}{n}=1$.

3 Coefficients binomiaux

Symétrie

$\binom{n}{k}=\binom{n}{n-k}$

Relation de Pascal

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

Lien loi binomiale

$P(X=k)=\binom{n}{k}p^k(1-p)^{n-k}$

Un comité de 3 personnes choisi parmi 10

L'ordre des membres ne compte pas, et pas de répétition : c'est une combinaison.

Nombre de comités $=\binom{10}{3}=\dfrac{10!}{3!\,7!}=\dfrac{10\times9\times8}{3\times2\times1}=120$.

Méthode — Choisir le bon outil

L'ordre compte et pas de répétition → arrangement $\frac{n!}{(n-k)!}$ (ex. podium, mots sans lettre répétée).
L'ordre ne compte pas → combinaison $\binom{n}{k}$ (ex. comité, main de cartes, tirage simultané).
On utilise tous les éléments en les rangeant → permutation $n!$ (ex. anagrammes de lettres distinctes).
Étapes successives indépendantes → on multiplie les possibilités.

Erreurs fréquentes

Confondre arrangement (ordre) et combinaison (sans ordre) : « tirage successif » vs « tirage simultané ».
Oublier $\binom{n}{0}=1$ et $\binom{n}{1}=n$.
Sur la calculatrice, $\binom{n}{k}$ se note souvent $\text{nCr}$ (et l'arrangement $\text{nPr}$).