In how many ways you can make up 20 pence using 20p, 10p, 5p, 2p and 1p coins

Question

I would like to ask in how many ways you can make up 20 pence using 20p, 10p, 5p, 2p and 1p coins. What I was thinking is that I have counted there are 11 ways to make up 10 pence using 10p, 5p, 2p and 1p coins. So, the number of way to make up 20 pence would be $11\times 11+1=122$ (using 1 20 pence). But. the answer turns out to be wrong. May I know why? Thank you so much for you guys.

Answer 1

The problem is that this counts some combinations several times. First, you double-counted all the ways where the two ways to make 10p are different, since you can have those in either order. But it's worse than that, because there are some ways to make 20p that can be split into two halves in more than one way (for example, two 5ps and ten 1ps - the 5ps can be in the same half or different halves).

Probably the best way to do it is to compute the following:

• the number of ways to make 10p
• the number of ways to make 15p without using a 10p coin
• the number of ways to make 18p only using 2p and 1p

then add these and add $2$. This works because you are conditioning on the largest coin used, and working out how many ways to do the rest without violating that condition. (The extra $2$ cases are using one 20p and all 1ps.)