Baccalauréat Mathématiques

Ensembles finis et listes

Un ensemble est fini lorsqu'il a un nombre fini d'éléments, et ce nombre est son cardinal, noté $\mathrm{Card}(A)$ ou $|A|$. Pour $A=\{a\,;b\,;c\}$, on a $\mathrm{Card}(A)=3$. L'ensemble vide $\varnothing$ a pour cardinal $0$.

Un couple est une liste ordonnée de deux éléments, un triplet une liste ordonnée de trois éléments, et plus généralement un $k$-uplet (ou $k$-liste) est une liste ordonnée de $k$ éléments, écrite $(x_1\,;x_2\,;\dots\,;x_k)$. L'ordre compte et les répétitions sont permises : $(1\,;2)$ et $(2\,;1)$ sont deux couples différents, et $(1\,;1)$ est un couple.

Le produit cartésien de deux ensembles $A$ et $B$ est l'ensemble des couples dont le premier élément est dans $A$ et le second dans $B$ :

Le produit de trois ensembles, $A\times B\times C$, est l'ensemble des triplets, et ainsi de suite. Lorsque tous les facteurs sont le même ensemble $A$, on note $A^k=A\times\dots\times A$ l'ensemble des $k$-uplets d'éléments de $A$. Par exemple, $\{0\,;1\}^3$ contient les huit triplets $(0\,;0\,;0)$, $(0\,;0\,;1)$, jusqu'à $(1\,;1\,;1)$.

Ces notions valent pour des ensembles quelconques, mais les dénombrements ne portent ici que sur des ensembles finis.

Principe additif

Si $A_1,\dots,A_m$ sont des ensembles finis deux à deux disjoints (aucun élément n'appartient à deux d'entre eux), le cardinal de leur réunion est la somme des cardinaux :

La condition de disjonction est nécessaire. Si elle n'est pas vérifiée, on retire ce qui a été compté deux fois : pour deux ensembles quelconques, $\mathrm{Card}(A\cup B)=\mathrm{Card}(A)+\mathrm{Card}(B)-\mathrm{Card}(A\cap B)$.

Exemple : une classe compte 14 élèves qui étudient l'espagnol seulement, 9 qui étudient l'allemand seulement et 5 qui étudient les deux. Les trois groupes sont deux à deux disjoints, donc la classe compte $14+9+5=28$ élèves, dont $14+5=19$ qui étudient l'espagnol.

En pratique, le principe additif sert à découper un problème en cas qui ne se recoupent pas, à compter chaque cas puis à additionner.

Principe multiplicatif

Le cardinal d'un produit cartésien d'ensembles finis est le produit des cardinaux :

Cela se voit avec un arbre : pour construire un $k$-uplet, on choisit successivement sa première composante ($n_1$ possibilités), puis la deuxième ($n_2$ possibilités quel que soit le premier choix), et ainsi de suite, de sorte que le nombre de chemins de l'arbre est $n_1\times n_2\times\dots\times n_k$. La condition essentielle est que le nombre de choix à chaque étape ne dépende pas des choix précédents.

Exemple : un menu se compose d'une entrée parmi 4, d'un plat parmi 3 et d'un dessert parmi 5. Il y a $4\times3\times5=60$ menus possibles.

Nombre de $k$-uplets

Un ensemble à $n$ éléments a exactement $n^k$ $k$-uplets, puisque $A^k$ est un produit de $k$ ensembles de cardinal $n$ :

Exemple : un code de carte comporte 4 chiffres, chacun pris parmi les dix chiffres $0,\dots,9$, avec répétition possible. Il y a $10^4=10\,000$ codes. Si l'on impose que le premier chiffre soit non nul, le principe multiplicatif donne $9\times10^3=9\,000$ codes.

Parties d'un ensemble

Une partie (ou sous-ensemble) de $E$ est un ensemble $A$ tel que tout élément de $A$ est dans $E$, ce que l'on écrit $A\subset E$. L'ensemble vide et $E$ lui-même sont des parties de $E$.

Un ensemble à $n$ éléments possède exactement $2^n$ parties.

Démonstration par dénombrement. Numérotons les éléments de $E=\{e_1\,;\dots\,;e_n\}$. À une partie $A$ de $E$, on associe le $n$-uplet $(x_1\,;\dots\,;x_n)$ de $\{0\,;1\}^n$ défini par $x_i=1$ si $e_i\in A$ et $x_i=0$ sinon. Cette association est une bijection : deux parties différentes donnent deux $n$-uplets différents, et tout $n$-uplet de $0$ et de $1$ provient d'une et une seule partie (celle formée des $e_i$ dont la composante vaut $1$). Il y a donc autant de parties de $E$ que de $n$-uplets de $\{0\,;1\}^n$, soit $2^n$.

