Exercice 11

Les quatre sommes se calculent par double comptage : on écrit le cardinal comme une somme d'indicatrices, $|A| = \sum_{x \in E} \mathbf{1}_{A}(x)$, et l'on intervertit les sommes (chapitre 3, proposition 6). Pour un élément $x$ fixé, il reste à compter les parties, ou les couples de parties, qui le contiennent.

Première somme. Pour $x \in E$, les parties qui contiennent $x$ s'écrivent $\{x\} \cup A'$ avec $A' \subset E \setminus \{x\}$ : il y en a $2^{n-1}$. Ainsi $$\sum_{A \in \mathcal{P}(E)} |A| = \sum_{A}\,\sum_{x \in E} \mathbf{1}_{A}(x) = \sum_{x \in E} \big|\{A \mid x \in A\}\big| = \sum_{x \in E} 2^{n-1}, \qquad \boxed{\sum_{A} |A| = n\,2^{n-1}}$$ On a compté de deux façons l'ensemble des couples $(x, A)$ tels que $x \in A$. On peut aussi regrouper les parties selon leur cardinal, et l'on retrouve l'identité $\sum_{k=0}^{n} k\binom{n}{k} = n2^{n-1}$ (chapitre 3, proposition 10).

Deuxième somme. Pour $x \in E$, les couples $(A, B)$ tels que $x \in A \cap B$ sont formés de deux parties qui contiennent $x$ : il y en a $2^{n-1} \times 2^{n-1} = 4^{n-1}$. $$\boxed{\sum_{(A, B)} |A \cap B| = n\,4^{n-1}}$$

Troisième somme. Pour $x \in E$, les couples tels que $x \notin A \cup B$ sont formés de deux parties de $E \setminus \{x\}$ : il y en a $4^{n-1}$, et il y a donc $4^{n} - 4^{n-1} = 3 \times 4^{n-1}$ couples tels que $x \in A \cup B$. $$\boxed{\sum_{(A, B)} |A \cup B| = 3n\,4^{n-1}}$$ On contrôle par la proposition 2 (iii), puisque $\sum_{(A, B)} |A| = 2^{n} \times n2^{n-1} = 2n4^{n-1}$ : $$\sum_{(A, B)} |A \cup B| = \sum_{(A, B)} |A| + \sum_{(A, B)} |B| - \sum_{(A, B)} |A \cap B| = 2 \times 2n4^{n-1} - n4^{n-1} = 3n4^{n-1} \ \checkmark$$

Quatrième somme. Pour $X$ et $Y$ disjoints, $|X| + |Y| = |X \cup Y|$ (proposition 2 (i)). Pour $x \in E$, les couples de parties disjointes tels que $x \in X \cup Y$ s'obtiennent en plaçant $x$ dans $X$ ou dans $Y$, de deux façons, puis en choisissant un couple de parties disjointes de $E \setminus \{x\}$, de $3^{n-1}$ façons (exercice 10). $$\boxed{\sum_{X \cap Y = \varnothing} \big(|X| + |Y|\big) = 2n\,3^{n-1}}$$ Les quatre formules ont été vérifiées par énumération pour $n \leqslant 5$. Pour $n = 2$, par exemple, la première somme vaut $0 + 1 + 1 + 2 = 4 = 2 \times 2^{1}$ ✓.

À retenir. Le double comptage transforme une somme de cardinaux, difficile à organiser, en une somme sur les éléments, où tous les termes sont égaux par symétrie. C'est l'ancêtre de la méthode des indicatrices de la section 21.6.3 : si $A$ est une partie de $E$ choisie au hasard sous la probabilité uniforme, la première somme montre que $|A|$ vaut $\frac{n}{2}$ en moyenne.