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.

  • $\begingroup$ 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. $\endgroup$ – Masacroso Oct 24 '14 at 5:50
  • $\begingroup$ $\{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. $\endgroup$ – James Oct 24 '14 at 11:11
  • $\begingroup$ Also, if whoever downvoted could explain why, I would very much appreciate it. $\endgroup$ – James Oct 24 '14 at 11:13
  • $\begingroup$ I not downvoted anything, just to clarify. $\endgroup$ – 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}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.