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$ 13 Answers
$\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$ 1 $\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$ $\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$
