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
-
0Isn't it just the cardinality of the starting set raised to the cardinality of the tuple? – 2011-12-20
-
0I 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. – 2011-12-20
-
0The 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? – 2011-12-20
-
1The 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. – 2011-12-20
-
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$.
-
0Your answer works for {6,9} but not for {1,2,3} because {{1,2,3}} and {{2,2,2}} have equal sums. – 2011-12-20
-
0@hidarikani: That is correct. I thought you were only interested in this example, the cases with larger sets are more difficult. – 2011-12-20
-
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