1
$\begingroup$

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.

$\endgroup$
2
  • 4
    $\begingroup$ It's half the number of solutions for $x\neq y$. If you find the number of solution for $x = y$, so the number of solutions of $2x + w + z =16$ then you just need to subtract that from the total number of solutions of $x+y+w+z$ and divide that by 2. $\endgroup$ May 12 '19 at 1:23
  • $\begingroup$ Make that an answer! $\endgroup$
    – Toby Mak
    May 12 '19 at 1:24
7
$\begingroup$

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).

$\endgroup$
0
$\begingroup$

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}$$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.