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!