<s>[INST] 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.
 [/INST] 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$.
</s>