# Compute the number of different sums that can be created by adding the elements of a set

Example set {9, 6}. I am creating multisets of cardinality 3 out of its elements, for example, {9, 9, 6}. How do I compute the number of different sums that can be created by adding the elements of all possible multisets of cardinality 3?

-
Isn't it just the cardinality of the starting set raised to the cardinality of the tuple? –  Ｊ. Ｍ. Dec 20 '11 at 8:39
I think he's looking for the set of possible linear combinations with natural ($0$?) coefficients. Or the possible sums you can make by said linear combinations. –  Arthur Dec 20 '11 at 8:42
The sum $X_i=3(6+i)$, where $i$ is the number of nines chosen ($0 \leq i \leq 3$). Thus there are four possible sums. So, how do we generalize this? –  bgins Dec 20 '11 at 8:57
The general problem appears to be hard. This example is easy, because each possible sum can be constructed in only one way, but if you start with the set $\{1,2,3\}$, for instance, the multisets $\{\{1,2,3\}\}$ and $\{\{2,2,2\}\}$ have the same sum. –  Brian M. Scott Dec 20 '11 at 9:04
I've found a formula for computing the number of different multisets. The number of different sums can't be bigger than the number of different multisets, so I have an upper bound :) –  hidarikani Dec 20 '11 at 9:33

There are not too many possibilities for the multisets, so just computing them all isn't that much work. But maybe it is more satisfying to have a general solution.

Suppose we are creating multisets of size $n$ out of the elements of $\{6, 9 \}$. Let $k$ be the amount of times the number $6$ appears in the multiset. This number uniquely determines a multiset, and since $0 \leq k \leq n$, there are $n+1$ different multisets. Then the sum of the elements in a multiset is of the form $6k + 9(n-k) = 9n - 3k$. You can see that this sum is an injective function on $k$, and thus each multiset gives a different sum. This shows that the number of different sums is the amount of multisets, $n+1$.

-
Your answer works for {6,9} but not for {1,2,3} because {{1,2,3}} and {{2,2,2}} have equal sums. –  hidarikani Dec 20 '11 at 15:08
@hidarikani: That is correct. I thought you were only interested in this example, the cases with larger sets are more difficult. –  Mikko Korhonen Dec 20 '11 at 16:35
Since no one else replied I'm assuming that the only solution of the general problem is brute-force-search. –  hidarikani Dec 20 '11 at 19:57
Given $A=\{a_1,\dots,a_n\}\subset\mathbb{Z}^+$ where the $a_k$ are distinct, define $$G(x,y) =\prod_{k=1}^{n}(1+x^{a_k}y) =\sum_{m=0}^{n}G_m(x)y^m \qquad\text{and}\qquad G_m(x)=\sum_{s \geq 0}g_{ms}x^s$$ where $G(x,y)\in\mathbb{N}[x,y]$, $G_m(x)\in\mathbb{N}[x]$ and $g_{ms}\in\mathbb{N}$, and note first that the coefficient of $x^sy^m$ in $G(x,y)$ is the number of multisets on $A$ of size $m$ having sum $s$. Next, note that the coefficient $g_{ms}$ of each monomial $x^s$ in $G_m(x)$ counts the number of ways of obtaining the sum $s$ from a multiset of size $m$ (counting multiplicity).
What we want to know, however, is the number of distinct sums $s$ "reachable" by multisets of size $m$. But this is just the number of nonzero coefficients (or of distinct monomials) of $G_m$.
See also Richard Stanley's list of bijective proof problems, particulary problems 2, 24, 25 & 30 for instance, or consider what would happen if we knew that $a_1<\dots<a_n$ and that $\frac{a_{k+1}-a_k}{a_k-a_{k-1}} \geq b$ for some $b>1$ and all $1<k<n$, to gain a better intuition on the matter.