# number of non-negative integer solutions of $ax+by+cz=k$

How to find the number of non-negative integer solutions of $2x+3y+z=21$ ?

• For your particular numbers, all you need to do is to divide into cases $y=0,1,2,3,4,5,6,7$. They will all be straightforward. There will be a little difference between even $y$ and odd $y$. – André Nicolas Jun 5 '14 at 4:02
• I do not understand. It's hard to rewrite it as it is? $z=21-2x-3y$ and bust cases when this number is positive. Amuses me how you like to solve simple equations. – individ Jun 5 '14 at 5:58

The general problem of the title is somewhat complicated. The particular problem of the main post is straightforward.

There are $8$ possibilities for $y$, $y=0$ to $y=7$.

If $y=0$, we need to make up $21$ dollars in $2$ dollar coins and $1$ dollar coins. The number of $2$ dollar coins is $0$ to $10$, so there are $11$ possibilities.

If $y=1$, we want to make up $18$ dollars. The number of $2$ dollar coins is $0$ to $9$, so there are $10$ possibilities.

If $y=2$, the same reasoning gives $8$ possibilities.

If $y=3$ we get $7$ possibilities.

For $y=4$ and $y=5$, we get respectively $5$ possibilities and $4$.

For $y=6$ and $y=7$, we get respectively $2$ possibilities and $1$.

Remark: For the specific problem, what is needed is counting that is organized enough to ensure that we do not miss anything, and that we do not double-count.

We can use the same basic reasoning to count the number of solutions of $2x+3y+z=6k$, $6k+1$, $6k+2$, $6k+3$, $6k+4$, and $6k+5$. For each of these we will get an explicit formula in terms of $k$.

• Here I have this kind of question. Could you please help to solve it? Thank you. – Bumblebee Dec 11 '16 at 2:13

Since $x$ , $z$ are non negative integers, possible Value of $y$ are $0,1,2,3,4,5,6,7$ Now take each value of $y$ and solve the diphantine equation. For example

Taking $y=0$,, $2x+z=21$. So for every odd less then or equal to 21 will give a solution.

Since 21 is a small number, making cases will do.

However, for large numbers use the multinomial theorem.

We can look at the number of $(x,y)$ pairs such that $2x+3y\le 21$.

We have:

$$(0,0),(0,1),\dots,(0,7)$$ $$(1,0),\dots,(1,6)$$ $$(2,0),\dots,(2,5)$$ $$\vdots$$ $$(10,0)$$

The maximum $y$ takes the value $\lfloor \frac{21-2x}{3} \rfloor$, i.e.

$$\begin{array} {c|c} x&\lfloor \frac{21-2x}{3} \rfloor\\ \hline 0&7\\ 1&6\\ 2&5\\ 3&5\\ 4&4\\ 5&3\\ 6&3\\ 7&2\\ 8&1\\ 9&1\\ 10&0\\ \hline \sum&37 \end{array}$$

The lists are zero-based, so the final answer is $37+11=48$.