0
$\begingroup$

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

How many subsets of $S$ are there that contain $x$, but do not contain $y$.

Can you explain why the answer is $2^{35}$?

$\endgroup$
2
$\begingroup$

There is an obvious bijection between the powerset of $S\setminus\{x,y\}$ and the set of sets you want to count.

$\endgroup$
1
$\begingroup$

Hints:

How many sets are there in $\;S\setminus\{y\}\;$ which also contain $\;x\;$ ?

Or in other words: you may want to look at all the sets of the form

$$A\cup\{x\}\;,\;\;A\subset S\setminus\{x,y\}\; ...$$

$\endgroup$
0
$\begingroup$

Imagine listing all 37 elements of the set $S$. To build a subset, you go through the elements one at a time and either circle them (if the element is to be included) or cross them out (if the element is to be excluded). How many choices do you get to make? Note that for every element except x and y, there are two possible choices. However, you don't get to choose when you hit x and y, because x is required to be in and y is required to be out. So you get 35 free choices, each of which can go two ways.

$\endgroup$

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.