# How many non-negative integer solutions does the equation $3x + y + z = 24$ have?

If the equation is $x + y + z = 24$ then it is solvable with stars and bars theorem. But what to do if it is $3x + y + z = 24$?

• Did you mean to ask how many non-negative integer solutions does the equation $3x + y + z = 24$ have? Commented Jan 21, 2016 at 13:32

Observe that $$3x + y + z = 24$$ implies that $$y + z = 24 - 3x$$. For a fixed value of $$x$$, a particular solution of the equation $$y + z = 24 - 3x$$ corresponds to where we place an addition sign in a row of $$24 - 3x$$ ones. For instance, if $$x = 5$$, $$y + z = 9$$ and $$+ 1 1 1 1 1 1 1 1 1$$ corresponds to the solution $$y = 0$$ and $$z = 9$$, while $$1 1 1 1 1 1 + 1 1 1$$ corresponds to the solution $$y = 6$$ and $$z = 3$$. The number of such solutions is the number of ways we can insert one addition sign in a row of $$24 - 3x$$ ones, which is $$\binom{24 - 3x + 1}{1} = \binom{25 - 3x}{1} = 25 - 3x$$ since we must select which of the $$25 - 3x$$ symbols ($$24 - 3x$$ ones and one addition sign) will be an addition sign. Since $$x$$ is a non-negative integer satisfying $$0 \leq 24 - 3x \leq 24$$, $$x$$ can assume the nine values $$0, 1, 2, 3, 4, 5, 6, 7, 8$$. Hence, the number of solutions of the equation $$3x + y + z = 24$$ in the non-negative integers is $$\sum_{k = 0}^{8} (25 - 3x) = \frac{9(25 + 1)}{2} = \frac{9 \cdot 26}{2} = 9 \cdot 13 = 117$$ since $$\sum_{k = 0}^{8} (25 - 3x)$$ is an arithmetic series consisting of nine terms with initial term $$25$$ and final term $$1$$.

• What if the the problem is extended to 3x+2y+z=24 Commented Jul 28, 2020 at 11:12
• @NoahJ.Standerson That said, a more sophisticated approach would be to use generating functions. The objective would be to find the coefficient of $x^{24}$ in the expansion of $$(1 + x^3 + x^6 + \cdots)(1 + x^2 + x^4 + \cdots)(1 + x + x^2 + \cdots)$$ That said, you could pose the question of how to find the number of solutions of $3x + 2y + z = 24$ on this site, linking to this question as your motivation for asking it. Commented Jul 28, 2020 at 11:44
• @NoahJ.Standerson For what my opinion is worth, to over-simplify the issue, when considering the three equations of $E_1: x + y + z = 24, ~E_2: 3x + y + z = 24, ~E_3: 3x + 2y + z = 24,~$ I would opt for Stars and Bars on $E_1$, generating functions on $E_3$, and consider $E_2$ a toss-up. In my opinion, manually computing $E_3$ via a double summation on $x_1 \in \{0,1,\cdots, 8\}$ and $x_2 \in \{0,1,\cdots, 12\}$ such that $3x_1 + 2x_2 \leq 24$ is not that bad. Commented Nov 6, 2020 at 17:13
• @N.F.Taussig Thanks. I asked the question here Commented Nov 6, 2020 at 19:01

The easiest way is to realize that $x$ is completely determined by $3x=24-y-z$ meaning that by choosing $y$ and $z$, $x$ is unique as long as $24-(y+z)$ is divisible by $3$, which actually means $y+z$ divisible by 3 as well.

This comes down to counting the number of ways two numbers $0 \leq y \leq 24$, $0 \leq z \leq 24$ can sum up to a number divisible by 3.

They can sum in 1 way up to 0; 4 ways up to 3 (for each selection of $y$ in $0,1,2,3$ we have exactly one selection of $z$); 7 ways up to 6; and in general $3k+1$ ways up to $3k$, and we go up to 24, which can be done in 25 ways.

You can do the calc manually or we can write:

$$\sum\limits_{k=0}^{8} 3k+1=9+3\sum\limits_{k=0}^{8}k=9+3\frac{9\cdot 8}{2}=117$$

And I will not be lazy to add that there is a general method of solving this and similar types of linear equations. You use generic functions. First you substitute each variable in form of a polynomial.

Since we know that $x$ can go from 0 to 8 we write $$(1+x^3+x^6+x^9+x^{12}+x^{15}+x^{18}+x^{21}+x^{24})=\frac{x^{27}-1}{x^3-1}$$ for $y$ and $z$ we need $$(1+x+x^2+x^3+...+x^{23}+x^{24})=\frac{x^{25}-1}{x-1}$$ So what we do now is we multiply them getting

