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

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?

• I got $36$ as coefficient of $x^{100}$ so you were right... $$\ldots + 30 x^{98}+30 x^{99}+36 x^{100}+35 x^{101}+35 x^{102}+35 x^{103}+\ldots$$ – Raffaele Oct 20 '17 at 21:10
• @Raffaele : You should get $36$ for every coefficient from $x^{100}$ to $x^{109}$. – Eric Towers Oct 20 '17 at 21:18
• Calculating the 100th derivative is definitely harder than writing the solutions one by one. An idea is to use partial fraction decomposition on $\frac{1}{(1-x)(1-x^{10})(1-x^{20})}$ and then sum the coefficients in front of $x^{100}$. But this can be rather tedious and hard to do too. – Stefan4024 Oct 20 '17 at 21:20
• The first time I used polynomial with a degree too low. I remade my calculations with higher degree polynomials (using Mathematica) and finally got $$\ldots+42 x^{111}+42 x^{110}+36 x^{109}+36 x^{108}+36 x^{107}+36 x^{106}+36 x^{105}+36 x^{104}+36 x^{103}+36 x^{102}+36 x^{101}+36 x^{100}+30 x^{99}+\ldots$$ BTW, I did not know this combinatorial trick :) – Raffaele Oct 20 '17 at 21:31

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.

• Nifty! Thanks for that argument. I was able to reduce it as well after reading up on the subject, but I quite like your closing argument to take $b + 2c \le 10$ and check the number of options for each $b$ at fixed $c$ – infinitylord Oct 20 '17 at 22:32
• Thanks. Although sadly(?) not using generating functions. With a little extension you can see that the same answer also applies to target values from $101$ to $109$ (using $a' = (a-r)/10$). – Joffan Oct 20 '17 at 22:39
• Slight generalization: For $x,y,z$ non-negative integers, the number of solutions to $x + by + cz = d$ where $b|c$, and $c|d$ is $(\frac{d}{2b} + 1)^2$ – infinitylord Oct 21 '17 at 2:08

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.