5
$\begingroup$

Sorry in advance, as I suspect I lack both the proper terms and the proper notation for the problem I have, but I'll try to be clear.

If I have a set $S = \{1,2,3\}$, I figured out that the summation of the "subset sums" of its power set is $\sum_i S_i \times 2^{|S| - 1}$.

For instance, as $P(S) = \{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$, this sum is $0+1+2+3+3+4+5+6=24$, i.e. $6 \times 2^2$.

Now I'd like to find a formula for the related summation where instead of summing the "subset sums", I sum 2 to their power: $2^0+2^1+2^2+2^3+2^3+2^4+2^5+2^6=135$.

I tried to reverse-engineer this formula for a long time, using many examples, but it completely eludes me.. Thanks for any help or clarification!

  • 1
    Your formula for the sum is correct. The simple justification is that there are $2^{|S|}$ subsets and each element is in half of them, so the element contributes $2^{|S|-1}$ times to the sum.2012-11-15

1 Answers 1

8

Denoting your summation with $f(S)$, we have the follwoing facts: $f(\emptyset)=1$ and if $S':=S\setminus\{x\}$ for some $x\in S$, then $ f(S) = f(S')\cdot(1+2^x)$ because the subsets of $S$ can be partitioned into those not containing $x$ (giving $f(S')$) and those containing $x$ (where each sorresponding summand is multiplied by $2^x$). Therefore, one readily sees that $f(S)=\prod_{x\in S}(1+2^x).$ In your example: $(1+2^1)(1+2^2)(1+2^3)=3\cdot 5\cdot 9=135$.

  • 0
    Hm, both I guess.2012-11-15