1
$\begingroup$

My task is this:

Suppose $M$ is a set s.t. $|M|\geq 2$. If we pick two items from $M$, how many subsets can be made using either the first, second or both items?

This is a combinatorial problem, but since I no close to nothing about it, I'd like someone to explain the approach.

My work so far:

I wrote $M=\{x_1,x_2,\ldots\}$ and wrote it out for $|M|=2,\dots,5$ and found that $\#$ subsets were 3,6,12 and 24 respectively. From this I got a hunch that the answer could be $3\cdot 2^{|M|-2}$?

$\endgroup$
1
$\begingroup$

You empirically obtained the correct answer. To show it, note that, from the remaining $N-2$ items, we can form $\binom {N-2}{0} $ subsets containing zero elements, $\binom {N-2}{1} $ subsets containing one element, $\binom {N-2}{2} $ subsets containing two elements, and so on. This leads to $$\sum_{k=0}^{N-2} \binom{N-2}{k}=2^{N-2} $$ total subsets. Multiplying this to the $3$ possible initial choices (first item, second item, or both), you get the result.

$\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.