1
$\begingroup$

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:

Drawing from David K's answer:

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

$\endgroup$
  • 1
    $\begingroup$ I don't see how you can get to $377$ with just negatives and positives. Are you sure that zeroes are allowed? $\endgroup$ – bof Mar 21 at 21:07
  • $\begingroup$ 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. $\endgroup$ – Esmaeil Mar 21 at 21:11
  • $\begingroup$ @bof Good point. My Python says disallowing zeroes reduces the number of solutions to $160$, while allowing them gets $377$. $\endgroup$ – J.G. Mar 21 at 21:11
  • 1
    $\begingroup$ 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. $\endgroup$ – robjohn Mar 21 at 22:32
  • $\begingroup$ @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$? $\endgroup$ – robjohn Mar 21 at 22:35
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Esmaeil Mar 21 at 22:26
  • $\begingroup$ paragraph one where? paragraph two where? paragraph three where? This information should be included in the question, not simply a comment to an answer. $\endgroup$ – robjohn Mar 21 at 22:39
  • $\begingroup$ 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. $\endgroup$ – Esmaeil Mar 21 at 22:56
  • $\begingroup$ @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. $\endgroup$ – robjohn Mar 21 at 23:17
  • $\begingroup$ @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. $\endgroup$ – robjohn Mar 21 at 23:29
1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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} &=a_{n,m}+2\sum_{k=1}^ma_{n,m-k}\\ &=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 $$ a_{n,m}=\sum_{k=0}^n2^k\binom{n}{k}\binom{m}{k}\tag6 $$ Plugging in $n=3$ and $m=6$ gives $$ 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} $$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – robjohn Mar 21 at 23:26
  • $\begingroup$ Would the downvoter care to comment? This answer answers the question and more. $\endgroup$ – robjohn Mar 29 at 16:22
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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}$$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.