Parties d'un ensemble fini

I. Définition

Soit un ensemble $E$ fini dont la cardinalité est $n$, c’est-à-dire $\mathrm{card}(E) = n$.

On appelle partie (ou sous-ensemble) de $E$ tout ensemble $A$ tel que $A \subseteq E$.On cherche à déterminer le nombre total de parties de $E$. On note généralement l’ensemble de toutes les parties de $E$ par $\mathcal{P}(E)$.

La question est donc : Combien y a-t-il d’éléments dans $\mathcal{P}(E)$ ?

II. Nombre de parties d'un ensemble

Un exemple : Prenons un petit ensemble $E$ :

$\circ\quad$ Si $E = \varnothing$ (ensemble vide, $\mathrm{card}(E) = 0$), la seule partie de $E$ est $\varnothing$ elle-même. Donc $\mathrm{card}(\mathcal{P}(E)) = 1 = 2^0$.

$\circ\quad$Si $E = {a}$ (un seul élément, $\mathrm{card}(E) = 1$), les parties de $E$ sont $\varnothing$ et $\{a\}$.
Il y en a 2 au total, donc $\mathrm{card}(\mathcal{P}(E)) = 2 = 2^1$.

$\circ\quad$ Si $E = \{a, b\}$ (deux éléments, $\mathrm{card}(E) = 2$), les parties de $E$ sont :
$\varnothing\,, \{a\}\,, \{b\}\,, \{a\,, b\}.$
Il y en a 4, donc $\mathrm{card}(\mathcal{P}(E)) = 4 = 2^2$.

Conjecture : lorsque $E$ a $n$ éléments, le nombre de ses parties serait $2^n$. Voyons pourquoi.

Justification par le principe multiplicatif

a) Décomposition de la formation d’une partie

Pour construire une partie (sous-ensemble) de $E$ :

$\circ\quad$ Chaque élément de $E$ peut soit être inclus dans la partie,

$\circ\quad$ soit être exclu de la partie.Il y a donc 2 choix (inclure ou non) pour chaque élément.

b) Application du principe multiplicatif

Puisque le choix concernant chaque élément est indépendant du choix fait pour les autres éléments, on applique le principe multiplicatif :Nombre total de façons de choisir = produit du nombre de choix pour chaque élément.

$\circ\quad$ Pour chaque élément de $E$, on a 2 possibilités.

$\circ\quad$ Il y a $n$ éléments dans $E$. Donc, $\mathrm{card}(\mathcal{P}(E)) = \underbrace{2 \times 2 \times \cdots \times 2}_{n\text{fois}}= 2^n.$

Propriété : $\boxed{\begin{array}{l}\textbf{Pour un ensemble fini } E \textbf{ de cardinal }n,\\[6pt] \textbf{ le nombre de ses parties est } \mathrm{card}\bigl(\mathcal{P}(E)\bigr) = 2^n.\end{array}}$

Remarque :
On appelle mot de longueur $n$ sur l’alphabet $A = \{ a ; b \}$ un $n$-uplet d’éléments de $A$.

Par exemple, $(a ; b ; b ; a)$ est un mot de longueur $4$ sur l’alphabet $A$.

Il y a $2^n$ mots de longueur $n$.