Number of solutions to $a + 10b + 20c = 100$ with $a,b,c$ non-negative integers

Question

How many solutions are there to the equation $$a + 10b + 20c = 100$$ where $a,b,c$ are non-negative integers

The problem I'm asking is another way of phrasing "How many ways can you break $100$ dollars into $1$, $10$, and $20$ dollar bills", or any multitude of variants.

Solutions can, for example, be $(a,b,c) = (100, 0, 0)$, $(10, 7, 1)$, $(0, 6, 2)$, etc.

I wrote a quick program which gave me a total of $36$ solutions, but I'd like to have a better understanding as to where this answer comes from without something resembling brute-force. Preferably, I'd like to see how to use generating functions to solve this, as that was the method I first tried (and failed) with.

The solution should be the coefficient of the 100th-power term in the product:

$$(1 + x + x^2 + x^3 + ...)(1 + x^{10} + x^{20} + ...)(1 + x^{20} + x^{40} + ...)$$ I can get this coefficient from the following: $$\lim_{x \to 0} \frac{1}{100!} \frac{d^{100}}{dx^{100}}(1 + x + x^2 + x^3 + ...)(1 + x^{10} + x^{20} + ...)(1 + x^{20} + x^{40} + ...)$$ For whatever reason, applying product rule fails (or I fail to use it correctly), as I get $3$. So, assuming $|x| < 1$, this equals: $$\lim_{x \to 0} \frac{1}{100!} \frac{d^{100}}{dx^{100}} \frac{1}{(1-x)(1-x^{10})(1-x^{20})}$$ However, to much dismay, this is not such a simple thing to find derivatives of. Any advice?

Answer 1

You can simplify fairly drastically, since $a = 100-10b-20c$ means $a$ must be a multiple of $10$. So setting $a' := a/10$, we have $a' + b + 2c = 10$.

Again $a'$ is determined by $b$ and $c$, so we just need $b+2c\le 10$. For $c=\{0,1,2,3,4,5\}$ we have $\{11,9,7,5,3,1\}$ options for $b$, for a total of $36$ possible combinations.

Answer 2

Er, ..., calculate carefully?

$$(1 + x + x^2 + x^3 + ...)(1 + x^{10} + x^{20} + ...)(1 + x^{20} + x^{40} + ...) \\ = \dots +30 x^{98} + 30 x^{99} + 36 x^{100} + 36 x^{101} + ...$$

---

Another way: Suppose there are $n_k$ ways to write $k$ as a non-negative integer weighted sum of $\{1,10\}$. Then the total number of ways to write $k$ as a non-negative integer weighted sum of $\{1,10,20\}$ is $N = n_0 + n_{20} + n_{40} + n_{60} + n_{80} + n_{100}$, where $n_0$ counts the number of ways we finish by adding five $20$s, $n_{20}$ the number of ways we finish by adding four $20$s, ..., and $n_{100}$ the number of ways we finish by adding no $20$s.

• Now $n_0 = 1$ because $0 \cdot 1 + 0 \cdot 10$ is the only way to write $0$ as a non-negative integer weighted sum of $\{1,10\}$.
• And $n_{20} = 3$, depending on whether there are zero, one, or two $10$s in the sum, the rest being made up with $1$s.
• And $n_{40} = 5$, for the same reason : zero to four $10$s and the remainder made of $1$s.
• Finishing, $n_{60} = 7$, $n_{80} = 9$, and $n_{100} = 11$.

Finally, $N = 1 + 3 + 5 + 7 + 9 + 11 = 36$. That the number of ways is controlled by the $10$s and $20$s, with the $1$ making up the rest, is hinted in the snippet of the series in $x$, above. There is only one way to make totals up to $9$ from $\{1,10,20\}$. There are two ways for totals in $[10,19]$, four ways in $[20,29]$, six ways in $[30,31]$, nine ways in $[40,41]$, where the increment in the number of ways in each range of ten totals increases by $1$ each time we pass a multiple of $20$ (counting that we could either include or exclude one more $20$ in our sums).

---

Another way: You don't have to multiply out the full power series. You can calculate with $$( 1 + x+ x^2 + \cdots + x^{99} + x^{100})(1 + x^{10} + \cdots + x^{100})(1+x^{20}+\cdots+x^{100})$$ always discarding any term with power greater than $100$. If you do this from right to left, you essentially perform the calculation described above.