Sum of cardinals of all intersections: elegant alternative proofs?

Question

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.

Answer 1

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)}$.

Answer 2

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