How can I find the number of integral solution to the equation

$|x | + | y | + | z | = 10.$

I am using the formula,

Number of integral solutions for $|x| +|y| +|z| = p$ is $(4P^2) +2 $, So the answer is 402.

But, I want to know, How we can find it without using formula.

any suggestion !!!

Please help

  • 2
    $\begingroup$ Or rather,how do we derive the formula? $\endgroup$ – user43081 Oct 28 '12 at 12:30
  • $\begingroup$ yes !!! sir... any help will be appreciate... $\endgroup$ – ram Oct 28 '12 at 12:36

The number $n_1(k)$ of solutions of $$|x|=k$$ is quite obviously given by $$n_1(k)=\begin{cases}2&\text{if }k>0\\1&\text{if }k=0\\0&\text{if }k<0.\end {cases}$$ Then the number of solutions $n_2(k)$ of $$|x|+|y|=k$$ can by obtained as $$n_2(k)=\sum_{i\in\mathbb Z}n_1(i)\cdot n_1(k-i)=\begin{cases}2+(k-1)\cdot 4+2=4k& \text{if }k>0\\1&\text{if }k=0\\0&\text{if }k<0.\end{cases}$$ Finally, the number $n_3(k)$ of solutions of $$|x|+|y|+|z|=k$$ is (using $\sum_{i=1}^n i=\frac{n(n+1)}2$) $$n_3(k)=\sum_{i\in\mathbb Z}n_2(i)\cdot n_1(k-i)\\=\begin{cases}2+2\sum_{i=1}^{k-1}4i + 4k=2+4k(k-1)+4k=4k^2+2& \text{if }k>0\\1&\text{if }k=0\\0&\text{if }k<0.\end{cases}$$

In general, the number of solutions of $$|x_1|+\cdots +|x_m|=k$$ is given by $$n_m(k)=\begin{cases}P_m(k)&\text{if }k>0\\1&\text{if }k=0\\0&\text{if }k<0,\end{cases}$$ where $P_m$ is some polynomial of degree $m-1$. The $P_m$ can be obtained recursively, e.g. via the relations $$P_m(X+1)-P_m(X)= P_{m-1}(X)+P_{m-1}(X+1)$$ $$P_m(1)=2m$$

  • $\begingroup$ nice solution. It is easy to think that there is sort of convolution but to write them down in a systematic way is really good. $\endgroup$ – Seyhmus Güngören Oct 28 '12 at 13:04
  • $\begingroup$ Very nicely done indeed! $\endgroup$ – LieX Oct 28 '12 at 13:09
  • 1
    $\begingroup$ @SeyhmusGüngören What does convolution mean in this context? (I'm new to this concept.) $\endgroup$ – bodacydo Oct 30 '12 at 17:57
  • $\begingroup$ @bodacydo please have a look at : en.wikipedia.org/wiki/Convolution $\endgroup$ – Seyhmus Güngören Oct 30 '12 at 20:46

I give a geometric derivation, we want to count all integral points lying on surface $|x|+|y|+|z|=P$. Actually in 3D space, in every octant, the shape of surface is triangle shape.

For example, if $P=4$, then the shape in the first octant would be $$ \begin{array}[ccccccccc] \ & & & &Q(0,0,4)& & & &\\ & & &D(0,1,3))& &D(1,0,3)& & &\\ & &D(0,2,2)& &S(1,1,2)& &D(2,0,2)& &\\ &D(0,3,1)& &S(1,2,1)& &S(2,1,1)& &D(3,0,1)&\\ Q(0,4,0)& &D(1,3,0)& &D(2,2,0)& &D(3,1,0)& &Q(4,0,0)\\ \end{array} $$ where $Q$ denotes the points that should be shared by 4 octants, $D$ denotes the points that should be shared by 2 octants and $S$ denotes the points belongs only to this octants.

So for the total octants, the number of points with S is $$n_S=8\cdot\frac{(P-1)(P-2)}{2}=4P^2-12P+8$$

the number of points with D is $$n_D=8\cdot\frac{3(P-1)}{2}=12P-12$$

the number of points with Q is $$n_Q=8\cdot\frac{3}{4}=6$$

So the total number would be $$n=n_S+n_D+n_Q=4P^2+2$$


