Watch all Cases

$\textbf{Generalization:}$ Find the number of all non-negative solutions to the equation $x+y+z = n$ under the condition that $x \leq y \leq z.$

---

$\textbf{Lemma:}$ The number of all non-negative solutions to the equation $x+y =$ under the condition that $x \leq y$ is $\left \lfloor \frac{n}{2} \right \rfloor + 1$

Fix $x = k$ . We have $y = n-k$ and $k \leq n-k \implies k \leq \frac{n}{2}$ . If $n$ is even or odd, the valid $k$ values are $0, 1, 2, ..., \left \lfloor \frac{n}{2} \right \rfloor$ . Thus, we have proven the lemma.

---

Disregarding the condition, with simple stars and bars, the answer is simply ${n + 2 \choose 2}$ . Note that there are four cases: $x < y < z , x = y < z, x < y = z , x = y = z$ . Denote the number of ways to find each by $\varepsilon_1, \varepsilon_2, \varepsilon_3, \varepsilon_4$ , respectively. We have that ${n+2 \choose 2} = 6\varepsilon_1 + 3\varepsilon_2 + 3\varepsilon_3 + \varepsilon_4.$ It suffices to find $\sum_{1 \leq k \leq 4}{\varepsilon_k}$ . It is obvious that $\varepsilon_4 = 1$ if and only if $3 | n$ and zero otherwise. Thus, we can write $\varepsilon_4$ as $\left \lfloor \frac{n}{3} \right \rfloor - \left \lfloor \frac{n-1}{3} \right \rfloor$ .

We will now try to find $\varepsilon_2 + \varepsilon_3 + \varepsilon_4$ . Note that this value is just the number of solutions to $2u + v = n$ . Letting $s = u, t = u+v$ , we have $s + t = n$ . By the $\textbf{Lemma}$ , we have that the number of ways to do this is $\left \lfloor \frac{n}{2} \right \rfloor + 1$ . Thus we have $\begin{aligned} \varepsilon_2 + \varepsilon_3 & = \left \lfloor \frac{n}{2} \right \rfloor + 1 - \left \lfloor \frac{n}{3} \right \rfloor + \left \lfloor \frac{n-1}{3} \right \rfloor \\ \varepsilon_1 & = \frac{(n+1)(n+2)}{12} - \frac{1}{2} \left \lfloor \frac{n}{2} \right \rfloor + \frac{1}{3} \left \lfloor \frac{n}{3} \right \rfloor - \frac{1}{3} \left \lfloor \frac{n-1}{3} \right \rfloor - \frac{1}{2} \\ \varepsilon_1 + \varepsilon_2 + \varepsilon_3 + \varepsilon_4 & = \frac{(n+1)(n+2)}{12} + \frac{1}{2} \left \lfloor \frac{n}{2} \right \rfloor + \frac{1}{3} \left \lfloor \frac{n}{3} \right \rfloor - \frac{1}{3} \left \lfloor \frac{n-1}{3} \right \rfloor + \frac{1}{2} \end{aligned}$ Plugging in $2016$ gives us our final answer.