# Combinatorics Problem with Coins

Am I on the right path with this?

A large pile of coins consists of pennies, nickels, dimes, and quarters.

a. How many different collections of $$30$$ coins can be chosen if there are at least $$30$$ of each kind of coin?

Answer- I got $$\binom{n}{k} = \dfrac{30+4-1!}{(30!)(33-30!)}$$

b. If the pile contains only $$15$$ quarters but at least $$30$$ of each other kind of coin, how many collections of $$30$$ coins can be chosen?

Answer - For this one I pretty much took the combination above and subtracted the case for the combinations possible if $$15$$ quarters are accounted for. This I found to be $$\dfrac{15+4-1!}{(15!)(18-15!)}$$ subtracted from $$\dfrac{30+4-1!}{(30!)(33-30!)}$$.

• Putting "n\choose k" inside dollar signs produces $n\choose k$. – Barry Cipra Nov 18 '18 at 12:58
• Type $\binom{n}{k}$ to produce $\binom{n}{k}$. – N. F. Taussig Nov 18 '18 at 14:44

A large pile of coins consists of pennies, nickels, dimes, and quarters. How many different collections of coins can be formed if there are at least $$30$$ of each type of coin?

If we let $$p$$, $$n$$, $$d$$, and $$q$$ denote, respectively, the number of pennies, nickels, dimes, and quarters contained in the collection, then $$p + n + d + q = 30 \tag{1}$$ A particular solution equation 1 corresponds to the placement of three addition signs in a row of $$30$$ ones. For instance, $$+ 1 1 1 1 1 + 1 1 1 1 1 1 1 1 1 1 + 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1$$ corresponds to the solution $$p = 0$$, $$n = 5$$, $$d = 10$$, and $$q = 15$$. The number of such solutions is the number of ways we can place three addition signs in a row of thirty ones, which is $$\binom{30 + 4 - 1}{4 - 1} = \binom{33}{3} = \binom{33}{30} = \frac{33!}{30!3!}$$ since we must choose which three of the thirty-three positions required for thirty ones and three addition signs will be filled with addition signs or, equivalently, which thirty of the thirty-three positions positions required for thirty ones and three addition signs will be filled with ones.

This appears to be what you had in mind. However, you did not use parentheses correctly in your answer.
$$\binom{30 + 4 - 1}{30} = \frac{(30 + 4 - 1)!}{30!(4 - 1)!} = \frac{33!}{30!3!}$$

If the pile contains only $$15$$ quarters but at least $$30$$ of each of the other types of coins, how many collections of $$30$$ coins can be chosen?

We must subtract those collections which include at least $$16$$ quarters from the total. Suppose $$q \geq 16$$. Then $$q' = q - 16$$ is a nonnegative integer. Substituting $$q' + 16$$ for $$q$$ in equation 1 yields \begin{align*} p + n + d + q' + 16 & = 30\\ p + n + d + q' & = 14 \tag{2} \end{align*} Equation 2 is an equation in the nonnegative integers with $$\binom{14 + 4 - 1}{4 - 1} = \binom{17}{3}$$ solutions.

Hence, the number of collections of $$30$$ coins that can be formed with at most $$15$$ quarters is $$\binom{33}{3} - \binom{17}{3}$$

• Thank you! That makes sense that you chose the case which includes the collection with 16 quarters too. I have a question. If we get a hypothetical case where we have 15 quarters and 16 nickles and still have to get 30 coins from the 4 respective piles, do we just subtract the case if we were to have 16 quarters and also subtract the case if we were to have 17 nickles from the original case? – Noob Coder Nov 18 '18 at 22:38
• @NoobCoder That is correct. – N. F. Taussig Nov 18 '18 at 23:17

Your answer is correct. The way to solve this is to think of the problem as this: Imagine you have to pick one by one coins from a bag with 4 different types (pennies, nickels dimes, and quarters). After you pick one, you put it back, and repeat 30 times. You keep repeating this until you exhausted all the possible combinations. In other words, this is the same as sampling with replacement where the order does not matter. For this you can use Bose-Einstein $$\binom{n + k - 1}{ n}$$ In your case, n is 30, k is 4.