What is the total sum of the cardinalities of all subsets of a set?

I'm having a hard time finding the pattern. Let's say we have a set

$$S = \{1, 2, 3\}$$

The subsets are:

$$P = \{ \{\}, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\} \}$$

And the value I'm looking for, is the sum of the cardinalities of all of these subsets. That is, for this example, $$0+1+1+1+2+2+2+3=12$$

What's the formula for this value?

I can sort of see a pattern, but I can't generalize it.

Solution 1:

Here is a bijective argument. Fix a finite set $S$. Let us count the number of pairs $(X,x)$ where $X$ is a subset of $S$ and $x \in X$. We have two ways of doing this, depending which coordinate we fix first.

First way: For each set $X$, there are $|X|$ elements $x \in X$, so the count is $\sum_{X \subseteq S} |X|$.

Second way: For each element $x \in S$, there are $2^{|S|-1}$ sets $X$ with $x \in X$. We get them all by taking the union of $\{x\}$ with an arbitrary subset of $S\setminus\{x\}$. Thus, the count is $\sum_{x \in S} 2^{|S|-1} = |S| 2^{|S|-1}$.

Since both methods count the same thing, we get $$\sum_{X \subseteq S} |X| = |S| 2^{|S|-1},$$ as in the other answers.

Solution 2:

Each time an element appears in a set, it contributes $1$ to the value you are looking for. For a given element, it appears in exactly half of the subsets, i.e. $2^{n-1}$ sets. As there are $n$ total elements, you have $$n2^{n-1}$$ as others have pointed out.

Solution 3:

Let $N=|A|$.

There is one set of cardinal $0$, there are $N$ of cardinal $1$, ${N\choose2}$ of cardinal $2$, and more generally $N \choose k$ of cardinal $k$.

Thus for $N\ge1$ : $$\sum_{X \subseteq A}|X| = \sum_{k=0}^{N} k{N \choose k} = \sum_{k=1}^{N} N{N-1 \choose k-1} = N\sum_{k=0}^{N-1} {N-1 \choose k} = N 2^{N-1}$$

This formula also applies when $N=0$.

Solution 4:

Reading the solution of Jack M made me think of another strategy which I can't help but post as a second answer, because I think it is a splendid argument :)

Recall the trick for finding the sum $1+2+\ldots+n$.

Denote the answer by $a$. We write out the sum twice, reversing order the second time \begin{align*} a &= 1+2+3 & &&\ldots +n \\ a &= n + \ldots & &&+ 3 + 2 + 1 \\ \end{align*} Each column adds to $n+1$, and there are $n$ columns, so we get $$\begin{align*} 2a = n(n+1) && \Longrightarrow && a= \frac{n(n+1)}{2} \end{align*}$$

Let $S$ be a set with $n$ elements. We want to find the sum $|A_1| + |A_2| + \ldots + |A_{2^n}|$ where $A_1,\ldots,A_{2^n}$ are all the subsets of $S$. OK, let's play the same trick again!

Denote the answer by $b$. We write out the sum twice, taking the complement of each term the second time \begin{align*} b &= |A_1|+|A_2|+|A_3| + \ldots +|A_{2^n}| \\ b &= |A_1^c|+|A_2^c|+|A_3^c| +\ldots +|A_{2^n}^c| \\ \end{align*} Each column adds to $n$ and there are $2^n$ columns so we get $$\begin{align*} 2b = n 2^n && \Rightarrow &&b = n 2^{n-1}. \end{align*}$$