How many are the non-negative integer solutions of $ + + + = 16$ where $x < y$?

Question

How many are the non-negative integer solutions of $ + + + = 16$ where $x < y$?

Anyone can explain how to think to approach this type of problem? The answer is 444.

Answer 1

I can't comment so this answer is more of a comment. You use stars and bars. You have three bars | | | where each space represents one of x, y, w, or z. And you have 16 stars. So you count the number of distinct ways to rearrange the three bars and 16 stars, which is (3+16)!/(3! * 16!) = 969.

Next, find the number of cases where x = y (x = y = 1, x = y = 2, etc.) which will take some calculation but isn't hard and one can use the above stars and bars method to calculate each case. This number should be 81.

So (969 - 81)/2 = 444 is the number of non-negative integer solutions where x < y (since the number of solutions where x > y is exactly equal).

Answer 2

Consider cases and find a pattern.

When $x=0$: $$0+y+z+w=16, y\ge 1, z,w\ge 0 \Rightarrow \\ t+1+z+w=16,t,z,w\ge 0 \Rightarrow \\ t+z+w=15, t,z,w\ge 0 \Rightarrow \\ {15+3-1\choose 3-1}$$ Note: It was used Stars and Bars.

When $x=1$: $$1+y+z+w=16, y\ge 2, z,w\ge 0 \Rightarrow \\ t+2+z+w=15,t,z,w\ge 0 \Rightarrow \\ t+z+w=13, t,z,w\ge 0 \Rightarrow \\ {13+3-1\choose 3-1}$$
$\vdots$

When $x=7$: $$7+y+z+w=16, y\ge 8, z,w\ge 0 \Rightarrow \\ t+8+z+w=9,t,z,w\ge 0 \Rightarrow \\ t+z+w=1, t,z,w\ge 0 \Rightarrow \\ {1+3-1\choose 3-1}$$ Hence, it is the sum: $$\begin{align}\sum_{i=1}^8 {2i-1+3-1\choose 3-1}&=\sum_{i=1}^8 {2i+1\choose 2}=\sum_{i=1}^8 \frac{(2i+1)!}{2!(2i-1)!}=\sum_{i=1}^8 \frac{(2i+1)2i}{2}=\\ &=\sum_{i=1}^8 (2i^2+i)=2\frac{8(8+1)(2\cdot 8+1)}{6}+\frac{8(8+1)}{2}=\\ &=24\cdot 17+36=444.\end{align}$$