Proposition 13

If $n$ and $p$ are integers, then

Let E be a set with $n + 1$ elements, let P be the set of all subsets of E containing $p + 1$ elements, let $a$ be an element of E, and put

Let P′ (resp. P″) denote the set of subsets of $p + 1$ elements of E which contain $a$ (resp. do not contain $a$). The set P″ is the set of subsets of $p + 1$ elements of E′ and therefore has $\binom{n}{p+1}$ elements. The mapping $\mathrm{X} \to \mathrm{X} \cap \mathrm{E}'$ is a bijection of P′ onto the set of subsets of $p$ elements of E′, and P′ therefore has $\binom{n}{p}$ elements. The result now follows from the fact that P is the union of the disjoint sets P′ and P″.

Proposition 13 can also be proved by means of a simple calculation from the formula $\binom{n}{p} = \dfrac{n!}{p!(n-p)!}$ for $p \leqslant n$.