Number of Distinct Sums of Integers Hello,
I'm new to MO. Please, bear with my inexperience. I try to be as precise as it is possible to me.
Given a multiset of integers $S$, I'm interested in the number of sub-multisets which sum up to distinct sums. I call this number $S_\sum$ and is defined as
$S_\sum = \left|\left\{ \sum_{i \in Q} i \quad \middle| \quad Q \subseteq S \right\}\right|$

EXAMPLE
$S = \{1,3,7,9\}$. Number of subsets is $2^4 = 16$, but the number of sub-multisets with distinct sums are $S_\sum = 15$, as the subsets $\{3,7\}$ and $\{1,9\}$ do add to the same number 10.

The upper bound is clearly the number of sub-multisets ($2^{|S|}$). The lower bound can be as small as $|S|+1$ (in the case of $S$ consisting of only equal numbers).
As I think, that it is difficult to come up with an exact solution, I'm looking for an estimation of the number in question if the set is chosen randomly.
The precise question:
For a randomly chosen multiset of integers $S$, how does $S_\sum$ relate in average to $|S|$ and $\sum_{i \in S} i$. 
 A: Here is a possible formulation of your question: A multiset is a list $S$ of positive integers $x_1 \le x_2 \le \cdots \le x_k.$ The size is $k=|S|$ and the total is $t=\Sigma_{x \in S}x.$ Call $S$ a $(k,t)-$multiset (which could also be called an unordered partition of $t$ into $k$ positive parts.)  There are $2^k$ sums of some all or none of the $x_i$ and, as you say, the number of distinct sums could be as high as $2^k$ ( provided that $t \ge 2^{k}-1$) and as small as $k+1$ (provided that $t$ is a multiple of $k$). 

Since the number of $(k,t)-$multisets is finite, what can be said, for fixed $k,t$, about the average number of distinct sums for a "randomly" chosen $(k,t)-$multiset.

There are still choices of what is meant by random. We could write each possible multiset on a card and pick one at random: then $13,13,13,13$ would be as likely as $3,10,13,26$ for $k,t=4,52.$ Or, you could roll a fair $4$-sided die $52$ times, see how often each face comes up and just use the multiset of those 4 counts ( you would either need to start over in the unlikely event that some count is zero or else roll $48$ times and start each count at $1$.). In this second model $5,8,13,26$ is twenty four times more likely than $13,13,13,13$
Later: You have now clarified that you are particularly interested in $(k,2^k+r)$ designs where $r$ is "small". I don't know if you are thinking about $r=3$ or $r=3k$ or $r=k^3.$ Even for $r=3$ I don't think that explicitly generating all multisets would be feasible for $k=10$ (or something like that) I can see a possible opening for impressive probability and statistics arguments by those expert in the field. It am thinking about fixing $k$ and increasing $t$ so perhaps that is not so much your interest, however maybe these thoughts would be of interest: 


*

*For $A \subseteq \{1,2,\cdots,k\}$ let $\Sigma_A=\Sigma_{i \in A}x_i.$ Perhaps you want to consider what the set $\mathcal{E}_S=\{(A,B) \mid  \Sigma_A=\Sigma_B\}$ could look like for a particular multiset $S$ of values. Certainly if $(A,B)$ is in $\mathcal{E}_S$ with $A,B$ disjoint so are  $(A \cup C,B \cup C)$  for any of the $2^{k-|A|-|B|}$ sets disjoint from both. That is a special case of $(A \cup A',B \cup B') \in \mathcal{E}_S$ when the unions are disjoint and $(A,B)$,$(A',B')$ both are.

*For $t \lt \binom{k+1}{2}$ there are forced to be solutions of $x_i=x_j$ (with $i \ne j$ of course) each of which leads to $2^{k-2}$ other equal sums as just commented. For $t \lt 2^k-1$ we have $\mathcal{E}_S \ne \emptyset.$

*How big must $t$ be relative to $k$ in order to have the $x_i$ distinct with probability greater than $ 1-1/k$ ( or some other $1 - \varepsilon$? ) Is it a sharp transition at some critical point?

*The comment above about the isolation lemma seems very interesting. If I read it correctly, then if we take $t=mk$ then the least of the $x_i$ is unique of its value with probability exceeding $1-1/m.$ If we take that singleton set out of consideration then the next smallest is again unique of its weight with probability exceeding $1-1/m$ etc. So the expected number of distinct $x_i$ is at least $(1-1/m)k.$ 

*How much larger (I'd guess quite a bit larger) does $t$ have to be in order to make it unlikely that there would be any cases of $x_i+x_j=x_k+x_{\ell}$? The same question if we ask that instead (or in addition) we are unlikely to see $x_i+x_j=x_k?.$ Again the isolation lemma says that for any given partition of the index set $\{1,\cdots,k\}$ or merely family $F$ of subsets of the index set, the $A \in F$ which minimizes $\Sigma_A$ is the only one of its weight with probability exceeding $1-1/m.$ (So it makes sense to restrict $F$ to at least have no member contain any other.)
Well maybe that is far enough with questions I can't answer. 
