Proving (rigorously) that the number of $m$ element subsets of an $n$ element set is ${n \choose m}$

Question

I am trying to solve the following problem (Amann & Escher Analysis I, Exercise I.6.3):

Show that the number of $m$ element subsets of an $n$ element set is ${n \choose m}$.

I emphasize that the "size" of the subsets as noted in the problem have been defined as a bijection with, for example, $\{1,...,n\}$ and where ${n \choose m}$ has been defined (only in the context of the natural numbers) as the (unique) quotient of $n!$ by $m!(n-m)!$) if $m \leq n$, and 0 otherwise.

My attempt at a proof is as below. I have highlighted the step I cannot complete. Please note that a few times I refer to an exercise or a proposition. These are basic set theoretical lemmas etc., which I would be happy to clarify if not clear from the context of what's used. Also, please note that my text uses $\textrm{Num}$ for the cardinality function.

Let $m \leq n$ (if $m>n$ then there are no such subsets, and thus ${n \choose m} = 0$ is correct per the definition). We will give a partition of the bijections of $\{1,...,n\}$ onto $N$, $B(\{1,...,n\},N)$, as follows. Define $S$ as the set of all subsets of size $m$ in $N$ (a subset of the powerset of $N$). Define $A_M : = \{f \in B(\{1,...,n\},N) \mid f(\{1,...,m\} = M,\, M \in S)\}$. We claim (1) that $B(\{1,...,n\},N) = \cup_{i=1}^k A_{M_i}$, (2) that the $A_{M_i}$ are pairwise disjoint, and also (3) that $\operatorname{Num}(A_M) = m!(n-m)!$. Note that, tacit in this claim is the claim that there are finitely many (some $k \in \mathbb{N})$ subsets of size $m$ (the $M$) of a set $N$ of (finite) size $n$. This in turn follows if we can show that the set of all subsets of a finite set ($\mathcal{P}(N)$) is finite, since the set of all subsets of $N$ of size $m$ would be a subset of $\mathcal{P}(N)$, and so finite by Exercise 9. This latter statement is not quite the claim in Exercise 8, where we only have directly (given the hypotheses in that exercise) only that the set of subsets is countable, but not necessarily finite. But we proved in Exercise I.5.4 that $\operatorname{Num}(\mathcal{P}(N)) = 2^n$, so we are done.

(1) $B(\{1,...,n\},N) = \cup_{i=1}^k A_{M_i}$. That $B(\{1,...,n\},N) \supseteq \cup_{i=1}^k A_{M_i}$ is immediate from the definitions of the $A_{M_i}$, so we simply verify that $B(\{1,...,n\},N) \subseteq \cup_{i=1}^k A_{M_i}$. Let $f \in B(\{1,...,n\},N)$, and consider that $f(\{1,...,m\})$ is an $m$-element subset of $N$, because $f\mid_{\{1,...,m\}}: \{1,...,m\} \to f(\{1,...,m\})$ is a bijection (since $f$ an injection) from $\{1,...,m\} \to f(\{1,...,m\})$, which means by definition that $f\mid_{\{1,...,m\}}$ is a set of size $m$. Thus $f\mid_{\{1,...,m\}} \in S$, so that $f \in A_{M_i}$ for $M_i = f\mid_{\{1,...,m\}}$.

(2) $A_{M_i} \cap A_{M_j}$ for $M_i, M_j \in S$, $j \neq i$. Since $M_i \neq M_j$, for one of $i,j$ -- let's take $i$ WLOG -- there is\footnote{Actually, one can show that neither is a subset of the other, but we don't need that here.} an $a_i \in M_i$ with $a_i \notin M_j$. Let $f \in A_i$. Then by definition of $f$ there is a $j \in \{1.,,,.m\}$ such that $f(j) = a_i$. Since $f(j) = a_i \notin M_j$, we have that $f \notin A_{M_j}$, and we are done.

(3) Intuitively it must be true, because any bijection in that set can be "built up" out of the set of bijections restricted to $\{1,...,m\}$, plus a bijection on the last $n-m$ elements. Since Prop 6.3' says we have $m!$ and $(n-m)!$ choices for each such part of the $f \in A_M$, we conclude from the fundamental counting principle that $\operatorname{Num}{A_M} = m!(n-m)!$.

Now given the three facts above, we may apply Exercise 5 to $B(\{1,...,n\},N) = \cup_{i=1}^k A_{M_i}$ and so find by that formula that $$n! \stackrel{(1)}{=} \operatorname{Num}{B(\{1,...,n\},N)} = \operatorname{Num}{\cup_{i=1}^k A_{M_i}} = \sum_{i=1}^k m!(n-m)! = km!(n-m)!,$$ where in (1) we have again used Proposition 6.3'. By the uniqueness of the quotient (bottom page 34), we have $$k = {n \choose m},$$ which proves our claim given that $k$ was defined to be the number of $m$-element subsets of $N$ at the beginning. In using Exercise 5, we have also tacitly used that the subsets $M$ of the finite set $N$ are, themselves, finite. This is shown in Exercise 9.

I am struggling to rigorize the bolded part, (3). I mean, intuitively it must be true, because any bijection in that set can be "built up" out of the set of bijections restricted to $\{1,...,m\}$, plus a bijection on the last $n-m$ elements Those two sets have size $m!$ and $(n-m)!$, and if we "bring them together" we get $m!(n-m)!$. But I am trying to reduce this intuition to the definitions and so build a valid proof, but I can't think how to do so. Any proofs or even hints would be greatly appreciated.

