# Determine the number of ordered triple $(x, y, z)$ of integer numbers (negatives and positives) satisfying $|x| + |y| + |z| \le 6$

Determine the number of ordered triple $$(x, y, z)$$ of integer numbers (negatives and positives) satisfying $$|x| + |y| + |z| \le 6$$

I know that final answer is 377, but how?

Edit:

One way to count the ways is to first do the ways for which $$x > 0,$$ $$y > 0,$$ and $$z > 0.$$ That's the number of ways to put $$6$$ or fewer indistinguishable balls into $$3$$ numbered bins under the constraint that every bin must have at least one ball, which is the number of ways to put $$3$$ or fewer indistinguishable balls in $$3$$ numbered bins without that constraint, which is the number of ways of putting exactly $$3$$ indistinguishable balls in $$4$$ numbered bins. Multiply by $$8$$ to take into account all the cases where $$x < 0$$ or $$y < 0$$ or $$z < 0.$$

$$x,y,z >0 => x + y + z <= 3, n = Cr(3+4-1,3) * (8) = 160$$

Now let $$x = 0,$$ $$y > 0,$$ and $$z > 0.$$ Count the number of ways to put up to $$6$$ balls in $$2$$ bins if each bin must contain at least one ball. Multiply by four to account for all the cases were $$y < 0$$ or $$z < 0.$$ Multiply that result by $$3$$ to account for the fact that we could have chosen $$y= 0$$ or $$z=0$$ instead of $$x = 0.$$

$$x=0, x,y>0 => y+z <=6, n = Cr(4+3-1, 4) * 3 * 14 = 180$$

Now let $$x = y = 0$$ and $$z > 0.$$ There are $$6$$ ways for that to happen. Multiply by $$2$$ to account for $$z < 0,$$ then by $$3$$ to account for the other choices of which variables are zeros.

$$x,y = 0, z>0 => z<=6, n = 6 * 2 * 3 = 36$$

$$x,y,z=0, n = 1$$

Sum of all of them is : 160 + 180 + 36 + 1 = 377

• I don't see how you can get to $377$ with just negatives and positives. Are you sure that zeroes are allowed? – bof Mar 21 '19 at 21:07
• I am sure the answer is 377, because I have it from a book, but I don't know how they reach to this answer as well. – Esmaeil Mar 21 '19 at 21:11
• @bof Good point. My Python says disallowing zeroes reduces the number of solutions to $160$, while allowing them gets $377$. – J.G. Mar 21 '19 at 21:11
• Please give more context. Providing context not only assures that this is not simply copied from a homework assignment, but also allows answers to be better directed at where the problem lies and to be within the proper scope. Please avoid "I have no clue" questions. Defining keywords and trying a simpler, similar problem often helps. – robjohn Mar 21 '19 at 22:32
• @Esmaeil: what book? What topics are covered in the section where this question arose? Have you tried anything? perhaps the number of pairs that sum to less than or equal to $m$? – robjohn Mar 21 '19 at 22:35

One way to count the ways is to first do the ways for which $$x > 0,$$ $$y > 0,$$ and $$z > 0.$$ That's the number of ways to put $$6$$ or fewer indistinguishable balls into $$3$$ numbered bins under the constraint that every bin must have at least one ball, which is the number of ways to put $$3$$ or fewer indistinguishable balls in $$3$$ numbered bins without that constraint, which is the number of ways of putting exactly $$3$$ indistinguishable balls in $$4$$ numbered bins. Multiply by $$8$$ to take into account all the cases where $$x < 0$$ or $$y < 0$$ or $$z < 0.$$

Now let $$x = 0,$$ $$y > 0,$$ and $$z > 0.$$ Count the number of ways to put up to $$6$$ balls in $$2$$ bins if each bin must contain at least one ball. Multiply by four to account for all the cases were $$y < 0$$ or $$z < 0.$$ Multiply that result by $$3$$ to account for the fact that we could have chosen $$y= 0$$ or $$z=0$$ instead of $$x = 0.$$

