How to calculate the number of elements in all subsets of a set

Question

There are $2^N$ subsets of a set.

For instance the set $\{ 1, 2 \}$ has the following subsets: $\{ \}$ $\{ 2 \}$ $\{ 1 \}$ $\{ 1, 2 \}$

I'm trying to calculate the total number of elements in all of the subsets. In the above example, it would be $4$:

$\{ 2 \}$ has one element, $\{ 1 \}$ has one element and $\{ 1, 2 \}$ has two elements, giving us $4$.

Is there a generic equation that could calculate this for me?

Answer 1

Well, let's work it out. I assume, here, that you're dealing with a finite set $A$ of cardinality $n.$ For each integer $k$ with $0\le k\le n,$ there are $$\binom{n}{k}=\frac{n!}{k!(n-k)!}$$ subsets of $A$ of cardinality $k$. Thus, one formula that would work is $$\sum_{k=0}^nk\binom{n}{k}.$$ However, that's not very revealing. Let's see if we can work out a closed form.

Calculating this number explicitly for small $n$ suggests that the closed form would be $$\sum_{k=0}^nk\binom{n}{k}=n2^{n-1},$$ and indeed, we can prove this to be the case fairly easily by using the following facts: $$n\binom{n-1}{k-1}=k\binom{n}{k},$$ $$\binom{x}{-1}=0$$ for all $x,$ and $$2^m=\sum_{k=0}^m\binom{m}{k}$$ for all integers $m\ge 0.$ See if you can take it from there on your own. If you get stuck, or if you just want to bounce your reasoning off of someone, let me know!

---

Another (more direct) way to see this is to note that, for any given element $x$ of $A,$ there are $2^{n-1}$ subsets of $A$ having $x$ as an element. Thus, there are $2^{n-1}$ occurrences of $x$ as an element, and since there are $n$ such $x,$ then we obtain $n2^{n-1},$ as desired.

Answer 2

It will be $\sum_{k=1}^N k \binom{N}{k}$, since $\binom{N}{k}$ is counting the subsets with $k$ elements.

We can use the binomial formula $(1+x)^N=\sum_{k=0}^N \binom{N}{k}x^k$. Let's differentiate both sides and we get $N(1+x)^{N-1}=\sum_{k=0}^N k \binom {N}{k}x^{k-1}$

Now if we substitute $x=1$ we get $N 2^{N-1}=\sum_{k=0}^N k\binom{N}{k}=\sum_{k=1}^N k \binom{N}{k}$

Answer 3

Let $A=\{a_1,a_2,\dots,a_N\}$. For $i\in\{1,2,\dots,N\}$ and subset $B$ of $A$. We either have $a_i\in B$ or $a_i\notin B$. There are two possibilities for each $i$. So there are totally $2^N$ possibilities. $A$ has $2^N$ subsets.

For each $a_i$, there are $2^N\div2=2^{N-1}$ subsets of $A$ containing it. As there are $N$ values of $i$, the total number of elements of all the subsets of $A$ is $N\cdot2^{N-1}$.