On va s'inspirer de la démonstration de la formule du triangle de Pascal. Soit $E$ un ensemble ayant $m$ éléments, et $F$ une partie de $E$ ayant $q$ éléments.
On cherche le nombre de parties de $E$ ayant exactement $p$ éléments.
- Une telle partie peut ne contenir aucun élément de $F$. Il y a exactement
$\binom{m-q}p$ telles parties.
- Une telle partie peut contenir exactement un élément de $F$. On a $\binom q1$ choix pour
cet élément, et $\binom{m-q}{p-1}$ choix pour les autres.
- Plus généralement on compte le nombre de parties à $p$ éléments de $E$ contenant exactement $k$ éléments de $F$. Il y a $\binom q k$ possibilités pour choisir ces éléments de $F$, et $\binom{m-q}{p-k}$ possibilités pour choisir les autres éléments (ils sont $p-k$, à choisir parmi $m-q$). Le nombre de parties recherché dans ce cas est donc $\binom qk\times\binom {m-q}{p-k}$.
Faisant la somme pour $k$ de $0$ à $q$, on trouve la formule souhaitée. Remarquons que ce dénombrement fonctionne même si $p>m-q$, à condition d'utiliser la convention $\binom nk=0$ pour $k>n$.
