# Discrete Math Combinatorics Sets and Subsets

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?

(a) 2^35

(b) 2^36

(c) 2^37 − 2^35

(d) 2^35 + 2^36

Think of it this way: Let $S = \left\lbrace s_1,s_2, \ldots, s_{37} \right\rbrace$. Every subset $A \subseteq S$ can be identified by a sequence $$(a_1,a_2, \ldots, a_{37}) ~ , ~ a_i \in \{0,1\}.$$ in the way that $a_i = 1$ if $s_i \in A$ and $a_i =0$ if $s_i \notin A$. Now you know that $x$ is some $s_m$ and $y$ is some $s_n$. If $x$ is in $A$ and $y$ isn't, this means that $a_m = 1$ and $a_n = 0$. However, every other $a_i$ can be either $0$ or $1$. Since there are $35$ other $a_i$'s left, you are looking for the number of sequences of length $35$ using only the symbols $0$ and $1$. This is $$\underbrace{2 \cdot 2 \cdot 2 \cdot \ldots \cdot 2}_{35 \text{ times}} = 2^{35}$$ because at every position you have $2$ symbols to choose from.
There are $2^{|S \setminus \{x,y\}|}=2^{35}$ subsets of $S \setminus \{x,y\}$. We add $x$ to each of them to obtain the $2^{35}$ subsets of $S$ that contain $x$ but don't contain $y$.