# How many combinations of coins add up to \$20 We have four coins • Coin 1: $$0.10$$ • Coin 2:$1.00

• Coin 3: $$1.00$$

• Coin 4: $1.00 How many ways can we get$20.00 from these coins?

My attempt:

I started by counting the total number of ways for each coin to reach $20.00 • 200 ways for coin 1 • 20 ways for coins 2, 3, and 4. I now have an equation, a + b + c + d + e = 200 We want to get the total number of solutions without any constraints $$\dbinom{200+5-1}{5-1} = \dbinom{204}{4}$$ Then I found the number of solutions with the constraint that the coin must be $$\leq$$ 20. The total number of solutions with coin > 20 can be determined by purchasing 21 coins and leaving 181 at most to buy. $$\dbinom{181+5-1}{5-1} = \dbinom{185}{4}$$ The final solution is: $$\dbinom{204}{4} - 3 \times \dbinom{185}{4}$$ • If only four coins, why five vars a,b,c,d,e? Dec 6 '18 at 18:20 • 'e' represents the difference between 200 and the number of coins purchased. Dec 6 '18 at 18:21 • I don't understand what you mean by$200$ways for coin 1. If the twenty dollars consists solely of coins of type 1, there will be$200$of them, but that's only one way, isn't it? In fact the number of coins of type 1 bust be a multiply of$10$, so there are only$21$choices for the number of coins of type 1. Dec 6 '18 at 18:29 • @saulspatz I thought I could solve the problem using constraints. I wanted to take the total number of options, then remove the smaller constraints from that total. Dec 6 '18 at 18:37 ## 1 Answer There should be a multiple of 10 number of coins of type $$1$$. Hence, in effect we have four types of coin of \$ $$1$$ and desire non-negative solutions to the equation $$x_1+x_2+x_3+x_4=20$$, which by the stars and bars problem is $$\binom{23}{3}$$.

• Very neat. I went through adding up the the stars and bars answer if there are $10k$ coins of type $1$, for $k=0,1,\dots,20$ and eventually ended up with ${23\choose3},$ but it never clicked that I could shortcut all that. Dec 6 '18 at 19:15
• Thanks, @saulspatz. Dec 6 '18 at 19:51