Consider the set $A = \{1, 2, \ldots , n\}$. Count the number of subsets of $A$ of cardinality $k$ in two ways. One of those ways must be to count them in two steps as follows.
• How many subsets of cardinality $k$ do not contain the numbers $1$ and $2$?
• How many subsets of cardinality $k$ do contain the numbers $1$ and/or $2$?
I need to count this $2$ ways and I can't figure out the second way that has to do with the bullet points. Can anyone help?
Best Answer
Break it into three cases:
1 - contains neither 1 nor 2 $$n_1 = \binom{n-2}k$$ 2 - contains a 1 but no 2 $$n_2 = \binom{n-2}{k-1}$$
3 - contains a 2 but no 1 $$n_3= \binom{n-2}{k-1}$$