Now let $$x = y = 0$$ and $$z > 0.$$ There are $$6$$ ways for that to happen. Multiply by $$2$$ to account for $$z < 0,$$ then by $$3$$ to account for the other choices of which variables are zeros.

Finally add $$1$$ for the case $$x = y = z = 0,$$ which was not covered by any of the other cases.

The total will be $$377$$ if you do all these calculations correctly.

• 1. $x,y,z >0 => x + y + z <= 3, n = Cr(3+4-1,3) * (8) = 160$ as explained in paragraph one 2. $x=0, x,y>0 => y+z <=6, n = Cr(4+3-1, 4) * 3 * 14 = 180$ as explained in paragraph two 3. $x,y = 0, z>0 => z<=6, n = 6 * 2 * 3 = 36$ as explained in paragraph three 4. $x,y,z=0, n = 1$ Sum of all of them is : 160 + 180 + 36 + 1 = 377 – Esmaeil Mar 21 '19 at 22:26
• paragraph one where? paragraph two where? paragraph three where? This information should be included in the question, not simply a comment to an answer. – robjohn Mar 21 '19 at 22:39
• I write in comment, because I try @David method. But he did not calculate it himself then I do to show he find correct method. – Esmaeil Mar 21 '19 at 22:56
• @Esmaeil: Oh, I see. These are paragraphs in David K's answer. I didn't understand before. Good! Adding this to your question to show your attempt would be very good. – robjohn Mar 21 '19 at 23:17
• @Esmaeil: It is pretty important that you add this attempt as context to the question; otherwise, the question may be closed (there is already one close vote) and possibly deleted. – robjohn Mar 21 '19 at 23:29

This is $$f(6)$$ where $$f(n)$$ for integers $$n\ge0$$ is the number of lattice points in the polyhedron $$nP$$. This is the $$n$$-fold dilate of $$P$$, the polyhedron with vertices $$(\pm1,0,0)$$, $$(0,\pm1,0)$$ and $$(0,0,\pm1)$$. By Ehrhart's theorem, $$f$$ is a degree $$3$$ polynomial in $$n$$. Moreover, its leading coefficient is the volume of $$P$$, namely $$\frac43$$. We also have $$f(0)=1$$ and $$f(1)=7$$. But by Macdonald's reciprocity law $$f(-n)$$ is the negative of the number of lattice points in the interior of $$nP$$, so that $$f(-1)=-1$$. The only polynomial satisfying all these conditions is $$f(n)=\frac43n^3+2n^2+\frac83n+1.$$ Then $$f(6)=377$$.

Try it first for the 2-dimensional $$(x, y)$$-plane and for smaller upper bounds: $$|x| + |y| \leq 1$$, then $$|x| + |y| \leq 2$$, then $$|x| + |y| \leq 3$$. In each case, sketch a picture.

Now try it in the $$(x, y, z)$$-space, with smaller upper bounds: $$|x| + |y| + |z| \leq 1$$, then $$|x| + |y| + |z| \leq 2$$, etc.. Sketch a picture in every case.

By the time you are up to $$|x| + |y| + |z| \leq 3$$, you will be seeing enough of a pattern to solve your problem--maybe even much earlier.

Here is a brute force solution. Letters $$x,y,z$$ stand for nonzero integers.

Case 1. Permutations of $$(x,x,x)$$.
$$(1,1,1)$$
$$(2,2,2)$$
$$2$$ combinations, one permutation of each, $$2^3=8$$ ways to assign $$\pm$$ signs, so $$2\cdot1\cdot8=\boxed{16}$$ solutions.

Case 2. Permutations of $$(x,x,y)$$, $$x\ne y$$.
$$(1,1,2)$$
$$(1,1,3)$$
$$(1,1,4)$$
$$(2,2,1)$$
$$4$$ combos, $$3$$ perms each, $$2^3=8$$ sign choices, so $$4\cdot3\cdot8=\boxed{96}$$ solutions.

