Combinatoire et dénombrement

Ensembles finis et k-uplets

On travaille avec des ensembles finis, c'est-à-dire des ensembles qui possèdent un nombre fini d'éléments. Si $E$ possède $n$ éléments, ce nombre $n$ est appelé le cardinal de $E$, noté $\mathrm{Card}(E)$.

Deux ensembles $A$ et $B$ sont disjoints lorsqu'ils n'ont aucun élément en commun (leur intersection est vide) : $A \cap B = \varnothing$.

On appelle $k$-uplet (ou $k$-liste) d'un ensemble $E$ une collection ordonnée de $k$ éléments de $E$, notée avec des parenthèses $(x_1\,; x_2\,; \ldots\,; x_k)$. Un 2-uplet s'appelle un couple, un 3-uplet un triplet.

Attention. Dans un $k$-uplet, l'ordre compte ($(a\,;b) \neq (b\,;a)$ dès que $a \neq b$) et les éléments peuvent être répétés (le couple $(a\,;a)$ existe).

Le produit cartésien de deux ensembles $E$ et $F$, noté $E \times F$, est l'ensemble des couples $(x\,;y)$ avec $x \in E$ et $y \in F$. Plus généralement, pour $k$ ensembles $E_1, E_2, \ldots, E_k$, on note $E_1 \times E_2 \times \cdots \times E_k$ l'ensemble des $k$-uplets $(x_1\,;x_2\,;\ldots\,;x_k)$ avec $x_i \in E_i$ pour tout $i$. Lorsque $E_1 = E_2 = \cdots = E_k = E$, on note ce produit $E^k$ : c'est l'ensemble des $k$-uplets d'éléments de $E$.

Principe additif

Le principe additif sert à dénombrer une réunion d'ensembles deux à deux disjoints : on additionne simplement les cardinaux.

Soit $n \geqslant 2$ un entier et $A_1, A_2, \ldots, A_n$ des ensembles finis deux à deux disjoints. Alors : $\mathrm{Card}(A_1 \cup A_2 \cup \cdots \cup A_n) = \mathrm{Card}(A_1) + \mathrm{Card}(A_2) + \cdots + \mathrm{Card}(A_n)$

Exemple. Dans une classe, 14 élèves pratiquent uniquement un sport collectif et 9 élèves pratiquent uniquement un sport individuel (aucun élève ne pratique les deux). Le nombre d'élèves sportifs de la classe est $14 + 9 = 23$.

Principe multiplicatif

Le principe multiplicatif sert à dénombrer un produit cartésien, c'est-à-dire une succession de choix indépendants.

Soit $E$ et $F$ deux ensembles finis non vides. Alors $\mathrm{Card}(E \times F) = \mathrm{Card}(E) \times \mathrm{Card}(F)$.

Plus généralement, pour $k \geqslant 2$ ensembles finis non vides $E_1, \ldots, E_k$ : $\mathrm{Card}(E_1 \times E_2 \times \cdots \times E_k) = \mathrm{Card}(E_1) \times \mathrm{Card}(E_2) \times \cdots \times \mathrm{Card}(E_k)$

