5
$\begingroup$

This is a question from my first proofs homework and I am confused about the combinatorial argument aspect. I already did the algebraic proof. I think I am supposed to put into words what both sides represent? So the LHS would be the number of ways of picking a committee of $k$ members from $n$ people, or number of subsets of size $k$ from a total of $n$, but I don't know how to articulate what is happening on the RHS.

$\endgroup$
12
$\begingroup$

Here's a hint. Try multiplying through by $k$, so it's at least obvious that both sides are integers. Then what you want to show is that $k\binom{n}{k} = n\binom{n-1}{k-1}$. The LHS is now the number of ways to select a committee of $k$ members from $n$ people along with a decision of which of those $k$ will be chairperson. Can you reinterpret this to get the RHS?.

$\endgroup$
  • 5
    $\begingroup$ Okay, that helped a lot. So then the RHS would be the number of ways of selecting the chairperson first, and then forming the committee of k-1 from a total of n-1 people, because we assume the chairperson is a part of the committee? $\endgroup$ – Marla Mar 5 '13 at 16:05
  • $\begingroup$ Exactly right. I'm glad I could help. $\endgroup$ – Noah Stein Mar 5 '13 at 16:08
3
$\begingroup$

Your expression can be rewritten as $$ \binom{n}{k} \binom{k}{1}=\binom{n}{1}\binom{n-1}{k-1} $$ Hence LHS can be interpreted as the number of ways to select $k$ unique items out of $n$ AND then one out of these $k$. Then RHS is the number of ways to select one item out of $n$ AND then $k-1$ out of the remaining $n-1$.

$\endgroup$
  • $\begingroup$ It seems worth pointing out that this argument works more generally, in the sense that you can replace all the $1$'s by $m$ for any $m\leq k$. $\endgroup$ – Andreas Blass Mar 5 '13 at 17:39
  • $\begingroup$ A generalization of this idea leads to multinomial coefficients. $\endgroup$ – Lord_Farin Apr 18 '13 at 7:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.