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?
Compute the number of different sums that can be created by adding the elements of a set
-
0I've found a [formula](http://en.wikipedia.org/wiki/Multiset#Counting_multisets) 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 :) – 2011-12-20
2 Answers
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$.
-
0Since no one else replied I'm assuming that the only solution of the general problem is brute-force-search. – 2011-12-20
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