Exercice 29

1. On liste les parties par cardinal croissant : $$\varnothing \; ; \; \{a\} \; ; \; \{b\} \; ; \; \{c\} \; ; \; \{a\,;b\} \; ; \; \{a\,;c\} \; ; \; \{b\,;c\} \; ; \; \{a\,;b\,;c\}$$

2. Construire une partie, c'est répondre par oui ou par non à $n$ questions successives : « l'élément $x_{1}$ est-il dans la partie ? », puis $x_{2}$, et ainsi de suite. Chaque réponse offre deux possibilités, indépendamment des autres.

Une partie correspond donc exactement à un $n$-uplet de l'ensemble $\{\text{oui}\,; \text{non}\}$, qui compte deux éléments : $$\boxed{\text{Le nombre de parties de } E \text{ est } 2^{n}}$$ Pour $n=3$, on retrouve bien $2^{3}=8$.

3. Une partie de cardinal $p$ est une combinaison de $p$ éléments parmi $n$, il y en a donc $\dbinom{n}{p}$. Or toute partie a un cardinal compris entre $0$ et $n$, et ces cas sont deux à deux disjoints. Le principe additif donne : $$\text{nombre de parties}=\binom{n}{0}+\binom{n}{1}+\dots+\binom{n}{n} =\sum_{p=0}^{n}\binom{n}{p}$$ En comparant avec la question 2, où le même nombre a été trouvé égal à $2^{n}$ : $$\boxed{\sum_{p=0}^{n}\binom{n}{p}=2^{n}}$$ Ce raisonnement est un double dénombrement : le même ensemble a été compté de deux façons.

4. La ligne $n=4$ du triangle de Pascal est $1$, $4$, $6$, $4$, $1$ : $$1+4+6+4+1=16=2^{4}$$

$$\boxed{\text{L'égalité est vérifiée}}$$ La conjecture de l'exercice 19 est donc démontrée.

5. $$2^{10}=\boxed{1\,024 \text{ parties}}$$

6. Pour $n=4$, les parties de cardinal pair sont celles de cardinal $0$, $2$ ou $4$ : $$\binom{4}{0}+\binom{4}{2}+\binom{4}{4}=1+6+1=8=2^{3}$$ Pour $n=5$, ce sont celles de cardinal $0$, $2$ ou $4$ : $$\binom{5}{0}+\binom{5}{2}+\binom{5}{4}=1+10+5=16=2^{4}$$

$$\boxed{\text{Conjecture : il y a } 2^{n-1} \text{ parties de cardinal pair}}$$ Autrement dit, exactement la moitié des parties ont un cardinal pair.

7. Il suffit de retirer les deux parties exclues, à savoir $\varnothing$ et $E$ : $$\boxed{2^{n}-2 \text{ parties}}$$