# A set with n elements has 2^n subsets

I don't understand why a set with n elements has 2^n subsets. How is this calculated? I realize that {123} has empty set - 1-2-3-1,2-1,3-2,3-1,2,3 but how is the formula derived?

• For each of the sets you listed, there are two corresponding subsets of $\{1,2,3,4\}$ - one with $4$ in it, and one without. Also, you get all the subsets for $n=4$ this way. So for $n=4$ the number is double the number for $n=3$. And similarly for $n=5$, double the number for $n=4$, etc. – user180040 Oct 1 '14 at 4:53

When choosing elements to be in a subset, they are in or they are not. So each element has 2 choices available to it. If you have n elements of a set $\implies 2^n$ subsets.

In addition, the number of subsets is equal to the sum of the binomial coefficients, and it is well-known that $\sum^{n}_{k=0}\binom{n}{k}=2^n$

A n-sized set can have subsets of sizes anywhere from 0 to n. So there are: $\displaystyle \sum_{i=0}^n \binom{n}{i} = 2^n$ ways to make such subsets. Alternatively think of it as either taking or not taking each of the n elements.

If you look at functions

$$f:S\to \{0,1\}$$

you see that $f^{-1}(1)$ is a unique subset completely determined by $f$. So the number of subsets is just the number of functions from a set with $n$ elements to a set with $2$ elements, i.e. $2^n$.

The key point here is that you can select any number of elements

So to select one element we have C(n, 1) number of ways.

Similarly selecting two elements from the set can be done in C(n, 2).

..

..

..

Similarly selecting n elements from the set of n elements is C(n, n) ways.

Also you can select an empty set or a set with no elements and this can be done only in one way.

Now summing all these ways you can observe that these are summation of binomial coefficients whose sum is given by $(1+x)^ n$ where $x=1$ hence $2^n$.

Hope this helped.

Suppose your set's $n$ elements are the distinct points $x_0,x_1,\ldots,x_{n-1}$.

Think of all the $n$-digit binary numbers you can form, which will all be of the form $a_{n-1}a_{n-2}\cdots a_1a_0$, where each $a_i$ is zero or one. There are exactly $2^n$ distinct values representable by such $n$-bit numbers. That's because there are 2 choices for each bit, and $n$ bits to populate, giving a total of $\underbrace{2\cdot 2\cdot \cdots \cdot 2}_{n\textrm{ factors}}$ distinct values.

For example, if $n=2$, the binary numbers are 00, 01, 10, and 11, a total of $2^2=4$ distinct values.

Now just make a correspondence between these values and the subsets of your set by declaring the point $x_i$ to be in the subset if and only if the bit $a_i$ is one.