The number of solutions for $x+y+z=n$

Question

How do I approach this problem? I know the formula but do not how it had come. Could you please explain to me the procedure, with examples if possible.

stars and bars theorem

Answer 1

Stars and Bars is a simple general procedure that works equally easily for the problem of expressing $n$ as the sum of $k$ non-negative integers. So I would consider it the right method to use. However, for a sum of three numbers, there are alternatives. We describe a natural one.

If $x=0$, there are $n+1$ choices for $y$, namely $0$ to $n$, and then $z$ is determined. So there are $n+1$ solutions with $x=0$.

If $x=1$ there are $n$ choices for $y$, namely $0$ to $n-1$. Once $y$ is chosen, $z$ is determined. So there are $n$ solutions with $x=1$.

If $x=2$ there are $n-1$ choices for $y$,

Continue. Finally, if $x=n$ there is only one choice for $y$.

Thus the total number of choices is $1+2+\cdots +n +(n+1)$. If we wish, this sum can be written in closed form as $\frac{(n+1)(n+2)}{2}$.