12
$\begingroup$

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

I have expanded it this far:

$$\frac{k \cdot n!}{k!(n-k)!} = \frac{n \cdot (n-1)!}{(k-1)!(n-k)!} $$

but then I am stuck from where to go from there.

$\endgroup$
2
  • $\begingroup$ Recursive definition of $m! = m\cdot(m-1)!$. $\endgroup$ Oct 16, 2013 at 20:06
  • 1
    $\begingroup$ It looks as if what you're attempting is an algebraic proof rather than a combinatorial proof. $\endgroup$ Oct 16, 2013 at 20:50

3 Answers 3

29
$\begingroup$

To select a committee of $k$ people with a president from a group of $n$ people, you can

  1. select the $k$ committee members, and then select the president from the members, or
  2. select the president from the $n$ people, and the $k-1$ remaining committee members from the remaining $n-1$ people.
$\endgroup$
1
  • 2
    $\begingroup$ You could also choose $k-1$ ordinary committee members from the group of $n$, and then a president from the remaining $n-k+1$, so $\displaystyle (n-k+1){n \choose k-1}$ should also give the same value $\endgroup$
    – Henry
    Oct 5, 2014 at 0:09
9
$\begingroup$

Here is a more comprehensive combinatorial proof.

Given $n$ people, we can form a committee of size $k$ in ${n\choose k}$ ways. Once the committee is formed we can pick a committee leader in $k$ ways. Thus we can form a committee of size $k$ with a committee leader in $k{n\choose k}$ ways. We can count the same thing by first picking a committee leader in $n$ ways. Once this has been done we can form the committee with the remaining $n-1$ people in ${n-1\choose k-1}$ ways. We choose $k-1$ people from $n-1$ people because a leader has already been specified. Thus we can pick a committee leader first and then form the committee with the remaining people in $n{n-1\choose k-1}$ ways. Hence $k{n\choose k}=n{n-1\choose k-1}$.

$\endgroup$
3
$\begingroup$

Left Side = $k\binom{n}{k} = k\frac{n!}{k!(n-k)!}$

Because $\frac{k}{k!} = \frac{1}{(k-1)!}$

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

Right side = $n\binom{n-1}{k-1} = \frac{n(n-1)!}{(k-1)!(n-1-k+1)!} = \frac{n(n-1)!}{(k-1)!(n-k)!}$

Because $n(n-1)! = n!$

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

Left Side = Right side, therefore proved !!

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .