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

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

Thus: $$\sum_{X \subseteq A}|X| = \sum_{k=0}^{|A|} k{|A| \choose k} = \sum_{k=1}^{|A|} |A|{|A|-1 \choose k-1} = |A|\sum_{k=0}^{|A|-1} {|A|-1 \choose k} = |A| 2^{|A|-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.

Yet another way, a manipulation of summations without binomial coefficients:

$$\begin{align*} \sum_{A\subseteq S}|A|&=\sum_{A\subseteq S}\sum_{x\in A}1\\ &\overset{(1)}=\sum_{x\in S}\sum_{A\subseteq S\text{ s.t. }x\in A}1\\ &\overset{(2)}=\sum_{x\in S}2^{|S|-1}\\ &=|S|2^{|S|-1} \end{align*}$$

Step $(1)$ is just reversing the order of summation, and step $(2)$ uses the fact that each $x\in S$ is in half of the subsets of $S$, one for each subset of $S\setminus\{x\}$.

This is really just a computational version of the basic idea of Mike F’s combinatorial argument.

For finite sets, it's easy to derive this formula by induction.

Let $n_k$ denote the sum of the cardinalities of all the subsets of a $k$-element set. Clearly, $n_0 = 0$, since the only subset of an empty set is empty. Now, let $S$ be a $k-1$ element set, and consider what happens when we add one more element $x$ to $S$ to obtain the $k$ -element set $S' = S \cup \{x\}$.

Clearly, the subsets of $S'$ can be divided into two groups of equal size: those that contain $x$, and those that don't. The subsets of $S'$ that do not contain $x$ are exactly the subsets of $S$, and so the sum of their cardinalities is $n_{k-1}$.

The subsets of $S$ that do contain $x$, meanwhile, can be mapped one-to-one onto those that don't, simply by removing $x$ from them, with each subset containing exactly one more element (namely $x$) more than the corresponding $x$-less subset. Thus, the sum of their cardinalities equals $n_{k-1} + m_k$, where $m_k = |P(S)| = 2^{k-1}$ is the number of subsets of $S$ (and thus also the number of subsets of $S'$ that contain $x$).

Thus, the total sum of the cardinalities of the subsets of $S'$ is $n_k = 2n_{k-1} + 2^{k-1}$. Noting that:

\begin{eqnarray} n_1 &=& 2 n_0 + 2^0 &=& 0 + 1 &=& 1 &=& 1 \cdot 2^0, \\ n_2 &=& 2 n_1 + 2^1 &=& 2 + 2 &=& 4 &=& 2 \cdot 2^1, \\ n_3 &=& 2 n_2 + 2^2 &=& 8 + 4 &=& 12 &=& 3 \cdot 2^2, \\ n_4 &=& 2 n_3 + 2^3 &=& 24 + 8 &=& 32 &=& 4 \cdot 2^3, \\ n_5 &=& 2 n_4 + 2^4 &=& 64 + 16 &=& 80 &=& 5 \cdot 2^4, \\ \end{eqnarray}

we may observe a pattern, and guess that a closed-form solution would be $n_k = k \, 2^{k-1}$.

We can then easily verify that this guess indeed satisfies the recurrence we derived above: if $n_{k-1} = (k-1)2^{k-2}$, then $n_k = 2(k-1)2^{k-2} + 2^{k-1} = k \, 2^{k-1}$.

Let $n$ be the cardinality of your set. We have to calculate $\sum \binom n k k$. Since $\binom n k=\binom n {n - k}$, we can pair off the terms of this sum like: $\binom n k k + \binom n {n - k} (n - k)=\binom n k n$. When $n$ is even we also get the extra term $\binom n {n/2}\frac n 2$. Thus, for odd n:

$$\sum_{k=0}^n \binom n k k = n \sum_{k=0}^{n/2} \binom n k=n\frac 1 2\sum_{k=0}^n\binom n k=n2^{n-1}$$

For even $n$ we have essentially the same calculation, except that there's the extra $\binom n {n/2} \frac n 2$ term in the second step.

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*}$$

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.

For the subsets of size $k$ one needs the number of ways how to draw $k$ distinguishable elements from $\lvert S \rvert$ available, which is given by the binomial coefficient. This is multiplied by the number of elements, thus $k$, and summed up over all possibilites: $$ \sum_{A \in 2^S} \lvert A \rvert = \sum_{k=0}^{\lvert S \rvert} \binom{\lvert S \rvert}{k} k $$ For your example: $$ \sum_{A \in 2^S} \lvert A \rvert = \sum_{k=0}^3 \binom{3}{k} k = 1 \cdot 0 + 3 \cdot 1 + 3 \cdot 2 + 1 \cdot 3 = 0 + 3 + 6 + 3 = 12 $$ Setting $$ s(n) = \sum_{k=0}^n \binom{n}{k} k $$ we have \begin{align} s(n+1) &= \sum_{k=0}^{n+1}\binom{n+1}{k} k \\ &= \sum_{k=1}^{n+1}\binom{n+1}{k} k \\ &= \sum_{k=1}^{n+1}\frac{(n+1)!}{k!(n+1-k)!} k \\ &= \sum_{k=1}^{n+1}\frac{(n+1)!}{(k-1)!(n-(k-1))!} \\ &= (n+1) \sum_{k=1}^{n+1} \binom{n}{k-1} \\ &= (n+1) \sum_{k=0}^n \binom{n}{k} \\ &= (n+1) \sum_{k=0}^n \binom{n}{k} 1^k \cdot 1^{n-k} \\ &= (n+1) (1+1)^n \\ &= (n+1) 2^n \end{align} This gives $s(0) = 0$ and $s(n) = n 2^{n-1}$ for $n \ge 1$ and $$ \sum_{A \in 2^S} \lvert A \rvert = \lvert S \rvert \, 2^{\lvert S \rvert - 1} $$

For your example this would mean $s(3) = 3 \cdot 2^2 = 3 \cdot 4 = 12$.

There are three things you can do to find the pattern (and, knowing the answer, the first two will work for this problem):

1. Work out MORE examples than just one. It's hard to find a pattern in one number.
2. Write out the prime factorizations of the numbers.
3. Write down the difference of every two consecutive terms and see if there is a pattern there.