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.
 A: There are $2^n$ subsets of the original set. We can pair these sets by grouping a given set with its complement (i.e. $A$, $S - A$). There are $2^n / 2 = 2^{n-1}$ such pairs and the sum of the cardinalities of each set in the pair is $n$. This gives us a total of $n2^{n-1}$.
EDIT: Also, if anyone is interested, there is a nice "story proof" of the above identity
$$ \sum_{k=0}^n k \binom{n}{k} = n2^{n-1}.$$
Suppose we want to pick a committee of any size with a president from a group of $n$ people. Two committees are distinct if the set of people that compose them are different or if they are the same but have a distinct president. We would like to count the number of distinct committees. We first can pick a committee of size $k$ with $k=0,1,2, \ldots, n$ (this happens in $\binom{n}{k}$ ways) and then select a president from the $k$ committee members. This gives the LHS of the above identity. Alternatively, we can first elect the person we want to be president (we have $n$ choices) and then pick a subset of the remaining $n-1$ people to round out his committee (there are $2^{n-1}$ choices). This gives the RHS of the above identity.
A: 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.
A: 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.
A: 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$.
A: 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}$.
A: 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.
A: 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$.
A: 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*}$$

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


*

*Work out MORE examples than just one. It's hard to find a pattern in one number.

*Write out the prime factorizations of the numbers.

*Write down the difference of every two consecutive terms and see if there is a pattern there. 

A: 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.
A: You can encode every subset of a set as a binary number. If the set has $n$ elements, then you need the binary numbers of length $n$. Position $i$ in the number is element $i$ of the original set. An element $i$ is in the subset, if you have a 1 at position $i$.
There are $2^n$ numbers of length $n$, and there are $n$ digits per number. So in all the digits of all numbers are $n*2^n$.
Now the sum of the cardinality of all subsets is just the number of 1's in all these numbers. For each binary number, you can complement each bit to get another binary number of the same length. Thus the number of 0's and 1's must be the same, or put it another way: the number of 1's must be half of the digits.
Therefore, the number of 1's is $n*2^n/2$ or $n*2^{n-1}$, and that is the number of the sum of the cardinalities.
