1
$\begingroup$

Sorry for the long title, I'm new here & not sure of the appropriate way to post long questions. The full question is:

Let n>=2,k>=2. The set of all k-element subsets of [n] may be partitioned into 4 classes: (i) class of subsets containing 1 & 2, (ii) class of subsets containing 1 but not 2; (iii) class of subsets containing 2 but not 1; (iv) class of subsets containing neither 1 nor 2.

a) how many k-element subsets of [n] fall into class (i)? class (ii)? class (iii)? class (iv)?

b) What recurrence relation follows from these answers?

My method for answering a) is to try to make sense of things by making n & k equal to integers, say n = 10 & k = 5. Then for class (i) I'd say "10 choose 5 minus 8 choose 5", since this would account for 1 & 2, I think?

If this is correct for class (i), my intuition for class (ii) would be to subtract both again but somehow add 1 back into the mix, but I'm not sure how to do this.

Again, I'm new here & hope to learn to participate in this great community in the next few days. Thanks!

$\endgroup$
1
$\begingroup$

For each problem you need to know how many elements you are choosing, and how many you can choose from. I will do (ii) and leave the rest to you.

There are $n$ elements available altogether and you have to choose $k$. But if the set contains $1$ and not $2$ then

  • you have to choose $k-1$ elements, because $1$ has already been chosen;
  • there are $n-2$ elements to choose from, because $1$ cannot be chosen again, and $2$ cannot be chosen at all.

So the number of possible subsets in case (ii) is $C(n-2,k-1)$.

See if you can do the rest.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, David! So by that reasoning I guess class (ii) & (iii) are the same, correct? I'd go on to solve (iv) as C(n - 2, k - 2) if I'm understanding correctly. But it seems I don't have the proper idea for solving class (i) when both 1 & 2 must be included. $\endgroup$ – BigD4J Jan 29 '15 at 0:33
  • $\begingroup$ Yes, (ii) and (iii) have the same answers. But your answer for (iv) is wrong, go through the same steps carefully and work out how many elements you need, from how many options. Remember you always have to end up with $k$ elements. Same for (i). $\endgroup$ – David Jan 29 '15 at 2:32
  • $\begingroup$ I've rechecked the problem for (iv). If I can't choose 1 or 2, then I have n-2 elements to choose from, then k elements to choose. Thus, C(n-2,k). At least I hope this is correct. Thanks for your instruction & for stating things clearly! $\endgroup$ – BigD4J Jan 29 '15 at 13:55
  • $\begingroup$ That's correct, well done. $\endgroup$ – David Jan 29 '15 at 23:17

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.