En particulier, si $E$ est un ensemble fini à $n$ éléments, le nombre de $k$-uplets de $E$ (c'est-à-dire $\mathrm{Card}(E^k)$) vaut : $n^k$

Exemple. Une plaque d'immatriculation « à l'ancienne » comporte 4 chiffres suivis de 2 lettres (parmi les 26 lettres de l'alphabet), chaque caractère pouvant être répété. Le nombre de plaques possibles est $10^4 \times 26^2 = 10\,000 \times 676 = 6\,760\,000$ (principe multiplicatif appliqué à 6 choix indépendants).

Nombre de parties d'un ensemble à $n$ éléments

Soit $E$ un ensemble fini à $n$ éléments. Pour décrire une partie $F$ de $E$, on peut examiner chaque élément de $E$ l'un après l'autre et décider, pour chacun, s'il appartient à $F$ (on lui associe alors $1$) ou non (on lui associe $0$). Choisir une partie de $E$ revient donc exactement à choisir un $n$-uplet de $\{0\,;1\}$.

Le nombre de parties d'un ensemble à $n$ éléments est égal au nombre de $n$-uplets de $\{0\,;1\}$, c'est-à-dire : $2^n$

Cette même situation se retrouve dans plusieurs contextes équivalents :

• les mots de longueur $n$ que l'on peut écrire avec un alphabet de deux lettres (par exemple $\{0\,;1\}$ en informatique) ;
• les chemins dans un arbre où chaque étape propose exactement deux branches ;
• les issues d'une succession de $n$ épreuves de Bernoulli (chaque épreuve n'ayant que deux issues possibles, par exemple succès/échec ou pile/face).

Exemple. Un octet informatique est une suite de 8 bits, chaque bit valant 0 ou 1. Il y a $2^8 = 256$ octets différents — ce qui correspond aussi au nombre de parties d'un ensemble à 8 éléments, ou au nombre de résultats possibles pour 8 lancers de pièce successifs.

Factorielle

Soit $n$ un entier naturel non nul. On appelle factorielle $n$ (notée $n!$) le nombre : $n! = n \times (n-1) \times (n-2) \times \cdots \times 3 \times 2 \times 1$ Par convention, $0! = 1$. On a aussi la relation $(n+1)! = (n+1) \times n!$.

Exemple. $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$.

$k$-uplets d'éléments distincts d'un ensemble à $n$ éléments

Contrairement à un $k$-uplet quelconque (où un élément peut être répété), un $k$-uplet d'éléments distincts de $E$ n'utilise jamais deux fois le même élément de $E$.

Soit $E$ un ensemble fini à $n$ éléments et $k$ un entier tel que $1 \leqslant k \leqslant n$. Le nombre de $k$-uplets d'éléments distincts de $E$ est : $n \times (n-1) \times \cdots \times (n-k+1) = \frac{n!}{(n-k)!}$

Ce résultat s'obtient par principe multiplicatif « en cascade » : $n$ choix possibles pour le premier élément, puis $n-1$ choix restants pour le deuxième (il doit être différent du premier), puis $n-2$ pour le troisième, etc.

Exemple. Sur un podium de 3 places, on veut classer 3 des 8 finalistes d'une course. Le nombre de podiums possibles est $8 \times 7 \times 6 = 336$.

Permutations d'un ensemble

Lorsque $k = n$, un $n$-uplet d'éléments deux à deux distincts d'un ensemble à $n$ éléments s'appelle une permutation de cet ensemble : c'est un rangement de tous les éléments de $E$, dans un ordre donné.

Le nombre de permutations d'un ensemble fini non vide à $n$ éléments est $n!$.

Exemple. Il y a $5! = 120$ façons de ranger 5 livres différents côte à côte sur une étagère.

Combinaisons de $k$ éléments d'un ensemble à $n$ éléments

Une partie de $E$ ayant $k$ éléments est appelée une combinaison de $k$ éléments de $E$. Contrairement à un $k$-uplet, l'ordre n'intervient pas : $\{a\,;b\}$ et $\{b\,;a\}$ désignent la même combinaison.

Soit $n$ et $k$ deux entiers naturels tels que $0 \leqslant k \leqslant n$, et $E$ un ensemble fini à $n$ éléments. Le nombre de combinaisons de $k$ éléments de $E$ (appelé coefficient binomial) est noté $\dbinom{n}{k}$ et vaut : $\binom{n}{k} = \frac{n!}{k!\,(n-k)!}$

Cas particuliers.

• $\dbinom{n}{0} = 1$ : il n'existe qu'une seule partie à 0 élément, la partie vide.
• $\dbinom{n}{1} = n$ : il existe $n$ parties à un seul élément.
• $\dbinom{n}{2} = \dfrac{n(n-1)}{2}$ : c'est le nombre de paires que l'on peut former parmi $n$ éléments.

Symétrie. Pour tous entiers $n$ et $k$ avec $0 \leqslant k \leqslant n$ : $\binom{n}{k} = \binom{n}{n-k}$ (choisir les $k$ éléments qui appartiennent à la partie revient à choisir les $n-k$ éléments qui n'y appartiennent pas).

Relation et triangle de Pascal. Pour tous entiers $n \geqslant 2$ et $k$ avec $1 \leqslant k \leqslant n-1$ : $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$

Cette relation permet de construire, ligne après ligne, le triangle de Pascal :

Chaque coefficient (hors bords) s'obtient en additionnant les deux coefficients situés juste au-dessus de lui. Par exemple $\dbinom{5}{2} = \dbinom{4}{1} + \dbinom{4}{2} = 4 + 6 = 10$.

Remarque. Sommer tous les coefficients binomiaux d'une ligne redonne le nombre de parties d'un ensemble à $n$ éléments vu dans la notion précédente : $\sum_{k=0}^{n} \binom{n}{k} = 2^n$

Exemple. Une classe de 30 élèves doit élire un binôme de délégués (2 élèves, sans distinction de rôle). Le nombre de binômes possibles est $\dbinom{30}{2} = \dfrac{30 \times 29}{2} = 435$.