Exercise 1, § 5

This solution was written by nemotron-3-ultra-free and judged by a machine. It is not Bourbaki's and it has not been checked by a person.

Let $n$, $p$, $q$ be integers such that $p \leqslant n$ and $q < p$. Consider the set $E = [1, n]$ of integers from $1$ to $n$. By Corollary 1 to Proposition 11, the number of subsets of $E$ with exactly $p$ elements is $\binom{n}{p}$.

For each integer $k$ with $q+1 \leqslant k \leqslant n-p+q+1$, let $\mathscr{P}_k$ be the set of all $p$-element subsets $X$ of $E$ whose $(q+1)$-th smallest element equals $k$. The sets $\mathscr{P}_k$ are pairwise disjoint and their union is the set of all $p$-element subsets of $E$; indeed, if $X$ is a $p$-element subset with elements $x_1 < \dots < x_p$, then $x_{q+1}$ must satisfy $q+1 \leqslant x_{q+1} \leqslant n - (p-q-1) = n-p+q+1$, so $X$ belongs to exactly one $\mathscr{P}_k$.

Fix $k$ in the above range. By Proposition 5 of no. 3, the interval $[1, k-1]$ has $k-1$ elements and the interval $[k+1, n]$ has $n-k$ elements. To form a subset $X \in \mathscr{P}_k$, we must choose $q$ elements from $[1, k-1]$ and $p-q-1$ elements from $[k+1, n]$, and then take their union with $\{k\}$. The number of ways to choose $q$ elements from $[1, k-1]$ is $\binom{k-1}{q}$ by Corollary 1 to Proposition 11 applied to the set $[1, k-1]$. The number of ways to choose $p-q-1$ elements from $[k+1, n]$ is $\binom{n-k}{p-q-1}$ by the same corollary applied to $[k+1, n]$. These choices are independent, and the mapping $(A, B) \mapsto A \cup B \cup \{k\}$ is a bijection from the Cartesian product of the set of $q$-element subsets of $[1, k-1]$ and the set of $(p-q-1)$-element subsets of $[k+1, n]$ onto $\mathscr{P}_k$. Hence $|\mathscr{P}_k| = \binom{k-1}{q} \binom{n-k}{p-q-1}$.

Since the sets $\mathscr{P}_k$ form a partition of the set of all $p$-element subsets of $E$, the cardinal of the latter is the sum of the cardinals of the $\mathscr{P}_k$. Therefore