0
$\begingroup$

I have two things that I need to prove using Combinatorial proofs (where you ask a question that satisfies both sides of an equation) and I have no idea what I'm doing.

  1. Prove $C(n,3) = C(2,2) + C(3,2) + C(4,2) + \ldots + C(n-1,2)$. The question that I need to be answered is, "How many 3 element subsets does an n element set have?" The first part is trivial, as the answer is $nC3$ by the definition of the Binomial Coefficient. However, I have no idea how to prove the second half of the equation satisfies the question. That is, how would I go about proving an $n$ element set has $C(2,2) + C(3,2) + C(4,2) + \ldots + C(n-1,2)$ subsets of 3 elements?

  2. Prove $k C(n,k) = n C(n-1,k-1)$ combinatorial proof. While this is trivial to prove algebraically, I have to find a question that both sides of the equation answer, similar to the problem above with the 3 element subsets.

  3. Finally, does anybody have any tips for getting through this class? The median score on our first exam was ~58% and our professor doesn't give us a curve. I got a 55, sitting at around a D- with the few homework grades we've gotten back. I am really pretty decent at other math classes, but this class has been kicking my proverbial ass. I'm just venting right here, but still. I need help.

$\endgroup$

closed as too broad by Bobson Dugnutt, choco_addicted, Claude Leibovici, Watson, Morgan Rodgers Mar 8 '16 at 11:00

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Are you using any particular book for the class? $\endgroup$ – Brian M. Scott Mar 8 '16 at 2:24
2
$\begingroup$

HINTS:

  1. Classify the $3$-element subsets of $\{1,2,\ldots,n\}$ according to their largest elements. If $3\le k\le n$, how many $3$-element subsets of $\{1,2,\ldots,n\}$ have $k$ as largest element?

  2. You have a pool of $n$ players. How many ways are there to pick a team of $k$ of those players, assigning one of the chosen players to be captain? If you still don’t see it after giving it some serious thought, take a look at the further hint in the spoiler-protected block below.

You can choose the team and then the captain, or you can choose the captain and then the rest of the team.

$\endgroup$
  • $\begingroup$ Thank you so much! This is really helpful, and I'm officially declaring StackExchange to be better than /r/LearnMath at providing easily understandable answers to my problems. $\endgroup$ – Mr Thysbe Mar 8 '16 at 2:45
  • $\begingroup$ @MrThysbe: You’re very welcome! $\endgroup$ – Brian M. Scott Mar 8 '16 at 2:48

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