How to find number of non negative integral solutions of $ax+by+cz= d$ ( no relation between $a,b,c,d$).

Question

My question stems from this one

Find the no. of non negative integral solutions for $x+y+3z=33$

and i did it by taking the $3z$ to the other side and thinking that z can only be one of these $\{0,1,2,...,11 \}$ and then for each one i found out how many such x and y can be .

For ex: for $z=0$ that is $x+y=33$ you can think of distributing 33 ones or $\{1,1,...\text{33 terms} \}$ between two different people , which gives $^{34}C_1$ or $34$ .

Similarly you will get the total = $$34+31+28+...1=210$$

---

That is fine but what if y had a different coefficient than x ( for example $x+2y+3z=33$ )was my actual question so I generalized the coefficients.

Answer 1

The number of nonnegative integer solutions of $ax + by + cz = d$ can be obtained as the coefficient of $X^d$ in the series expansion of $1/((1-X^a)(1-X^b)(1-X^c))$.

Alternatively, it is $F_3(d)$ where $F_3(m) = F_3(m-a) + F_2(m)$ for $m \ge a$, $F_3(m) = F_2(m)$ for $0 \le m < a$, $F_2(m) = F_2(m-b) + F_1(m)$ for $m \ge b$, $F_2(m) = F_1(m)$ for $0 \le m < b$, and $F_1(m) = 1$ if $m$ is a multiple of $c$, $0$ otherwise.

EDIT: The point about the series expansion is this. We have the geometric series formula (convergent for $|X|<1$, but convergence doesn't play any role here) $$ \dfrac{1}{1-X^a} = 1 + X^a + X^{2a} + X^{3a} + \ldots = \sum_{k=0}^\infty X^{ka}$$ and similarly for $b$ and $c$. If you expanded out $$ \dfrac{1}{(1-X^a)(1-X^b)(1-X^c)} = (1 + X^a + X^{2a}+\ldots)(1+X^b+X^{2b}+\ldots)(1+X^c+X^{2c}+\ldots)$$ you get the sum of terms $X^{ax}X^{by}X^{cz} = X^{ax+by+cz}$ for all nonnegative integers $x,y,z$. You get an $X^n$ for each triple $(x,y,z)$ with $ax+by+cz = n$, so the coefficient of $X^n$ counts the number of such triples. The function $g(X) = 1/((1-X^a)(1-X^b)(1-X^c))$ is called the generating function for the sequence of coefficients. These pop up all over combinatorics.

Now, how do you calculate it? Certainly not by differentiating. But computer algebra systems can generate series quite efficiently, e.g. you can ask Wolfram Alpha. Also, you can use partial fractions to simplify $g(X)$ and then find a formula for the coefficients.

Answer 2

So, we've to find the number of non-negative integral solutions of the equation $ax+by+cz=d$ i.e. the number of ways of distributing $d$ identical objects to $3$ distinct groups where a group must contain at least one object.

It is obvious that the number of objects received by group $1, 2,3$ are multiples of $a, b, c$ respectively. Now, you have to calculate the min. and max. value that $x, y, z$ can take (as you showed in your question that $z=\{0, 1,\dots, 11\}, z\in Z$) like, $$a_1\le x\le a_2\\b_1\le y\le b_2\\c_1\le z\le c_2$$

The total number of solutions of the given equation is equal to coefficient of $x^d$ in

$\displaystyle \{(x^a) ^{a_1}+(x^a) ^{a_1+1}+\dots+(x^a) ^{a_2}\}\times \{(y^b)^{b_1}+(x^b) ^{b_1+1}+\dots+(x^b)^{b_2}\}\times \{(z^c)^{c_1}+(z^c) ^{c_1+1}+\dots+(z^c)^{c_2}\}$