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?
 A: 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$.
I think Amdeberhan and Stanley may have solved this problem
in a 2008 paper entitled Polynomial Coefficient Enumeration
-- I am thinking particularly of Lemma 4.1(a),
but (apologies) I don't have time to investigate this further.
In any case, the above formulation could be used to
create an algorithm which could be implemented
in a computer algebra system such as Sage or Mathematica
to solve special cases programmatically,
and might be an interesting exercise
(for someone with time)
to analyze its complexity.
But be forewarned, this is most likely
not the most efficient solution.
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. 
A: 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$.
