# How to count solutions to a linear Diophantine equation?

I have the following linear Diophantine equation.

$a+5b+20c+50d+100e+200f=300$

I wish to know the number of solutions to this equation with the constraint that $a,b,c,d,e,f \ge 0$.

What algorithms or techniques may I apply to find the number of solutions?

I've read some papers using wild ideas like Ehrhart polynomials or some wild summations of vector inner products, but they seem out of reach to my comprehension.

Please don't give me the number of solutions to the equation above, I want to work it out with your advice.

## 1 Answer

$1$. One way out is to enumerate the various possible cases starting from $f$ and proceeding to $e$ and all the way up to $a$. For instance, $f$ can be either $0$ or $1$. If $f$ is $0$, then $e$ can be either $0$, $1$, $2$ or $3$. If $f$ is $1$, then $e$ can be either $0$ or $1$. And so on.

$2$. Another way is to consider the product $$(1+x+x^2+x^3+\cdots)(1+x^5+x^{10}+x^{15}+\cdots)(1+x^{20}+x^{40}+x^{60}+\cdots)(1+x^{50}+x^{100}+x^{150}+\cdots)(1+x^{100}+x^{200}+x^{300}+\cdots)(1+x^{200}+x^{400}+x^{600}+\cdots)$$ Find the coefficient of $x^{300}$ in the above product by writing the product as $$\dfrac1{1-x} \dfrac1{1-x^5} \dfrac1{1-x^{20}} \dfrac1{1-x^{50}} \dfrac1{1-x^{100}} \dfrac1{1-x^{200}}$$ and extracting out the $x^{300}$ term efficiently.

• I took your first advice to simplify calculations and did a brute force on the problem. I couldn't find a way of extracting a single term from the expansion on point 2. Perhaps you could illuminate me? Thank you. – Sebastian Garrido Jul 2 '13 at 3:12