Pour $E=\{a\,;b\,;c\}$, les $2^3=8$ parties sont $\varnothing$, $\{a\}$, $\{b\}$, $\{c\}$, $\{a\,;b\}$, $\{a\,;c\}$, $\{b\,;c\}$ et $E$.

Une même quantité sous plusieurs formes

Le nombre $2^n$ apparaît sous plusieurs visages, qui sont les mêmes objets représentés différemment :

• les $n$-uplets de $\{0\,;1\}$ ;
• les mots de longueur $n$ écrits avec un alphabet de deux lettres, par exemple $\{P\,;F\}$ ;
• les chemins d'un arbre à $n$ niveaux dont chaque nœud a deux branches ;
• les issues d'une succession de $n$ épreuves de Bernoulli, chaque épreuve ayant deux issues (succès ou échec).

Ainsi, lancer une pièce 6 fois donne $2^6=64$ suites de résultats possibles, et un ensemble de 6 éléments a 64 parties.

Listes d'éléments distincts

On cherche maintenant le nombre de $k$-uplets dont les éléments sont deux à deux distincts, dans un ensemble à $n$ éléments (avec $k\leqslant n$). On choisit la première composante parmi $n$ éléments, la deuxième parmi les $n-1$ restants, la troisième parmi $n-2$, et ainsi de suite jusqu'à la $k$-ième, parmi $n-k+1$ éléments. Le principe multiplicatif donne

Exemple : dans une course de 8 coureurs, le nombre de podiums possibles (premier, deuxième, troisième, sans ex aequo) est $8\times7\times6=336$.

Exemple : le nombre de mots de 3 lettres toutes différentes écrits avec les 26 lettres de l'alphabet est $26\times25\times24=15\,600$.

Factorielle et permutations

Pour un entier $n\geqslant1$, la factorielle de $n$ est le produit des entiers de $1$ à $n$ :

et l'on convient que $0!=1$. On a donc $1!=1$, $2!=2$, $3!=6$, $4!=24$, $5!=120$, $6!=720$ et la relation $n!=n\times(n-1)!$ pour $n\geqslant1$.

Une permutation d'un ensemble fini à $n$ éléments est une liste de ces $n$ éléments, chacun apparaissant une fois : c'est une façon de les ranger dans un ordre. C'est le cas particulier $k=n$ de la section précédente.

Un ensemble à $n$ éléments possède $n!$ permutations.

Exemple : cinq personnes peuvent s'asseoir sur cinq chaises alignées de $5!=120$ façons.

Les listes d'éléments distincts s'écrivent avec la factorielle. Pour $0\leqslant k\leqslant n$, le nombre de $k$-uplets d'éléments distincts d'un ensemble à $n$ éléments est

Pour le vérifier, on multiplie et on divise par $(n-k)!=(n-k)(n-k-1)\cdots1$ : le numérateur devient le produit de tous les entiers de $n$ à $1$.

Choisir la bonne représentation

Face à un problème de dénombrement, il faut d'abord reconnaître ce que l'on compte. Quatre questions aident à choisir.

1. L'ordre des éléments compte-t-il ? Si oui, on compte des listes ; sinon, on compte des parties (les combinaisons).
2. Les répétitions sont-elles permises ? Oui : $n^k$. Non : $\dfrac{n!}{(n-k)!}$.
3. Le problème se découpe-t-il en cas disjoints ? On additionne alors les dénombrements de chaque cas.
4. Le problème se construit-il par choix successifs, dont le nombre ne dépend pas des choix précédents ? On multiplie.

Exemple : on forme un mot de 4 lettres avec les lettres A, B, C, D, E, avec répétition possible, qui ne commence pas par A. Il y a $4\times5^3=500$ mots. Sans répétition, il y a $4\times4\times3\times2=96$ mots : quatre choix pour la première lettre (B, C, D ou E), puis quatre pour la deuxième (les quatre lettres restantes, A compris), puis trois, puis deux.

Un tableau à double entrée, un arbre ou un diagramme aide à visualiser les cas. Dans un arbre, chaque niveau correspond à un choix, et le nombre de chemins complets est le nombre d'objets cherchés.