Finding the subsets in a set that contains x or y but not z

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

$(a) 2^{36} − 2^{34}$

$(b) 2^{36} − 2^{35}$

$(c) 2^{37} − 2^{34}$

$(d) 2^{37} − 2^{35}$

This is a review question, so if someone can help me out it would be appreciated!

Thanks!

• What have you tried? Working out the solution when $S$ has size $4$ or $5$ might give you a clue as to how to proceed. – ajd Oct 24 '14 at 5:08

Hints:

The number of subsets of $S$ that does not contain $z$ is the same as the number of subsets of $S-\{z\}$.

The number of subsets of $S$ that contains $x$ or $y$ are all the subsets minus all the subsets of $S-\{x,y\}$.

Let A be the set of subsets of S that contain x but not z, and

let B be the set of subsets of S that contain y but not z.

Then $|A|$ is the number of subsets of $S-\{x,z\}$, and $|B|$ is the number of subsets of $S-\{y,z\}$; so

$|A\cup B|=|A|+|B|-|A\cap B|=2^{35}+2^{35}-2^{34}=2^{36}-2^{34}$

since $|A\cap B|$ is the number of subsets of $S-\{x,y,z\}$.

Alternate solution:

For $\begin{bmatrix}x\\y\\z\end{bmatrix}$, we have 3 choices: $\begin{bmatrix}1\\1\\0\end{bmatrix},\begin{bmatrix}1\\0\\0\end{bmatrix},\begin{bmatrix}0\\1\\0\end{bmatrix}$.

For each of the other 34 elements, there are 2 choices; so there are

$3\cdot2^{34}=(4-1)\cdot2^{34}=2^{36}-2^{34}$ possible subsets.