Proof that $\binom{ n}{k} \in \mathbb N$

Question

This problem is from Spivak. Give another proof that $\binom{n}{k}$ is a natural number by showing that $\binom{n}{k}$ is the number of sets of exactly $k$ integers each chosen from $1, \ldots,n$.

I went ahead and argued that since, by the multiplication principle, the number of ways to choose $k$ integers from $n$ with order is $n(n-1)(n-2)\cdots(n-k+1)$ or $\frac{n!}{(n-k)!}$ and the number of ways to arrange any $k$ integers is $k!$, that the number of ways to choose $k$ integers from $1,\cdots,n$ without order has to be $\frac{n!}{k!(n-k)!}=\binom{n}{k}$. Somehow though, in a chapter on induction, I doubt this is what Spivak was looking for.

I just don't know how to rigorously define the idea of "the number of subsets of $1, \ldots, n$ with cardinality $k$."

Answer 1

This is the given answer to that question:

There are $n(n-1)...(n-k+1)$ $k$-tuples of distinct integers each chosen from $1,...,n$ since the first can be picked in $n$ ways, the next in $n-1$ ways, etc. Now each set of exactly $k$ integers can be arranged in $k!$ $k$-tuples, so there are $n(n-1)...(n-k+1)/(k!)= {n\choose k}$

Hopefully that elucidates it a little; I sympathise with you about doing Spivak's problems and sometimes not really knowing how he intended you to answer it. I remember this problem and my answer looked nothing like the one above.

Answer 2

No, that's about it. It's the achetypical double counting argument.

$\displaystyle \frac{n\cdot(n-1)\cdot(n-2)\cdots(n-k+1)}{1\cdot 2\cdot 3 \cdots k}$ is not obviously a natural number.

However, because the numerator, $n(n-1)\cdots(n-k+1)$, is the count of ways to select an ordered sequence of $k$ elements with out repetition from a set of $n$ elements, and the denominator, $1\cdot 2\cdots k$, is the count of permutations of such sequences, then the quotient, must be the count of subsets, with cardinality $k$, of a set with cardinality $n$; and is thus a natural number.

Answer 3

I don't know if this is exaclty what are you asking:

Define the binomial coefficient $\binom {n} {k}$ as follows: the number of subsets of ordered $k$ in the set $\{1,\ldots,n\}$.

Claim: For every integer $n$ and every $k\le n$ we have $\binom {n} {k}=\binom {n-1} {k}+\binom {n-1} {k-1}$

Proof: Let $S$ be a subset of $\{1,\ldots,n\}$ of $k$ elements. Then either $n\in S$ or $n\notin S$. If $n\notin S$, so $S \subset \{1,\ldots,n-1\}$ and by definition there are $\binom {n-1} {k}$ of these subsets. Suppose that $n\in S$, define $S' = S \setminus\{n\}$. Then $S'$ is a subset of $\{1,\ldots,n-1\}$ and so there are $\binom {n-1} {k-1}$ such sets $S'$. Hence there are $\binom {n-1} {k-1}$ subsets of ordered $k$ which contain $n$. Thus this give us a total of $\binom {n-1} {k}+\binom {n-1} {k-1}$ sets of ordered $k$ in general, i.e., $\binom {n} {k}=\binom {n-1} {k}+\binom {n-1} {k-1}$

Proposition:$\binom {n} {k}= \frac{n!}{k! (n-k)!}$

Proof: Let $P(n)$ be the statement: "$\binom {n} {k}= \frac{n!}{k! (n-k)!}$ is true for all $k\le n$". Suppose that $P(n-1)$ is true, so

$$\binom {n-1} {k}=\frac{(n-1)!}{k!(n-1-k)!}\;\; \text{and }\;\; \binom {n-1} {k-1}=\frac{(n-1)!}{(k-1)!(n-k)!}$$

Thus by the claim

\begin{align}\binom {n} {k}=\binom {n-1} {k}+\binom {n-1} {k-1}=\frac{(n-1)!}{k!(n-1-k)!}+\frac{(n-1)!}{(k-1)!(n-k)!}\\= \frac{n!}{k! (n-k)!} \end{align}

So this definition of binomial coefficient agrees with the other, and I suppose that you have already proven that $\frac{n!}{k! (n-k)!}$ is a natural number.