Exercice corrigé : Couples de parties emboîtées

Soit $E$ un ensemble fini à $n$ éléments ($n\geqslant1$). On s'intéresse aux couples $(A;B)$ de parties de $E$ tels que $A\subset B$.

1. On prend $E=\{a;b\}$. Dresser la liste de ces couples et les compter.
2. On revient au cas général et on note $E=\{x_1;\ldots;x_n\}$. Pour chaque élément $x_i$, combien de situations sont possibles vis-à-vis de $A$ et $B$ ? En construisant une bijection avec $\{0;1;2\}^n$, montrer qu'il y a $3^n$ couples $(A;B)$ avec $A\subset B$.
3. Dénombrer ces couples d'une autre façon, en classant selon le nombre $k$ d'éléments de $B$. En déduire que $\displaystyle\sum_{k=0}^{n}\binom{n}{k}2^k=3^n$, et vérifier pour $n=3$.
4. Combien y a-t-il de couples $(A;B)$ de parties de $E$ quelconques ? Combien vérifient $A\not\subset B$ ? Donner les valeurs pour $n=3$.