Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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
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$$
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
Since there will be 3 cases, total solution possible = 45 * 3 = 135
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 ?
