# How to count the amount of subsets within a set

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 and y, but do not contain z?

(a) $2^{33}$

(b) $2^{34}$

(c) $2^{35}$

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

This is a review question, I have no idea how to approach it, If someone can help that'd be appreciated!

My attempt is that $2^n$ determines the number of subsets in a set

So without Z, there is no {Z}, {Z,X}, {Z,Y}

therefore you take 3 off of 37 so $2^{34}$ is final answer

We want to count the number of subsets of $S$, which contain $x,y$ but do not contain $z$. There is an obvious bijection between such subsets, and arbitrary subsets of $S\setminus\{x,y,z\}$ given by just adding $x$ and $y$ to a subset of $S\setminus\{x,y,z\}$. So the cardinality of $S\setminus\{x,y,z\} = 37-3 = 34$ and so there are $2^{34}$ subsets.

Another way of thinking about the bijection, is to say, to define a subset of $S$ we need to decide whether each element is in or out. We are told $x$ and $y$ are in, and also that $z$ is out. That leaves us $34$ more choices of "in" and "out" which is $2^{34}$ choices.

• I have a doubt... What happen with the subset that is only $\{x,y\}$? I may be wrong here but I think it is $2^{34}+1$, Im not sure if void can be counted as a subset. – Masacroso Oct 24 '14 at 5:50
• $\{x,y\}$ corresponds to the empty subset of $S\setminus \{x,y,z\}$ or, to when you choose "out" whenever you have a choice. You may note that $2^{34}+1$ isn't even an option for the OP. – James Oct 24 '14 at 11:11
• Also, if whoever downvoted could explain why, I would very much appreciate it. – James Oct 24 '14 at 11:13
• I not downvoted anything, just to clarify. – Masacroso Oct 24 '14 at 18:44

Fix $x$ and $y$ in the set and start adding elements one by one from from the rest of the 34 elements(without including $z$).

There is one combination with just $x$ and $y$. There are $34\choose 1$ combinations with 1 extra element, $34\choose 2$ combinations with two extra elements and so on.

So the total number of combinations is $$1+{34\choose 1} + {34\choose 2}+....{34\choose 34}=2^{34}$$