Let $S$ be a set of size $37$, and let $x$,$y$, and $z$ be three distinct elements of $S$.

  1. How many subsets of $S$ are there that contain x and $y$, but do not contain $z$?
  2. How many subsets of $S$ are there that contain x or $y$, but do not contain $z$?

I got these questions during a midterm exam and I felt like I didn't have enough information to solve them. Is there like a formula to these kind of questions? Can you please provide explanations to the answers?



For the first case, you have 37 elements in all, but are excluding $z$, leaving 36.

  1. If both $x$ and $y$ are included, you get to choose only the other 34 elements, giving $2^{34}$ possible sets.
  2. If you decide to include $x$, by the same reasoning above you get $2^{35}$ subsets, if you include $y$ again $2^{35}$; but that counts the sets containing $x$ and $y$ twice (once in each collection) and you have to discount them, so the result is $2 \cdot 2^{35} - 2^{34}$.
  1. We want subsets of 36 elements containing at least two of them. We can just take those two out and then chose from there all possible subsets of 34 elements. That is, 2^34 if I remember right (cardinality of a power set is 2 to the cardinality of the set?).

  2. Do the same thing, but this time we have to choose which of x or y we remove, so we have to take twice as many possibilities. There are 2^34 for choosing x, and 2^34 for choosing y. hence the answer is 2^35.

It's been a while since I took discrete math, but this is probably what I would turn in. The idea is that z clearly makes no difference to how many ways there are to choose so just throw it out. Then x and y, if they are both in, we can only count once. If there are two ways to choose them (problem 2) then we count each of them. Then we take subsets of the remaining, and this will be the amount required.


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.