Answer 1

We are given a set $N$ and a set $M \subseteq N$, and we define $n = \operatorname{Num}(N)$ and $m = \operatorname{Num}(M)$. (With this setup, $m \leq n$.) We define $A_M = \{f \in B(\{1,\ldots,n\},N) \mid f(\{1,\ldots,m\}) = M\}$. Then we want to show:

(3) $\operatorname{Num}(A_M) = m! (n-m)!$

Choose any element $a_M \in A_M$. (Is it clear from set theorems you already have that $A_M \neq \emptyset$?)

Let $P_k$ be the set of permutations on $\{1,2,\ldots,k\}$ —that is, the bijections $\{1,2,\ldots,k\} \to \{1,2,\ldots,k\}$. (The usual name for this set/group is $S_k$, but I don't want to cause confusion with your set $S$.)

Then there is a bijection $\varphi: P_m \times P_{n-m} \to A_M$. Given $\sigma \in P_m$ and $\tau \in P_{n-m}$, define the function $\varphi(\sigma,\tau) : \{1,\ldots,n\} \to N$ by

$$ \varphi(\sigma,\tau)(i) = \begin{cases} a_M(\sigma(i)) & 1 \leq i \leq m \\ a_M(m + \tau(i-m)) & m < i \leq n \end{cases} $$

This is well-defined since $$ 1 \leq i \leq m \implies 1 \leq \sigma(i) \leq m \leq n \implies a_M(\sigma(i)) \in M $$ $$ m < i \leq n \implies 1 \leq i-m \leq n-m \implies 1 \leq \tau(i-m) \leq n-m \\ \implies m < m+\tau(i-m) \leq n \implies a_M(m+\tau(i-m)) \notin M $$

showing that the arguments to $\sigma$, $\tau$, and $a_M$ are in the appropriate domains.

$\varphi(\sigma,\tau)$ is injective since:

• If $i\leq m < j$, then $\varphi(\sigma,\tau)(i) \in M$ and $\varphi(\sigma,\tau)(j) \notin M$, so $\varphi(\sigma,\tau)(i) \neq \varphi(\sigma,\tau)(j)$.
• If $i < j \leq m$, then $\sigma(i) \neq \sigma(j)$, so $\varphi(\sigma,\tau)(i) = a_M(\sigma(i)) \neq a_M(\sigma(j)) = \varphi(\sigma,\tau)(j)$.
• If $m < i < j$, then $\tau(i) \neq \tau(j)$, so $\varphi(\sigma,\tau)(i) = a_M(\tau(i)) \neq a_M(\tau(j)) = \varphi(\sigma,\tau)(j)$.

$\varphi(\sigma,\tau)$ is surjective: Given $y \in N$,

• If $y \in M$, then we may define $x = \sigma^{-1}(a_M^{-1}(y))$, and $\varphi(\sigma,\tau)(x) = y$.
• If $y \notin M$, then we may define $y = \tau^{-1}(a_M^{-1}(y))$, and $\varphi(\sigma,\tau)(x) = y$.

Therefore $\varphi(\sigma,\tau)$ is a bijection. Since we earlier proved $1 \leq i \leq m \implies \varphi(\sigma,\tau)(i) = a_M(\sigma(i)) \in M$, $\varphi(\sigma,\tau) \in A_M$.

Now let $b : \{1,\ldots,n\} \to N$ be any element of $A_M$. Then define $\sigma_{b_M}: \{1,\ldots,m\} \to \{1,\ldots,m\}$ and $\tau_{b_M}: \{1,\ldots,n-m\} \to \{1,\ldots,n-m\}$ by

$$ \begin{align*} \sigma_{b_M}(i) &= a_M^{-1}(b_M(i)) \\ \tau_{b_M}(i) &= a_M^{-1}(b_M(m+i)) - m \end{align*} $$

These values are in the claimed codomains:

$$ 1 \leq i \leq m \implies b_M(i) \in M \implies 1 \leq \sigma_{b_M}(i) \leq m $$ $$ 1 \leq i \leq n-m \implies m < m+i \leq n \implies b_M(m+i) \notin M \\ \implies m < a_M^{-1}(b_M(m+i)) \leq n \implies 1 \leq \tau_{b_M}(i) \leq n-m $$

Since each of the operations $b_M$, $a_M^{-1}$, adding $m$, and subtracting $m$ are injective, $\sigma_{b_M}$ and $\tau_{b_M}$ are injective, and therefore they are bijective permutations.

Then combining the definitions of $\varphi$, $\sigma_{b_M}$, and $\tau_{b_M}$ shows that for every $i \in \{1,\ldots,n\}$,

$$ \varphi(\sigma_{b_M}, \tau_{b_M})(i) = b_M(i) $$

which means that $\varphi(\sigma_{b_M}, \tau_{b_M}) = b_M$. The mapping from each $b_M \in A_M$ to $(\sigma_{b_M}, \tau_{b_M})$ as described here is an inverse of $\varphi$. So $\varphi$ is in fact a bijection between $P_m \times P_{n-m}$ and $A_M$.

Finally,

$$ \operatorname{Num}(A_M) = \operatorname{Num}(P_m \times P_{n-m}) = \operatorname{Num}(P_m) \operatorname{Num}(P_{n-m}) = m! (n-m)! $$