4
$\begingroup$

I was enumerating the elements of the power set of this set $S:= \{1,2,3,4,5\}$ and I thought that the number of these elements could be obtained with this: $\#\wp S = 1 + \sum_{k=1}^n {n\choose k}$ where $n=\#S$

I saw that it holds for this set. But I'm not sure what if it could be applied to a different kind of set.

1 Answers 1

9

Well, of course the equation you state is valid. You are counting all subsets of a given cardinality $k < n$ and summing them up. Actually, you can include the $1$ in the sum taking the index from $k=0$ (combinations of $n$ in $0$ is $1$, corresponding to the empty set).

And, by the way, that sum is $2^n$, for any set of cardinality $n$. That is, the cardinality of the power set is $2^n$. One way you can relate that sum to this result is immediately with the Binomial Theorem (expanding $(1+1)^n$).