1

I need to calculate the sum $\sum_{A,B \subset X} |A \cup B|$ for $|X|=n$

Well I guess we can think of $X=\{1,...,n\}$.

Well, in my opinion this is basically this.

$\sum_{k=1}^n {{n}\choose{k}}*2^{k-1}$, because first we choose which elements appear in the sum $A \cup B$ and then we find $2^k$ subsets that fullfill this. We divide it by two because we counted each subset twice (one for $B$ and one for $A$).

And this sum can be easily deciphered using annihilators or generating functions.

Is my reasoning correct?

Arek Krawczyk
  • 2,114
  • 1
    sounds correct to me – gt6989b Feb 07 '14 at 16:33
  • 1
    For each element in $|A\cup B|$ you have three options, it can belong only to $A$, only to $B$ or to both of them. Maybe your $2^k$ should be $3^k$. Also you need to multiply by $k$ because $|A\cup B|$ has $k$ elements. – Quimey Feb 07 '14 at 16:46

1 Answers1

1

An different answer (look my comment to see how you can adapt your solution): Each element $x\in X$ is counted $2^{n-1}2^n+2^n2^{n-1}-2^{n-1}2^{n-1}$ times ($x\in A + x\in B - x\in (A\cap B)$). The answer is then $n 2^{2(n-1)}(2+2-1)= 3 n 4^{n-1}$ (your formula simplifies to $(3^n-1)/2$ which is different).

Quimey
  • 3,180