Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 9 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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