Les principes du dénombrement en terminale

Compter sans dresser de liste : deux principes, puis les formules qui en découlent pour ranger et pour choisir.

Choisir entre le principe additif et le principe multiplicatif
Dénombrer les listes ordonnées avec répétition et les parties d'un ensemble
Dénombrer les permutations et les listes d'éléments distincts
Calculer un coefficient binomial et utiliser sa symétrie
Utiliser la relation de Pascal et le triangle de Pascal

Un menu propose trois entrées, quatre plats et deux desserts. Le restaurant annonce « plus de vingt menus » : il y en a exactement $24$.

$$ 3 \times 4 \times 2 = 24 $$

Personne n'a écrit la liste : les choix s'enchaînent, donc leurs nombres se multiplient.

Quand des choix s'enchaînent, leurs nombres se multiplient : c'est le principe multiplicatif.

Dénombrer, c'est compter sans énumérer. Deux principes suffisent, et toute la difficulté est de décider lequel s'applique - et si l'ordre compte.

Les deux principes

Principe additif

Si deux ensembles sont disjoints, le nombre d'éléments de leur réunion est la somme de leurs nombres d'éléments.

Principe multiplicatif

Si un choix se fait en $k$ étapes, avec $n_1$ possibilités à la première, $n_2$ à la deuxième, et ainsi de suite, alors le nombre total de choix est le produit :

$$ n_1 \times n_2 \times \ldots \times n_k $$

Le mot qui signale l'un ou l'autre : « ou » appelle une somme, à condition que les cas s'excluent, « et » appelle un produit. C'est le premier tri à faire en lisant l'énoncé.

Les $k$-uplets

$k$-uplet

Un $k$-uplet d'un ensemble à $n$ éléments est une liste ordonnée de $k$ éléments, les répétitions étant permises.

$$ \text{nombre de } k\text{-uplets} = n^k $$

Exemple :

Un code de quatre chiffres est un $4$-uplet de $\{0 \ ; \ 1 \ ; \ \ldots \ ; \ 9\}$ :

$$ 10^4 = 10 \ 000 \ \text{codes} $$

Le nombre de parties

Parties d'un ensemble

Un ensemble à $n$ éléments possède exactement :

$$ 2^n \ \text{parties} $$

Permutations

Ranger les $n$ éléments dans un ordre, c'est choisir le premier de $n$ façons, le deuxième de $n - 1$ façons, et ainsi de suite : le principe multiplicatif donne une factorielle.

$$ n \, ! = n \times (n-1) \times \ldots \times 2 \times 1 \hspace{2em} \text{avec} \ 0 \, ! = 1 $$

Plus généralement, une liste ordonnée de $k$ éléments distincts choisis parmi $n$ s'obtient de :

$$ n \times (n-1) \times \ldots \times (n - k + 1) = \frac{n \, !}{(n-k) \, !} \ \text{façons} $$

Combinaisons

Coefficient binomial

$\binom{n}{k}$ est le nombre de parties à $k$ éléments d'un ensemble à $n$ éléments - autrement dit le nombre de choix de $k$ objets sans tenir compte de l'ordre.

$$ \binom{n}{k} = \frac{n \times (n-1) \times \ldots \times (n-k+1)}{k \, !} = \frac{n \, !}{(n-k) \, ! \ k \, !} $$

Le dénominateur $k \, !$ est exactement le nombre d'ordres possibles des $k$ objets choisis : on divise pour effacer l'ordre.

Trois valeurs se lisent directement, et une symétrie évite la moitié des calculs :

$$ \binom{n}{0} = 1 \hspace{2em} \binom{n}{1} = n \hspace{2em} \binom{n}{2} = \frac{n(n-1)}{2} $$

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

La symétrie se comprend sans calcul : choisir $k$ objets à prendre, c'est choisir les $n - k$ qu'on laisse.

La relation de Pascal

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

C'est cette relation qui construit le triangle de Pascal, où chaque nombre est la somme des deux qui le surplombent.

Avec ordre, ou sans

La situation	Ordre	Répétition	Nombre
un code, un mot	oui	oui	$n^k$
un podium, un tirage sans remise ordonné	oui	non	$\frac{n \, !}{(n-k) \, !}$
un comité, une main de cartes	non	non	$\dbinom{n}{k}$
un rangement de tous les objets	oui	non	$n \, !$

deux questions suffisent à trancher : l'ordre compte-t-il, un objet peut-il se répéter

Le test qui décide en une seconde : échanger deux objets change-t-il le résultat ? Si oui, l'ordre compte. Un podium change, un comité non.

Les principes du dénombrement