# How many subsets can be made with a set of $N$ items?

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.

• Some people consider the empty set a subset. – Thomas Andrews Jan 10 '16 at 13:22

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.

• Thank you for your response :) – Hirboy Jan 10 '16 at 13:24

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.

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.