Finding the number of non-negative integral solutions of $x + y + z = 10$

2.5k Views Asked by At

I realize that this question has been asked multiple times and I do not really want to know how to do it, I understand how to solve it, my issue is somehow I have used the distribution and I am not getting the right answer.

Method of Solving:
I solved this in the first go by directly applying the distribution formula that is $$\binom {n+r-1}{r-1} $$
By using, $n = 10, r= 3$ we get,
$$\binom{12}{2} = 66$$ however the answer given is $$\binom{12}{3} = 220$$ Next, I tried to solve by taking multiple cases that is, setting any variable, $x,y$ or $z$ to values from $0,1,2,3...10$, so for example if $x = 0$ then we get, $$y+z=10$$ now it is simple enough to distribute this even without the formula, we get $$\Bigl((0,10),(1,9),(2,8)(3,7),(4,6)\Bigl) \cdot 2,(5,5)$$ which gives us $11$ cases, that can be verified using the formula $$P_0 = \binom{11}{1}.$$ Now taking cases till $x=10$ we get, the final result as $$\sum _{n=0} ^{n=10} P_n = 11+ 10 + 9 + 8+ \ldots +1 = 66$$
Please tell me where I am going wrong or of it simply a case of the answer in the text being wrong, and if the second method is correct.

2

There are 2 best solutions below

3
On

I think they have the role of $r$ and $n$ mixed up in the given solution, that is why they got the wrong result. Look at the proof of the formula again, and you will see immediately which one of $10$ and $3$ play the role of $n$ and $r$.

So you are right, the answer is 66, because $\binom{3+10-1}{10}=66$.

0
On

The answer is $66$ even by double checking with generating functions, more details here.

The number of solutions for $x+y+z=n, x\geq0, y\geq0, z\geq0$ is the coefficient of $x^n$ term of the $$(1+x+x^2+x^3+...+x^k+...)^3=\frac{1}{(1-x)^3}$$ and because $$\frac{1}{(1-x)^3}= \frac{1}{2}\left(\frac{1}{1-x}\right)^{''}= \frac{1}{2}\left(\sum\limits_{k=0}x^k\right)^{''}= \sum\limits_{k=2}\frac{k(k-1)}{2}x^{k-2}$$ the coefficient of $x^n$ is $\color{green}{\frac{(n+2)(n+1)}{2}=\binom{n+2}{2}}$, which for $n=10$ yields $66$.