Coin change with fixed denominations with duplicate values

Question

Suppose I have $\{1, 1\} \{2, 2, 2\} \{5\} \{10\}$ coins.

How many ways I can get 15 by adding coins?

If I use DP then it counts 7, because $\{1+2+2+10\} \{1+2+2+10\} \{1+2+2+10\} \{1+2+2+10\} \{1+2+2+10\} \{1+2+2+10\}$ and $\{10 + 5\}$. But actual result is $\{1+2+2+10\}$ and $\{10 + 5\}$. How do I solve efficiently?

Now I able to figure out the solution. I have to find integral solutions of equation $x+2y+5z+10m=15$ with constraints $x <= 2$, $y <= 3$, $z <= 1$ and $m <= 1$. Now how to do that?

Answer 1

This is a supplement to the already given answer showing that calculating the coefficient is not that cumbersome. We use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ in a polynomial.

We obtain \begin{align*} \color{blue}{[x^{15}]}&\color{blue}{(1+x+x^2)(1+x^2+x^4+x^6)(1+x^5)(1+x^{10})}\\ &=[x^{15}](1+x^5+x^{10}+x^{15})(1+x+x^2)(1+x^2+x^4+x^6)\tag{1}\\ &=\left([x^{15}]+[x^{10}]+[x^5]+[x^0]\right)(1+x+x^2)(1+x^2+x^4+x^6)\tag{2}\\ &=\left([x^5]+[x^0]\right)(\color{blue}{1}+x+x^2)(\color{blue}{1}+x^2+x^4+x^6)\tag{3}\\ &=1+[x^5](1+\color{blue}{x}+x^2)(1+x^2+\color{blue}{x^4}+x^6)\tag{4}\\ &=1+1\tag{5}\\ &\,\,\color{blue}{=2} \end{align*}

Comment:

• In (1) we multiply out the terms with the highest powers which is convenient as we will see in step (3).

• In (2) we use the linearity of the coefficient of operator and apply the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$.

• In (3) we can skip $[x^{15}]$ and $[x^{10}]$ since they do not contribute as the highest power of $x$ is $8$.

• In (4) we select the coefficient of $x^0$.

• In (5) we select the coefficient of $x^5$.

Answer 2

The generating function for the number of solutions in integers to $$x_1 + 2x_2 + 5 x_3 + 10 x_4 = r$$ subject to $0 \le x_1 \le 2$, $0 \le x_2 \le 3$, $0 \le x_3 \le 1$ and $0 \le x_4 \le 1$ is $$f(x) = (1+x+x^2)(1+x^2+x^4+x^6)(1+x^5)(1+x^{10})$$ The answer to your problem is the coefficient of $x^{15}$ when this polynomial is expanded, which is $2$. I used a computer algebra system for the expansion. Expanding the polynomial by hand is possible, but tedious unless you can find a shortcut.

Another approach is to observe that using only coins of denomination 1, 2, or 5, the largest amount you can make is 13, so you must use one coin of denomination 10 if the total is to be 15. That leaves an amount of 5 to be made up from coins of denomination 1, 2, or 5. There aren't many cases to consider, and you can probably see that the only possibilities are 5 and 1+2+2.