3
$\begingroup$

If you have a set of $N$ items, how many subsets can you make? For example, for the set existing of $3$ items (Item1, Item2 and Item3) the subsets are Item1, Item2, Item3, Item2+3, Item1+2, Item1+3 and Item1+2+3. Is there a general formula for this?

I think it might be $2^N-1$, but I'm not sure.

Thank you in advance!

$\endgroup$
  • 3
    $\begingroup$ Some people consider the empty set a subset. $\endgroup$ – Thomas Andrews Jan 10 '16 at 13:22
4
$\begingroup$

Yes there is a formula for the maximum number of subsets given a set of size $N$.

The formula is:

$$2^N$$

If you do not want to include the null set, then the answer would be $2^N - 1$.

If you wish to know the derivation of this formula, please see this question.

$\endgroup$
  • $\begingroup$ Thank you for your response :) $\endgroup$ – Hirboy Jan 10 '16 at 13:24
0
$\begingroup$

You know that there are $\binom n k $ subsets of $k \le n$ elements in a set of $n$. There are then subsets for $k=1,2,...,n$ and you have a total of $\sum _{k=1}^n \binom nk = (\sum _{k=0}^n \binom nk) -1$ subsets. The second sum (except for -1) is the Newton's formula for $(1+1)^n$. You have then a total of $2^n -1$ subsets.

$\endgroup$
0
$\begingroup$

You are right. Take it like this. You have $n$ items of course. You can't select $0$ items so now we have to choose $$(1,2,...n)$$ elements so we have $$\sum_{k = 0}^n {n\choose k}$$ Now we know $$\sum_{k = 0}^n {n\choose k}=2^n$$ but as stated above we can't choose $0$ elements so it becomes $$\sum_{k = 1}^{n} {n\choose k}=2^n-1$$ as ${n\choose 0}=1$ and we are done.

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