Number of Subsets In a Set

The number of subsets for a set of n elements is \(2^n\).

Let's say we have a set of n things and we want to know how many different ways we can pick subsets of those things (including all of them or none of them). If we have three things, for instance, we might pick only the first item, or the first and the last item, or only the second item, etc.

We can represent the items as boxes in a row and if an item is in the subset we put a one in its box and if it isn't then we put a zero there. So for the three item example we can represent the subset that has the first and third item as 101 (the boxes are invisible and elastic). Writing it this way we can think of each element of the set as a binary digit and the number of subsets you can create is the same as the number of binary numbers with the same number of digits as the elements in our set.

To see all the possible subsets you can write out the binary numbers. For the case of three elements we represent them as three digits so finding the subsets will be the equivalent of counting from 0 to 7 in binary.

	Item 1	Item 2	Item 3
0	0	0	0
1	0	0	1
2	0	1	0
3	0	1	1
4	1	0	0
5	1	0	1
6	1	1	0
7	1	1	1

In this case we get 8 possibilities. More generally, for n digits we can count from \(0\) to \(2^n - 1\) for a total of \(2^n\) numbers so the total number of subsets of a set with n elements is \(2^n\).