Les principes du dénombrement en terminale

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} $$

Pourquoi $2^n$

Choisir une partie de $E$, c'est décider, pour chacun des $n$ éléments, s'il en fait partie ou non.

À chaque partie correspond ainsi un $n$-uplet de $\{0 \ ; \ 1\}$, et à chaque $n$-uplet une partie : la correspondance est parfaite.

Or les $n$-uplets d'un ensemble à deux éléments sont au nombre de :

$$ 2^n $$

L'ensemble vide et $E$ lui-même sont comptés : ils correspondent aux uplets composés uniquement de zéros, et uniquement de uns.

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 \qquad \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 \qquad \binom{n}{1} = n \qquad \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} $$

Une démonstration sans calcul

Comptons les parties à $k+1$ éléments d'un ensemble à $n+1$ éléments, et fixons l'un de ces éléments, appelé $a$. Chaque partie est de l'un des deux types, et d'un seul.

celles qui contiennent $a$ : il reste à choisir $k$ éléments parmi les $n$ autres, soit $\binom{n}{k}$ façons
celles qui ne le contiennent pas : il faut choisir les $k+1$ éléments parmi les $n$ autres, soit $\binom{n}{k+1}$ façons

Les deux cas étant disjoints, le principe additif donne :

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

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

La somme d'une ligne du triangle vaut $2^n$

Comptons les parties d'un ensemble à $n$ éléments de deux façons.

D'un côté, il y en a $2^n$, comme on vient de le voir.

De l'autre, rangeons-les selon leur nombre d'éléments : il y en a $\binom{n}{0}$ qui n'en ont aucun, $\binom{n}{1}$ qui en ont un, et ainsi de suite jusqu'à $\binom{n}{n}$.

Ces cas sont disjoints et couvrent tout : leur somme est le total.

$$ \sum_{k=0}^{n} \binom{n}{k} = 2^n $$

Compter le même ensemble de deux façons est le procédé le plus économique du chapitre : il donne une égalité sans le moindre calcul.

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	$\dfrac{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