Combine different denominations to form a sum

Question

I am trying to do the Euler Project Problem 31 by hand. ( https://projecteuler.net/problem=31 )

Basically, I am asked how many ways I can form 200 pence by using the denominations 200, 100, 50, 20, 10, 5, 2 and 1.

My solution (which is not correct):

It can be realized that 5 can be formed in 4 ways:

$$ 5\\ 2+2+1\\ 2+1+1+1\\ 1+1+1+1+1 $$

Since 10 = 5+5, 10 can be formed in 4*4 ways.

Since 20 = 10+10, 20 can be formed in 4*4*4*4 = $16^2$ ways

Since 50 = 20+20+10, 50 can be formed in $16^2$ * $16^2$ * 16 = $16^5$

Since 100 = 50+50, 100 can be formed in $16^5 * 16^5$ ways

Since 200 = 100 + 100, 200 can be formed in $16^5 * 16^5 * 16^5 * 16^5$ ways

Answer: 200 can be formed in $$(16^5)^4 = 16^{20} = 1 208 925 819 614 629 174 706 176$$

However this answer is not correct. What is the correct answer, how do I find it and why is my solution wrong? Thanks in advance.

Answer 1

When you compute the ways to make $10$ you make two mistakes. First, you miss a single $10$ coin. Second, when you choose two ways to make $5$ the order doesn't matter, as $(2+2+1)+5$ is the same as $5+(2+2+1)$. If you want to make $10$ out of two $5$'s, you can do it in $4$ (both $5$'s the same)+ ${4 \choose 2}=6$ (two different $5$'s$)=10$ ways. Finally, $100$ can be five $20$'s, which you miss because they can't make two $50$'s.

Answer 2

Your assumption that you can determine the number of ways of making $10~\text{p}$ by multiplying the number of ways of obtaining $5~\text{p}$ by itself is faulty. For instance, you can obtain $10~\text{p}$ by using a $10~\text{p}$ coin or by using five $2~\text{p}$ coins. Also, as Ross Millikan pointed out, the order in which the coins are used does not matter.

Before we consider the problem you posed, let's consider a simpler problem. In how many ways can we obtain $200~\text{p}$ using only $50~\text{p}$, $100~\text{p}$, and $200~\text{p}$ coins? They are \begin{align*} 200~\text{p} & = 200~\text{p}\\ & = 100~\text{p} + 100~\text{p}\\ & = 100~\text{p} + 50~\text{p} + 50~\text{p}\\ & = 50~\text{p} + 50~\text{p} + 50~\text{p} + 50~\text{p} \end{align*} so there are four ways.

We can solve this problem using generating functions. To do so, we find the coefficient of $x^{200}$ in the expansion of the product $$(1 + x^{50} + x^{100} + x^{150} + x^{200})(1 + x^{100} + x^{200})(1 + x^{200})$$ where the terms in the first parentheses correspond to using $0, 1, 2, 3,~\text{or}~4$ $50~\text{p}$ coins, respectively; the terms in the second parentheses correspond to using $0, 1,~\text{or}~2$ $100~\text{p}$ coins, respectively; and the terms in the third parentheses correspond to using $0$ or $1$ $200~\text{p}$ coin, respectively.
\begin{align*} (1 + x^{50} & + x^{100} + x^{150} + x^{200})(1 + x^{100} + x^{200})(1 + x^{200})\\ & = (1 + x^{50} + x^{100} + x^{150} + x^{200})(1 + x^{200} + x^{100} + x^{300} + x^{200} + x^{400})\\ & = (1 + x^{50} + x^{100} + x^{150} + x^{200})(1 + x^{100} + 2x^{200} + \cdots)\\ & = 1 + x^{100} + 2x^{200} + x^{50} + x^{150} + 2x^{250} + x^{100} + x^{200} + 2x^{300}\\ & \quad + x^{150} + x^{250} + 2x^{350} + x^{200} + x^{300} + 2x^{400} + \cdots\\ & = 1 + x^{50} + 2x^{100} + 2x^{150} + \color{blue}{4}x^{200} + \cdots \end{align*} where we drop terms of degree greater than $200$ since they do not contribute to the $x^{200}$ term.

To solve the problem you are interested in, you must find the coefficient of $x^{200}$ in the expansion of $$(1 + x + x^2 + \cdots + x^{200})(1 + x^2 + x^4 + \cdots + x^{200})(1 + x^5 + x^{10} + \cdots + x^{200})(1 + x^{10} + x^{20} + \cdots + x^{200})(1 + x^{20} + x^{40} + \cdots + x^{200})(1 + x^{50} + x^{100} + x^{200})(1 + x^{100} + x^{200})(1 + x^{200})$$