Prépa, 1re année › Dénombrement › Nombre de parties
Nombre de parties : énoncé (MPSI)
Théorème
Nombre de parties
Si $E$ est fini de cardinal $n$, l'ensemble $\mathcal{P}(E)$ de ses parties est fini et $$\operatorname{Card}\mathcal{P}(E)=2^n.$$
Démonstration : Nombre de parties
Démonstration
Preuve
L'application $A\mapsto\mathbf{1}_A$ est une bijection de $\mathcal{P}(E)$ sur $\{0,1\}^E$ : une partie est déterminée par son indicatrice, et toute $g:E\to\{0,1\}$ est l'indicatrice de $A=g^{-1}(\{1\})$. Donc $\operatorname{Card}\mathcal{P}(E)=\operatorname{Card}\{0,1\}^E=2^n$.
Concrètement : pour chacun des $n$ éléments, on décide s'il est dans la partie ou non, soit $2$ choix à chaque fois.
S’entraîner
- Applications et injections entre deux petits ensembles
- Délégués et comités
- Parties emboîtées
- Répartition en binômes
- Surjections sur un ensemble à trois éléments