Number of different sums with k numbers from {1, 5, 10, 50}

Question

Say we have $k$ numbers, each of which belongs to the set $S = \{1, 5, 10, 50\}$ How many different sums can be created by adding these numbers?

If $k = 1$, the are four different sums. Also, if $k = 2$, there are ten: $$\begin{align} 1 + 1 = 2 \quad 1 + 5 &= 6 \quad 1 + 10 = 11 \\ 1 + 50 = 51 \quad 5 + 5 &= 10 \quad 5 + 10 = 15 \\ 5 + 50 = 55 \quad 10 + 10 &= 20 \quad 10 + 50 = 60 \\ 50 + 50 &= 100 \quad \end{align}$$

Answer 1

Imagine that we have $k$ baskets, labeled $50,\ 10,\ 5,\ 1.$ If we distribute $k$ balls into the baskets, the number of balls in each basket indicates how many summands of each value to take. The number of ways of distributing the balls can be computed with stars and bars. It is the binomial coefficient $$\binom{k+3}{3}.$$

That leaves the question of whether all the sums are actually different for a particular value of $k,$ and unfortunately, the answer is "no." For example, with $k=6,$ we have $$1\cdot50+5\cdot1=5\cdot10+1\cdot5$$ so that the stars and bars formula counts the number $55$ at least twice.

I doubt that there is a simple way to answer this question for general $k,$ because of the need to account for multiple ways of arriving at the smae sum. This is reminiscent of the subset sum problem which is known to be NP-complete.

Answer 2

At least for small values of $k$, this answer will be tractable. Your answer is the number of terms in the expansion of $(x+x^{5}+x^{10}+x^{50})^k$ which can be found using a computer algebra system.

Answer 3

We can calculate the number of solutions with some algebra. We represent multiples of $\{1,5,10,50\}$ by generating functions (in $x$) and count the number of occurrences in $y$.

We calculate the number of sums with $k$ members from $\{1,5,10,50\}$ as the coefficient of $[y^k]$ evaluated at $x=1$: \begin{align*} \left.\left([y^k]\frac{1}{1-xy}\frac{1}{1-x^5y}\frac{1}{1-x^{10}y}\frac{1}{1-x^{50}y}\right)\right|_{x=1} \end{align*}

The series starts with \begin{align*} 1&+(x+x^5+x^{10}+x^{50})y\\ &+(x^2+x^6+x^{10}+x^{11}+x^{15}+x^{20}+x^{51}+x^{55}+x^{60}+x^{100})y^2\\ &+\cdots \end{align*} which is evaluated at $x=1$ \begin{align*} \color{blue}{1}+\color{blue}{4}y+\color{blue}{10}y^2+\cdots \end{align*} and with some help of Wolfram Alpha we find in accordance with the example of @saulspatz \begin{align*} \color{blue}{[x^{55}y^6]}\frac{1}{1-xy}\frac{1}{1-x^5y}\frac{1}{1-x^{10}y}\frac{1}{1-x^{50}y}\color{blue}{=2} \end{align*}