Nombre de parties : énoncé (Terminale spé)

Si $n=0$, $E=\emptyset$ a une seule partie, $\emptyset$, et $2^0=1$.

Soit $n\geqslant1$ et $E=\{x_1;x_2;\ldots;x_n\}$. À toute partie $A$ de $E$, on associe le $n$-uplet $(\varepsilon_1;\ldots;\varepsilon_n)\in\{0;1\}^n$ défini par $$\varepsilon_i=\begin{cases}1 & \text{si } x_i\in A\\ 0 & \text{si } x_i\notin A.\end{cases}$$ Réciproquement, tout $n$-uplet de $\{0;1\}^n$ définit une unique partie de $E$ : celle formée des $x_i$ pour lesquels $\varepsilon_i=1$.

Cette correspondance est donc une bijection entre $\mathcal{P}(E)$ et $\{0;1\}^n$. Ces deux ensembles ont le même cardinal, et d'après le nombre de k-uplets : $$\mathrm{card}\big(\mathcal{P}(E)\big)=\mathrm{card}\big(\{0;1\}^n\big)=2^n.$$ Autrement dit : pour construire une partie, on décide, pour chacun des $n$ éléments, s'il est dedans ou non, soit 2 choix à chaque fois.