Exercice 36

1. L'application $X \mapsto (X \cap A, X \cap B)$ est une bijection de l'ensemble des parties $X$ de $A \cup B$ telles que $\mathrm{card}(X \cap A) = k$ et $\mathrm{card}(X) = q$ sur l'ensemble des couples $(X_{1}, X_{2})$ formés d'une partie de $A$ à $k$ éléments et d'une partie de $B$ à $q - k$ éléments. Sa réciproque est $(X_{1}, X_{2}) \mapsto X_{1} \cup X_{2}$, et $X_{1} \cup X_{2}$ a bien $q$ éléments, d'après le lemme 4 du chapitre 2, puisque $A$ et $B$ sont disjoints. Le lemme 6 du chapitre 2 donne le cardinal du produit. $$\boxed{\binom{a}{k}\binom{b}{q-k} \text{ parties}}$$

2. Les parties $X$ de $A \cup B$ à $q$ éléments se répartissent en $q + 1$ catégories disjointes, selon la valeur de $\mathrm{card}(X \cap A)$, qui va de $0$ à $q$. Le lemme 4 du chapitre 2, étendu à une réunion disjointe finie, donne la formule, puisque $A \cup B$ a $a + b$ éléments. $$\boxed{\sum_{k=0}^{q} \binom{a}{k}\binom{b}{q-k} = \binom{a+b}{q}}$$

3. On prend $a = b = q = n$, et l'on utilise la symétrie des coefficients binomiaux : $$\boxed{\sum_{k=0}^{n} \binom{n}{k}^{2} = \binom{2n}{n}}$$ Le chapitre 13 en donnera une autre démonstration, en identifiant les coefficients des deux membres de l'égalité de polynômes $$(1 + X)^{a}(1 + X)^{b} = (1 + X)^{a+b}.$$