Question

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.

Answer 1

That formula is right, but there is a much shorter formula for the number of elements in the power set of an n-element set.

If write out the power sets for sets with 2, 3 and 4 elements, it should become clear what the shorter formula is.

Answer 2

Yeah I know. The formula is \(2^n\)

Answer 3

I'm ashamed this is actually the binomial theorem

Answer 4

the binomial expansion of \((x+y)^n\) is \[\Large (x+y)^n=\sum_{k=0}^n \left(\begin{matrix}n \\ k\end{matrix}\right)x^ky^{n-k}\]
put \(x=y=1\) and you'll get the answer to your question.

Answer 5

\[\#\wp S=2^{\#S}= \sum_{k=0}^{n} {n\choose k}\]

Answer 6

thank you @sirm3d

Answer 7

YW