$$P(x)=\frac{x^{27}-1}{x^3-1}\frac{x^{25}-1}{x-1}\frac{x^{25}-1}{x-1}=\frac{(x^{27}-1)(x^{25}-1)^2}{(x^3-1)(x-1)^2}$$

If you would multiply the above polynomials you would get the coefficients by each $x^k$ that would say how many solutions you have for $3x+y+z=k$. This is simply because multiplication will actually create each solution and in our case $x^{24}$ will collect in its coefficient the number of solutions for $3x+y+z=24$.

But, we do not want to multiply, we want to find the coefficient without multiplication. We have many options and unfortunately none of them is suitable for manual calculation even for the simple case like the one we have.

Still I will mention few options:

1. Fast Fourier transformation, FFT, requires calculating the polynomial in $n$ complex points which is tedious since we would need 24 points. But a computer can do that in no time.

2. Cauchy integral theorem requires calculating a complex integral. This still goes to calculating the polynomial in sufficiently many points so that we can claim that our integral value is sufficiently precise.

If you try it you will find that the solution is the value of the integral $$\frac{1}{2\pi}\int\limits_{0}^{2\pi} (2 \cos(x)+2 \cos(2 x)+1)^2 (2 \cos(3 x)+1)$$ $$(2 \cos(9 x)+1) (2 \cos(5 x)+2 \cos(10 x)+1)^2 (\cos(12 x)) \mathrm{d} x$$

(It might be even feasible for manual calculation.)

1. Differentiate the polynomial 24 times and calculate $\frac{P^{(24)}(0)}{24!}$ for which you can use various numerical methods.

2. Finding $P(x)$ mod $x^{25}$ and then finding the highest coefficient.

So even for a very complicated equations we may find the number of solutions as long as our computers can digest the computational task.

• By multiplication you mean applying newtons binomial formula to bring denominator expressions on the top and then multiplying maually Commented Mar 26, 2022 at 13:37

Put $x=0\;,$ Then $y+z=24$. So we get Total ordered pair of $(y,z)$ is $= 25$

Put $x=1\;,$ Then $y+z=21$. So we get Total ordered pair of $(y,z)$ is $= 22$

Put $x=2\;,$ Then $y+z=18$. So we get Total ordered pair of $(y,z)$ is $= 19$

Put $x=3\;,$ Then $y+z=15$. So we get Total ordered pair of $(y,z)$ is $= 16$

Put $x=4\;,$ Then $y+z=12$. So we get Total ordered pair of $(y,z)$ is $= 13$

Put $x=5\;,$ Then $y+z=9$. So we get Total ordered pair of $(y,z)$ is $= 10$

Put $x=6\;,$ Then $y+z=6$. So we get Total ordered pair of $(y,z)$ is $= 7$

Put $x=7\;,$ Then $y+z=3$. So we get Total ordered pair of $(y,z)$ is $= 4$

Put $x=8\;,$ Then $y+z=0$. So we get Total ordered pair of $(y,z)$ is $= 1$

So total no. of ordered triples $(x,y,z)$ is $= 25+22+19+16+13+10+7+4+1=$

• Is there any shortcut method? Commented Jan 21, 2016 at 13:27
• Seems like you are missing some expressions Commented Jan 21, 2016 at 13:39
• I changed the last line to read ordered triples rather than ordered pairs. Nice solution. Commented Jan 21, 2016 at 14:10

Lets take $x=0$ so now $y+z=24$ has ${25\choose 1}$ solutions now take $y=0$ so $3x+z=24$ has 1 solution for y for each $x=1....8$ so $8$ solutions now same for $z$ so again $8$ solutions as solutions for $x=0$ have already been counted now lets take $x=1...7$ so each will have corresponding solutions to $y,z$ so its a binomial series which is ${22\choose 1}+...+{3\choose 1}=22+19+16...3=116$ so total solutions are $25+91+1=117$

• I am having trouble parsing your answer. However, it looks like you have not taken into account the fact that $y + z = 24 - 3x$, where $x$ is a non-negative integer satisfying the inequalities $0 \leq x \leq 8$. You should have obtained the sum $$\binom{25}{1} + \binom{22}{1} + \binom{19}{1} + \binom{16}{1} + \binom{13}{1} + \binom{10}{1} + \binom{7}{1} + \binom{4}{1} + \binom{1}{1}$$ Commented Jan 21, 2016 at 14:34
• Where does $\binom{3}{1}$ come from? Also, note if $y = 0$ and $z = 0$, then $x = 25/3$. Commented Jan 21, 2016 at 14:46