# How many subsets of $S$ are there that contain $x$ but do not contain $y$?

Let $S$ be a set of size $37$, and let $x$ and $y$ be two distinct elements of $S$. How many subsets of $S$ are there that contain $x$ but do not contain $y$?

This question is on a practice exam that I am reviewing for tomorrow. The answer key says that the answer to this question is $2^{37} - 2^{35}$.

I fail to see how this is correct as $2^{37}$ would be the amount of all subsets and $2^{35}$ is the amount of subsets containing x and y (I believe), therefore the answer would be the # of subsets that do not contain x or y, which doesn't answer the question.

I thought the answer should be $2^{36} - 2^{35}$, where $2^{36}$ is the number of subsets containing $x$, taking away the number of subsets that contain both $x$ and $y$, therefore being left with the number of subsets that contain $x$ and not $y$.

Can someone please confirm that I am right or explain to me why I am wrong?

• You are correct, the number of such subsets is $2^{36}-2^{35}$ or simply $2^{35}$. The answer key is just wrong, assuming the problem is quoted correctly above. – hardmath Apr 16 '15 at 16:00

You are correct; the answer should be $2^{36}-2^{35}=2^{35}$.
Another way of looking at it: $x$ must be in any such subset, and $y$ must not be. Thus, we have $35$ "free" elements that could either be in or out of the subset. So, there are $2^{35}$ ways of forming that subset.