L’application $\Phi$ est une bijection : son inverse est $\Phi$ elle-même.

Supposons que $E$ soit un ensemble fini. Notre bijection $\Phi$ envoie un ensemble $\mathcal{Q} \subset \mathcal{P}(E)$ sur un ensemble de même cardinal.

Choisissons $E$ un ensemble à $n$ éléments, et soit $p\le n$ . Soit $\mathcal{Q} \subset \mathcal{P}(E)$ : $\mathcal{Q} = \left\lbrace F \subset E,\ \ \mathrm{Card} F = p \right\rbrace.$

Nous savons que $\mathrm{Card} \mathcal{Q} =C_n^p$ (c’est la définition de $C^p_n$ ). De plus $\begin{align*} \Phi(\mathcal{Q}) &= \left\lbrace \Phi(F),\ \ F \subset E,\ \ \mathrm{Card} F = p \right\rbrace \\ &= \left\lbrace \complement F,\ \ F \subset E,\ \ \mathrm{Card} F = p \right\rbrace \\ &= \left\lbrace G\subset E,\ \ \mathrm{Card} G = n-p \right\rbrace. \end{align*}$

Donc $\mathrm{Card} \Phi(\mathcal{Q}) = C_n^{n-p}$ . Et comme $\Phi$ est une bijection, $\mathrm{Card} \Phi(\mathcal{Q}) = \mathrm{Card} (\mathcal{Q})$ , donc $C_n^{n-p}=C_n^p$ .

exo7 230