Sum of cardinals of all intersections: elegant alternative proofs? I once read the following problem: compute
$$\sum_{A,B\in\mathcal{P}(\Omega)}\operatorname{card}(A\cap B)$$
where $\Omega$ is a set of cardinal $n>0$ and $\mathcal{P}(\Omega)$ the set of the sets of $\Omega$.
At that time, I managed to prove that the sum was equal to $n\,2^{2(n-1)}$ with multiple inductions, which was very tedious.
Some time ago, someone showed a very efficient proof using the indicator function: $$\operatorname{card}(A)=\sum_{\omega\in\Omega} 1_A(\omega)$$
Then,
\begin{align}\sum_{A,B\in\mathcal{P}(\Omega)}\operatorname{card}(A\cap B)&=\sum_{A,B\in\mathcal{P}(\Omega)}\sum_{\omega\in\Omega} 1_A(\omega)1_B(\omega)= \sum_{\omega\in\Omega}\sum_{B\in \mathcal{P}(\Omega)} 1_B(\omega)\Big(\sum_{A\in\mathcal{P}(\Omega)}1_A(\omega)\Big) \\
&=\sum_{\omega\in\Omega} \sum_B 1_B(\omega) 2^{n-1} = \sum_{\omega\in\Omega} 2^{2(n-1)}=n\,2^{2(n-1)}
\end{align}
I think it is hard to beat this proof (in terms of length), but I am curious if anyone here would end up with another proof.
 A: Here's a more complicated proof that I think is pretty neat.  Given a subset $C\subseteq\Omega$, let's count the number of pairs $(A,B)$ such that $A\cap B=C$.  Equivalently, we can count the number of pairs $(A',B')$ of subsets of $\Omega\setminus C$ such that $A'\cap B'=\emptyset$ and then set $A=A'\cup C$ and $B=B'\cup C$.  Now note that there are $3^{n-|C|}$ such pairs, since such a pair is equivalent to an ordered partition of $\Omega\setminus C$ into three sets $A'$, $B'$, and $\Omega\setminus(A'\cup B'\cup C)$.
So we have learned that $$\sum_{A,B\in\mathcal{P}(\Omega)}\operatorname{card}(A\cap B)=\sum_{C\in P(\Omega)}\sum_{A\cap B=C}|C|=\sum_{C\in P(\Omega)}3^{n-|C|}|C|=\sum_{k=0}^n\binom{n}{k}k3^{n-k}.$$
Setting $j=n-k$, we can rewrite this as $$\sum_{j=0}^n\binom{n}{j}(n-j)3^{j}=n\sum_{j=0}^n\binom{n}{j}3^j-\sum_{j=0}^n\binom{n}{j}j3^{j}.$$
By the binomial theorem, the first term is $n(3+1)^n=n4^n$.  To compute the second term, consider the function $$f(x)=(x+1)^n=\sum_{j=0}^n\binom{n}{j} x^j.$$
Differentiating, we find $$f'(x)=n(x+1)^{n-1}=\sum_{j=0}^n\binom{n}{j}j x^{j-1}$$
and so $$xf'(x)=nx(x+1)^{n-1}=\sum_{j=0}^n\binom{n}{j}j x^j.$$
Plugging in $x=3$, we see that the second term we had above is $3n4^{n-1}$.  Putting it all together, we find $$\sum_{A,B\in\mathcal{P}(\Omega)}\operatorname{card}(A\cap B)=n4^n-3n4^{n-1}=n4^{n-1}(4-3)=n4^{n-1}.$$
A: I’d have expressed essentially the same idea verbally:
In that sum each $\omega\in\Omega$ gets counted once for each pair $\langle A,B\rangle\in\Omega\times\Omega$ such that $\omega\in A\cap B$. There are $2^{n-1}$ sets $A\subseteq\Omega$ such that $\omega\in A$, so there are $2^{2(n-1)}$ such pairs. Thus, each of the $n$ elements of $\Omega$ gets counted $2^{2(n-1)}$ times, for a total count of $n2^{2(n-1)}$.