Case 3. Perms of $$(x,y,z)$$ with $$x,y,z$$ all different.
$$(1,2,3)$$
Just $$1$$ combo, $$6$$ perms, $$8$$ sign choices, so $$1\cdot6\cdot8=\boxed{48}$$ solutions.

Case 4. Perms of $$(x,x,0)$$.
$$(1,1,0)$$
$$(2,2,0)$$
$$(3,3,0)$$
$$3$$ combos, $$3$$ perms each, $$2^2=4$$ sign choices, so $$3\cdot3\cdot4=\boxed{36}$$ solutions.

Case 5. Perms of $$(x,y,0)$$, $$x\ne y$$.
$$(1,2,0)$$
$$(1,3,0)$$
$$(1,4,0)$$
$$(1,5,0)$$
$$(2,3,0)$$
$$(2,4,0)$$
$$6$$ combos, $$6$$ perms each, $$4$$ sign choices, so $$6\cdot6\cdot4=\boxed{144}$$ solutions.

Case 6. Perms of $$(x,0,0)$$.
$$(1,0,0)$$
$$(2,0,0)$$
$$(3,0,0)$$
$$(4,0,0)$$
$$(5,0,0)$$
$$(6,0,0)$$
$$6$$ combos, $$3$$ perms each, $$2$$ sign choices, so $$6\cdot3\cdot2=\boxed{36}$$ solutions.

Case 7. Perms of $$(0,0,0)$$.
$$(0,0,0$$. Just $$1\cdot1\cdot1=\boxed{1}$$ solution

The final answer is $$16+96+48+36+144+36+1=\boxed{377}$$ provided $$0$$'s are allowed. However, if you really mean "negatives and positives" (no $$0$$'s) then you only get $$16+96+48=\boxed{160}$$.

Let $$a_{n,m}$$ be the number of $$n$$-tuples of integers so that $$\sum_{k=1}^n|x_k|\le m\tag1$$ Pretty simply, we have $$a_{1,m}=2\binom{m}{1}+\binom{m}{0}\tag2$$ Furthermore, we have the recurrence \begin{align} a_{n+1,m} &=\overbrace{\quad a_{n,m}\quad\vphantom{\sum_1^m}}^\text{0 in position n+1}+\overbrace{2\sum_{k=1}^ma_{n,m-k}}^\text{\pm k in position n+1}\\ &=a_{n,m}+2\sum_{k=0}^{m-1}a_{n,k}\tag3 \end{align} Thus, $$a_{2,m}=4\binom{m}{2}+4\binom{m}{1}+\binom{m}{0}\tag4$$ and $$a_{3,m}=8\binom{m}{3}+12\binom{m}{2}+6\binom{m}{1}+\binom{m}{0}\tag5$$ In general, we get by induction, using $$(2)$$ and $$(3)$$ and $$\sum\limits_{k=0}^{n-1}\binom{k}{j}=\binom{n}{j+1}$$, $$a_{n,m}=\sum_{k=0}^n2^k\binom{n}{k}\binom{m}{k}\tag6$$ Plugging in $$n=3$$ and $$m=6$$ gives $$\bbox[5px,border:2px solid #C0A000]{a_{3,6}=377}\tag7$$

I just came across this answer which proves $$\sum_{k=0}^n\binom{n}{k}\binom{m+k}{n}=\sum_{k=0}^n2^k\binom{n}{k}\binom{m}{k}$$

• I have undeleted my answer because the OP has provided context in a comment to David K's answer. I have prompted the OP to include that effort in the question. – robjohn Mar 21 '19 at 23:26
• Would the downvoter care to comment? This answer answers the question and more. – robjohn Mar 29 '19 at 16:22
• Since no explanation was given for the recent downvote (10 months after the last activity on this question), I have expanded the discussion above. If the downvote was for some other reason, it would be nice to know that reason. – robjohn Jan 16 '20 at 22:00