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?
[Math] A set with n elements has 2^n subsets
combinatorics
combinatorics
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?
Best Answer
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$