Nombre des parties d’un ensemble à $n$ éléments. Démonstrations (2024)

1. Nombre des parties d’un ensemble à $n$ éléments. Démonstrations

Propriété 1.
Soit $n$ un entier naturel et $E$ un ensemble fini ayant $n$ éléments. Alors,
l’ensemble des parties de $E$, noté ${\mathcal P}(E)$ contient exactement $2^n$ éléments.
$$\text{Card}({\mathcal P}(E))=2^n$$

Démonstrations

1ère méthode. Par récurrence

Pour chaque entier $n$, appelons $P_n$ la proposition logique :
$$P_n :\quad[\text{Card}({\mathcal P}(E))=2^n]$$
Montrons par récurrence que pour tout entier $n$, $P_n$ est vraie.

$i$) Initialisation.
Pour $n=0$, $E=\emptyset$.
Donc ${\mathcal P}(E)$ contient une seule partie $A=\emptyset$.
$\text{Card}({\mathcal P}(E))=1=2^0$.
Par conséquent, $P_0$ est vraie.

$ii$) Hérédité.
Soit $n$ un entier naturel fixé, et $E$ un ensemble fini ayant exactement $n$ éléments.
Supposons que la propriété est vraie au rang $n$. Donc :
$$\text{Card}({\mathcal P}(E))=2^n\quad(H.R.)$$

Montrons qu’elle est vraie au rang $n+1$.

Soit $a$ un élément étranger à $E$. Donc $a\not\in E$.
L’ensemble $E’=E\cup \{a\}$ contient exactement $n+1$ éléments.

Mais alors, ${\mathcal P}(E’)$ contient deux types de parties.

• Les parties de $E’$ qui ne contiennent pas $a$. Ce sont toutes les parties de $E$. Et d’après l’hypothèse de récurrence, leur nombre est égal à $\text{Card}({\mathcal P}(E))=2^n$.
• Et les parties de $E’$ qui contiennent $a$. Ce sont toutes les parties de $E$ auxquelles, on a adjoint $a$. Leur nombre est aussi égal à $\text{Card}({\mathcal P}(E))=2^n$.

Ces deux ensembles de parties de $E’$ étant disjoints, d’après le principe additif des cardinaux de deux parties disjointes, le nombre d’éléments de $E’$ est égal à :
$2^n+2^n=2\times 2^n=2^{n+1}$.

Par conséquent, $\text{Card}({\mathcal P}(E’))=2^{n+1}$
Ce qui montre que la proposition $P_{n+1}$ est vraie. La proposition $P_n$ est héréditaire.

Conclusion. Pour tout entier $n$, le nombre de parties d’un ensemble à $n$ éléments est bien égal à $2^n$.

2ème méthode. Par une méthode combinatoire

Soit $n$ un entier naturel et $E$ un ensemble fini ayant exactement $n$ éléments.

Une partie $A$ de $E$ peut posséder de $0$ à $n$ éléments.
Ainsi ${\mathcal P}(E)$ contient toutes les parties à $0$ éléments, plus toutes les parties à $1$ élément, plus toutes les parties à $2$ éléments et ainsi de suite, jusqu’aux parties à $n$ éléments.

Or, on sait que le nombre de parties à $k$ éléments, $0\leqslant k \leqslant n$ est égal à $\dbinom{n}{k}$. Ce qui donne :
$$\text{Card}({\mathcal P}(E))=\dbinom{n}{0}+\dbinom{n}{1}+\cdots+\dbinom{n}{n}$$
ce qui s’écrit :
$$\text{Card}({\mathcal P}(E))=\dsum_{k=0}^{n}\dbinom{n}{k}\quad(1)$$
Or d’après la formule du binôme, $(a+b)^n=\dsum_{k=0}^{n}\dbinom{n}{k}a^kb^{n-k}$.
En appliquant cette formule au cas $a=1$ et $b=1$, on obtient :
$$2^n=\dsum_{k=0}^{n}\dbinom{n}{k}\quad(2)$$
Par conséquent, d’après (1) et (2), on obtient :
$$\text{Card}({\mathcal P}(E))=2^n$$

Conclusion. Pour tout entier $n$, le nombre de parties d’un ensemble à $n$ éléments est bien égal à $2^n$.

2. Lien avec les $n$-uplets de $\{0,1\}$

Propriété 1.
Soit $n$ un entier naturel et $E$ un ensemble fini ayant $n$ éléments. Alors,
l’ensemble des parties de $E$, noté ${\mathcal P}(E)$ contient autant d’éléments que de $n$-uplets de $\{0,1\}$. $$\text{Card}({\mathcal P}(E))=2^n$$

Démonstration

$E$ un ensemble fini ayant $n$ éléments. On pose $E=\{x_1;x_2;\ldots;x_n\}$.
Nous allons définir une correspondance entre l’ensemble des parties de $E$ et l’ensemble des $n$-uplets de $\{0,1\}$.

Ce qui signifie que :

1. A chaque partie $A$ de $E$, correspond un unique $n$-uplets de $\{0,1\}$.
2. Et à chaque $n$-uplets de $\{0,1\}$, correspond une partie $A$ de $E$.

On suppose que les éléments de $E$ sont rangés dans l’ordre des indices. On procède comme dans un algorithme.

1°) Soit $A$ une partie de $E$. On teste chaque élément $x_k$.
$\bullet$ Si $x_1\in A$, on affecte $1$ à la première position du $n$-uplet. Sinon, on lui affecte un $0$.
$\bullet$ Si $x_2\in A$, on affecte $1$ à la deuxième position du $n$-uplet. Sinon, on lui affecte un $0$.
$\bullet$ et ainsi de suite, jusqu’à $x_n$.
Ainsi, à la partie $A$, nous avons fait correspondre 1 seul $n$-uplet.

2°) Réciproquement. Soit $(i_1;i_2;\ldots;i_n)$ un $n$-uplet de $\{0,1\}$, avec $i_k=0$ ou $1$ pour tout $k$ compris entre $0$ et $n$. On teste chaque élément $i_k$.

$\bullet$ Si $i_1=1$, alors $x_1\in A$. Sinon, $x_1\not\in A$.
$\bullet$ Si $i_2=1$, alors $x_2\in A$. Sinon, $x_2\not\in A$.
$\bullet$ et ainsi de suite, jusqu’à $i_n$.
Ainsi, à chaque $n$-uplet, nous avons fait correspondre 1 seule partie $A$.

Par conséquent, le nombre de parties de $E$, est égal au nombre de $n$-uplets de $\{0,1\}$.
Or, d’après le principe multiplicatif des cardinaux, on sait que :
$$\text{Card}(^n)=[\text{Card}(E)]^n\quad\text{ avec } E=\{0,1\}$$
Donc, le nombre de $n$-uplets de $\{0,1\}$ est égal à $2^n$.

Conclusion. $\text{Card}({\mathcal P}(E))=2^n$.

Remarques

Nous venons de voir que le nombre de $n$-uplets de $\{0,1\}$ est égal à $2^n$.
Il est clair qu’on pourrait prendre les $n$-uplets dans n’importe quelle paire d’objets. On obtient le même résultat : $2^n$

Ainsi, le nombre de mots de longueur $n$ sur un alphabet à deux éléments est égal $2^n$.
Le nombre de chemins dans un arbre correspondant à une succession de $n$ épreuves de Bernoulli, est égal $2^n$.
Le nombre d’issues correspondant à une succession de $n$ épreuves de Bernoulli, est égal $2^n$.

Exercices résolus

Exercice résolu n°1.