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.

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.
