# Number of integral solutions for $|x | + | y | + | z | = 10$

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 !!!

• Or rather,how do we derive the formula? – user43081 Oct 28 '12 at 12:30
• yes !!! sir... any help will be appreciate... – 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$$

• 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. – Seyhmus Güngören Oct 28 '12 at 13:04
• Very nicely done indeed! – LieX Oct 28 '12 at 13:09
• @SeyhmusGüngören What does convolution mean in this context? (I'm new to this concept.) – bodacydo Oct 30 '12 at 17:57
• @bodacydo please have a look at : en.wikipedia.org/wiki/Convolution – 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.

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

(1) z=0, $40$ patterns

z=1, $36$

z=2, $32$

・・・

z=9,$4$

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

$40+8*10C2+2=402$

x+y+z=10

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 ?