What is the reason for this answer on this coin problem?

Question

Question: How many ways are there to pick a collection of 15 coins from bags of pennies, nickels, dimes, and quarters? (Assume coins of the same denomination are indistinguishable.)

I know the answer is (4 choose 15).

I'm just having a hard time understanding WHY. Can anyone give me a detailed explanation to improve my understanding of the problem?

Answer 1

Here's some intuition:

Suppose you have 15 coins as follows:

O O O O O O O O O O O O O O O O

How many ways can you divide up these 15 coins into 4 different categories of coins? For instance:

O | O O | O O O O O O O O O | O O O

(Pennies | Nickels | Dimes | Quarters)

Hope this is helpful, let me know if you need another hint :)

Answer 2

Here is one way to count the number of possibilities. Suppose you only had pennies to work with then there is only one way. Now if you have pennies and nickels, then there can be (1 penny, 14 nickels) or (2 pennies, 13 nickels) and so on upto (14 pennies, 1 nickel). That is there are 14 possibilities. In general, if you have $x$ coins, there are $x-1$ ways for dividing it into pennies and nickels.

Now consider pennies, nickels and dimes. We can build off our answer for pennies and nickels. One possibility is 1 dime and 14 of nickels and pennies. But number of ways of having 14 of nickels and pennies is 13. Next is 2 dimes and 13 of nickels and pennies, which will be 12. Thus, it will be the $\sum_{x=2}^{14} (x-1)$.

See if you can generalize this idea one more step.

An easier way is to see that there is a pattern here. When you have only pennies, the answer is 1. When you have pennies and nickels, the answer is linear in number of coins. When you have pennies, nickels and dimes it is quadratic. So for the full case it will cubic in the number of coins. Assume a general cubic expression $f(n)=an^3 + bn^2 + cn +d $. We know the value of $f(n)$ for small values of $n$. For example, $f(4) = 1$, $f(5) = 2$. Find $f(6), f(7)$ and then solve $a, b, c$ and $d$.

Answer 3

If one takes $p$ pennies, $n$ nickels, $d$ dimes and $q$ quarters, the requirment is $p+n+d+q=15$, $p,n,d,q\ge 0$. The number of solutions is known as the number of weak compositions of 15 into 4 parts, where ''weak'' means that parts of size 0 are allowed and ''composition'' means that the order in the sum matters (so $p=7,n=4$ is considered different to $p=4,n=7$, for example). The usual approach is to lift the ''weak'' case and to count instead the number of compositions of $p+n+d+q=19$, $p,n,d,q\ge 1$. The well-known formula for the number of compositions of $N$ into $k$ parts is $\binom{N-1}{k-1}$, see e.g. https://oeis.org/A097805, so the answer is $\binom{19-1}{4-1}=816$.