1

I want to compute this sum: $$\sum_{S\,\subseteq\,Q} f\left(S\right)$$ where $Q$ is some finite set with $n$ elements. I think the first step should be: $$\sum_{i=0}^{n}\left(\sum_{S\,\subseteq\,Q\,;\,\vert S\vert\, =\,i}f\left(S\right)\right)$$

which can be useful if $f$ depends on $\vert S\vert$. Can the order of summation be interchanged?? I honestly don't know how to do it (if it can be done). The conditions $i=0,1,2,\dots,n$ and $\vert S\vert=i$ don't seem very "compatible" because there is no natural total order in $\{ \,S\subseteq Q:\vert S\vert=i\,\}$

Thanks in advance

Asaf Karagila
  • 393,674
augustoperez
  • 3,216
  • Try it with simple examples. If $Q={1,2}$ or $Q={1,2,3}$, what are the possible inner summation sets of subsets with one subset per magnitude, and do any of them look possibly useful? – aschepler Jul 01 '18 at 00:58
  • I don't quite get what you mean by interchanging the order of the summations. If we do that, we get: $$\sum_{S,\subseteq,Q,;,\vert S\vert, =,i}\left(\sum_{i=1}^{n}f\left(S\right)\right) \stackrel{()}{=} \sum_{S,\subseteq,Q,;,\vert S\vert, =,i}\left(n f(S)\right) \stackrel{(*)}{=} \phi(i)$$

    $(*)$ since the formula isn't depending on the value of $i$.

    $(**) \ \ i$ stays there as a constant of the first summation, so we get some $(\phi)$ function of $i$.

     – Daniel P Jul 01 '18 at 01:16
  • @DanielP I don't mean "literally" change the two summations, that doesn't make sense here. The answer should depend on $n$ (the size of $Q$). Try looking for related questions to see what I'm trying to do – augustoperez Jul 01 '18 at 19:18
  • @aschepler I don't think it is going to work at least in a nice way. "Organizing" the sets is probably getting harder the larger the size of $Q$ – augustoperez Jul 01 '18 at 19:24
  • The set $S$ is the variable of the function $f$? Maybe do you mean $S$ belongs to $Q$ ? – dmtri Aug 23 '18 at 13:18
  • @dmtri yes. I mean $S$ belongs to the power set of $Q$. $f(S)$ is a function like "number of elements of $S$" or "1 if $5\in S$ and 0 otherwise" – augustoperez Aug 23 '18 at 21:05

1 Answers1

1

In case the cardinality of the set $Q$ is finite and the function $f$ takes real values, then adding finite real numbers with any order , would always give the same result-sum.

dmtri
  • 3,270