Combinatoire et dénombrement

Pour un entier $n \geqslant 1$, la factorielle de $n$, notée $n!$ (lu « factorielle $n$ »), est le produit de tous les entiers de $1$ à $n$ :

$n! = 1 \times 2 \times 3 \times \dots \times n$

Par convention, $0! = 1$.

Exemples.

$3! = 1 \times 2 \times 3 = 6 \qquad 5! = 1 \times 2 \times 3 \times 4 \times 5 = 120$

Une permutation de $n$ éléments distincts est une façon de les ranger dans un ordre. Le nombre de permutations de $n$ éléments est égal à :

$n!$

Pourquoi ? Il y a $n$ choix pour la première place, puis $n - 1$ pour la deuxième, puis $n - 2$ pour la troisième, et ainsi de suite jusqu’à $1$ : cela donne bien $n \times (n-1) \times \dots \times 1 = n!$.

Exemple. On peut classer $5$ coureurs de $5! = 120$ façons différentes.

Soit $n$ et $k$ deux entiers avec $0 \leqslant k \leqslant n$. Le coefficient binomial $\dbinom{n}{k}$ (lu « $k$ parmi $n$ ») est le nombre de façons de choisir $k$ éléments parmi $n$, sans tenir compte de l’ordre. Il se calcule par :

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

Exemple. Le nombre de façons de choisir $2$ éléments parmi $6$ est :

$\binom{6}{2} = \dfrac{6!}{2!\,(6-2)!} = \dfrac{6!}{2!\,4!} = \dfrac{720}{2 \times 24} = \dfrac{720}{48} = 15$