I'll give an argument for computing the number of integer solutions of $\sum_{i=1}^n|x_i|=k$ for any $n,k\in\Bbb N$, then specialize it for $n=3$.

First the number of solutions of $\sum_{i=1}^nx_i=k$ with all $x_i\geq0$ is $\binom{k+n-1}{n-1}$: first draw $k+n-1$ vertical strokes, then for $n-1$ of them cross them with a horizontal stroke, turning them into $+$ signs, to obtain a decomposition $x_1+x_2+\cdots+x_n$ of $k$ with each of the $x_i$ in unary notation (possibly with no strokes at all, representing $0$).

This counts the purely non-negative solutions to the original problem. To include solutions where $x_i<0$ for some $i$, we record the subset of the positions $i$ where this happens, and then replace each such negative $x_i$ by $-1-x_i$, making it non-negative. The result is a solution to the non-negative problem above, but with $k$ diminished by the number of originally negative $x_i$ (because of the term $-1$ used for each one). Thus we get the number $$ \sum_{j=0}^n\binom nj\binom{k+n-1-j}{n-1} $$ of solutions to $\sum_{i=1}^n|x_i|=k$, where the binomial coefficient on the left counts the subsets of negative entries, and the one on the right counts the number of solutions of the corresponding non-negative problem. This summation does not appear to be of the type that can be reduced to a single binomial coefficient (as it would if the sum were alternating).

For $n=3$ one gets $\sum_{j=0}^3\binom3j\binom{k+2-j}2$, which gives concretely $$ \frac{(k+2)(k+1)+3(k+1)k+3k(k-1)+(k-1)(k-2)}2 =4k^2+2. $$


This is very similar to Marc's answer, but since I was deriving it when he posted, I decided to keep going and post it anyway.

First count the number of solution to $$ x+y+z=k, x,y,z\geq 1. $$ By usual bars and stars argument, this is ${k-1\choose 2}$. Now by symetry, each of these solution is in fact $2^3$ solution allowing $\pm j$ in each variable.

Now count the number of solution to $$ x+y+z=k, $$ where exactly one of the variable is $0$. Using similar techniques and symetry arguments, on gets $$ {3\choose 1}{k-1\choose 1}2^2. $$

Finally the number of solution to $$ x+y+z=k, $$ where exactly $2$ are $0$ is given by $6$, for you have $3$ choices for the non-zero variable and $2$ choices for its sign.

This give

$$ \sum_{i=0}^{2}{3\choose i}{k-1\choose 2-i}2^{3-i}=4k^2+2 $$

This generalized to $$ \sum_{i=0}^{n-1}{n\choose i}{k-1\choose n-1-i}2^{n-i}; $$


A sketch of derivation goes like this: (I did it on paper but perhaps missed some pluses or minuses). Also this approach is not a generic one.

Given the problem we know bound on each variable is $p$. Now if we assume we know $x = p$ then y and z can only be 0. If x is p-1, y and z $\in (0,1)$ which makes 4 cases (not 8 since +0 is same as -0). Similarly for x=p-2 we have y and z $\in (0,1,2)$ making 8 cases. You sum this all till you have x=1, Then double it for considering -ve values of x and finally add, x = 0 case, you would get the formula. :)

Not elegant way at all, though there is clear trend in these additions, but would work.


(1) z=0, $40$ patterns

z=1, $36$

z=2, $32$



but z=10,$2$ the total is $S=2(4+8+\dots+36)+40+2=402$

(2) Another counting

There are 8 areas by plus and minus of x,y,z, 40 patterns at x=0, 2 patterns at y=z=0, therefore




  1. No. of integral solution when all are positive -> 9C2 = 36
  2. No. of integral solution when all are negative -> 12C2 = 66
  3. No. of integral solution when any one of them is negative = 10C2 = 45

Since there will be 3 cases, total solution possible = 45 * 3 = 135

  1. No. of integral solution when two of them are negative = 11C2 = 55

Since again there will be 3 cases, total solution possible - 55*3 = 165

Total solution possible = 36+66+135+165 = 402

I am using the formula when n identical things are to be distributed among r persons, each one of whom receives at least 1 item is (n-1)C(r-1).

Am i wrong in this method ?


I think it must 8 times the number of intergral solution to equation: $$x+y+z=10$$ So the result is : $$8C_{12}^2=528$$


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.