# combinational proof for $\binom{n}{k}=\frac{n}{k}*\binom{n-1}{k-1}$ (not algebraic) Understanding the order that cause division.

I need to proof the following : $\binom{n}{k}=\frac{n}{k}*\binom{n-1}{k-1}$ using combinational proof only

The main problem is the division in $k$, I'll be glad if someone could provide an explanation for division in $k$.

This is what I've done

• Problem

: choose a group of $k$ people from $n$ people

• Left

: $\binom{n}{k}$ - to choose k from n people. (definition)

• Right

$\binom{n-1}{k-1}$ - choose $k-1$ people from $n-1$.  $\frac{n}{k}$ - $n$ choose the first person to be in the group,$k$ umm, I don't know.

I think when I use the term first person in the group I created order in group and the group shouldn't have an order, yet I'm not sure how I defined it like how does the order looks, if someone could explain how to choose the first person cause order in the group and add a simple example so I'll understand how choosing the first person cause order I'll be very happy.

Any help will be appreciated, Thanks.

• Prove that $$k \binom{n}{k} = n \binom{n - 1}{k - 1}$$ instead. – Trevor Gunn Nov 23 '17 at 17:17

Suppose we are choosing a team of $k$ people from $n$ candidates. The team will have exactly one captain.

To count the number of possible teams, we could select the $k$ team members first, then from those $k$ members we choose the captain. This gives

$$\binom{n}{k}\cdot\binom{k}{1}\ =\ \binom{n}{k}\cdot k$$ configurations.

Another way to count these would be to first select the captain from the original $n$ people, then select the remaining $k-1$ team members from the $n-1$ remaining people. There are

$$\binom{n}{1}\cdot\binom{n-1}{k-1}\ =\ n\cdot\binom{n-1}{k-1}$$

such configurations.

These two methods of counting yield

\begin{align} \binom{n}{k}\cdot k\ &=\ n\cdot\binom{n-1}{k-1}\\\\ \binom{n}{k} &=\frac{n}{k}\cdot\binom{n-1}{k-1}. \end{align}

Note that division is okay here since the requirement that there be a captain means that $k>0$.