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.

$\endgroup$
9
$\begingroup$

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$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.