How many non-negative integer solutions exist for: $x+y+z=48$ where, $x<y<z$

Question

I want to find the number of non-negative integral solutions to the following:

$x+y+z=48$ where, $x<y<z$.

The answer is apparently 192 and the solution provided is $$\frac{\dbinom{50}{2}-\dbinom{3}{2}\cdot24 – 1}{3!}$$

The method I used was I guessed that the lowest value of $z$ will be 17, I.E. $(15,16,17)$. When $x$ was an odd number, the number of solutions I got were of the form $3K+1$ and when $x$ was even, the number of solutions were of the form $3K-1$. So listing them all down gets you the series: $1,2,4,5,7,8,…,23$

The sum of all the solutions is 192. I did it this way, however this calculation could have been tedious had the number on $R.H.S$ been any larger.

Now after reading the solution, I can understand bits and parts of it. $\binom{50}{2}$ is the total number of solutions , ignoring the $x<y<z$ constraint. The division by 3! I guess is justified by noting that $x$ is the smallest among all the solutions in $\frac{1}{3^{rd}}$ of the cases while in those cases, $\frac{1}{2}$ of them have $y<z$ so we are multiplying by $\frac{1}{6}$. Again we are subtracting 1 because there exists a solution {$16,16,16$} which has to be excluded from the solution set.

My doubts are
$1)$how do you get the "$-\binom{3}{2}\cdot24$" and
$2)$ Is there any different way that one can use to solve this question?

P.S. I have seen similar questions(not exactly the same) on MSE but I am not able to ask my doubts on those posts. So pls point me in the right direction. Thanks!

Answer 1

The approach can be summarized as follows. First, we find the solutions to $x + y + z = 48$ such that $x,y,z$ are all distinct. Then, we note that each valid $x<y<z$ is represented $3!$ times among this set, since each permutation of $x,y,z$ gives a solution to $x+y+z=48$ with distinct values, hence the division by $3!$.

The "stars and bars" formula tells us that the total number of non-negative solutions to $x+y+z = 48$ is $$ \binom{48 + 3 - 1}{3 - 1} = \binom{50}2, $$ as you have stated in the question. Now, we subtract off any solutions where $x,y,z$ are not distinct.

There is one solution where $x = y = z$, namely $x = y = z = 16$.

Now, we want to count the solutions where exactly two are equal. We can uniquely generate any such solution with the following process:

• Select $2$ values that will be equal (for instance, $x$ and $z$). There are $\binom 32 = 3$ such choices.
• Select a common value for the equal pair. This can be any non-negative integer from $0$ to $24$ inclusive except for $16$ (since choosing $16$ would lead to all three being equal). There are $24$ valid choices for this value.
• Once we have made the above choices, the remaining number is forced, so there are no more choices to be made.

Since the above process uniquely generates all possibilities, we can conclude that there are $\binom 32 \cdot 24$ total solutions to $x+y+z = 48$ in which exactly two values are equal.

With that, we may finally conclude that the desired quanitity is indeed $$ \frac{\binom{50}2 - \binom 32 \cdot 24 - 1}{3!}. $$

---

As for an alternative approach: using the inclusion-exclusion principle would yield the numerator $$ \begin{align} [\text{# of triples without repeats}] &= [\text{total # of triples}] \\ & \quad - [\text{# of triples with } x=y] \\ & \quad - [\text{# of triples with } y=z] \\ & \quad - [\text{# of triples with } x=z] \\ & \quad + 2\cdot [\text{# of triples with } x=y=z] \\ & = \binom{50}2 - 3 \cdot 25 + 2, \end{align} $$ which is equal to the $\binom{50}2 - \binom 32 \cdot 24 - 1$ we got above.