How many subsets are there of size k from the set {1,2,…n} such that if a subset contains 2 it doesn't contain 1?
My answer:
The total number of possible subsets of size k is just $|\Omega| ={n \choose k}$. Let $A_k$ be subset of size $k$ and divide by cases:
- i) subset contains both 1 and 2
- ii) subset containers neither 1 nor 2
- iii) subset contains 1 but not 2, or 2 but not 1 (same amount for both cases)
In other words, $$ |\Omega| = |1,2\in A_k| + |1,2\notin A_k| +2 |1\in A_k,2\notin A_k| $$.
For case i), we know that $1,2\in A_k$, so we count how many subsets of size $k-2$ there are from set $\{3,4,…n\}$, which is ${n-2} \choose {k-2}$. For case ii), we have to choose $k$ elements from $\{3,4,….n\}$, which gives $n-2 \choose k$ options. Thus, my answer would be
$$\dfrac{1}{2} ({n \choose k} – {n-2 \choose k} – {n-2\choose k-2})$$
The actual solution isn't given, so I don't know if my answer is correct or not. Any help?
Best Answer
It seems you've given the number of subsets $A$ of $\{1,\dots,n\}$ such that:
However, this is not what you're asked to find. To have "$2\in A\implies 1\notin A$" be true, we need one or both of the following to be true:
Fortunately, it's an easy fix. You've already found the number of ways that both can hold (case 2), as well as the number of ways that exactly one can hold (case 3). Thus, we must add $\binom{n-2}k$ to twice your answer, yielding $$\binom nk-\binom{n-2}{k-2}.$$
More simply, we could do it this way. The following statements are equivalent:
Thus, it's more straightforward to simply subtract your case 1 possibilities from the total number of possibilities, which of course yields the same result.