Help finding a combinatorial proof of $k {n \choose k } = n {n - 1 \choose k -1}\;$

Question

I am unsatisfied with the answers here. (Half of which used algebraic methods despite being advised not to!)

Help finding a combinatorial proof of $k {n \choose k } = n {n - 1 \choose k -1}$

I have completed the algebraic proof, it was easy. I am unsure how to do a combinatorial proof, or what exactly that pertains to.

Is this the expression needed:

$$\begin{pmatrix} n+1\\r\end{pmatrix}=\begin{pmatrix}n\\r\end{pmatrix}+\begin{pmatrix}n\\r-1\end{pmatrix}$$$$???$$

Answer 1

I will prove the general statement.

$$ \binom{n}{k}\binom{k}{m} = \binom{n}{m} \binom{n-m}{k-m}$$

Let $S$ be an $n$ set. Consider the set $T$ of all ordered pairs $(A,B)$ where $A$ is $k$-subset of $S$ and $B$ is an $m$-subset of A. We prove this statement by counting the elements in $T$ in two ways.

• Set $A \subseteq S$ can be choosen in $\binom{n}{k}$ and set $B \subseteq A$ can be chosen in $\binom{k}{m}$ ways and so $|T| = \binom{n}{k}\binom{k}{m} $
• An $m$-subset $B$ of $S$ cab be choosen in $\binom{n}{m}$ ways for each choice of set $B$, choose a $(k-m)$-subset $C$ of $S-B$ and let $A = B \cup C$. Then $A$ is a $k$ subset of S and $B \subseteq C$. Thus the number of ways of choosing set $A$ is equal to number of ways of choosing set $C= \binom{n-m}{k-m}$. Hence $|T|= \binom{n}{m} \binom{n-m}{k-m} $.

And so result follows. For this problem take $m=1$ $\Box$