How many integer solutions to$ x+y+z \le 6$ where $x,y,z$ are non-negative?

Question

I understand the steps towards working this question out if $x + y + z = 6$, but what are the steps for an inequality?

Answer 1

Hint: Consider $x+y+z=0 \implies x=y=z=0$ (that's one solution)

Consider $x+y+z=1$. There is only one way to produce 1, and this way is $1+0+0=1$. Though, the number 1 in the sum can hold 3 places (e.g. $1+0+0$ or $0+1+0$ or $0+0+1$). As you can see, order matters. So you take 3 different solutions.

$(x,y,z)=(1,0,0)$

$(x,y,z)=(0,1,0)$

$(x,y,z)=(0,0,1)$

You can go on with $x+y+z=2$. There are 2 fundamental ways (and their respective permutations) to construct this sum, which are $2+0+0$ and $1+1+0$....

Answer 2

This is an example of stars and bars. First, rephrase the question to make it an equality:

Find the number of solutions $(w, x, y, z)$ such that $w + x + y + z = 6$ and $w, x, y, z$ are non-negative integers.

To apply stars and bars, you transform $(w, x, y, z)$ so that they are positive integers.

Find the number of solutions $(w, x, y, z)$ such that $(w + 1) + (x + 1) + (y + 1) + (z + 1) = 10$ and $(w + 1), (x + 1), (y + 1), (z + 1)$ are positive integers.

This gives $\binom{9}{3}$ as the answer.

Answer 3

$x$ can be anything from $0$ to $6$.
$y$ can be anything from $0$ to $6 - x$.
$z$ can be anything from $0$ to $6 - (x+y)$

$$\begin{align} \text{total} &= \sum_{x=0}^6 \quad \sum_{y=0}^{6-x}\quad \sum_{z=0}^{6-(x+y)} 1 \\ &\quad \text{...and the rest is just algebra} \\ &= \sum_{x=0}^6 \quad \sum_{y=0}^{6-x} 6-(x+y) + 1 \\ &= \sum_{x=0}^6 \left(\sum_{y=0}^{6-x} 7 - x\right) - \left(\sum_{y=0}^{6-x}y\right) \\ &= \sum_{x=0}^6 (6 - x + 1)(7 - x) - \left(\frac{(6-x)^2 + (6-x)}2\right) \\ &= \frac 12 \sum_{x=0}^6 x^2 - 15x + 56 \\ &= \frac 12\left( \sum_{x=0}^6 x^2 - 15\sum_{x=0}^6x + \sum_{x=0}^6 56 \right) \\ &= \frac 12\left( \frac{6(6+1)(2\cdot 6 + 1)}{6} - 15 \frac{6(6+1)}2 + 56\cdot(6+1) \right) \\ &= 84 \end{align}$$

Answer 4

The number of solutions of the inequality $x + y + z \leq 6$ in the non-negative integers is equal to the number of solutions of the equation $x + y + z + w = 6$ in the non-negative integers since $w = 6 - (x + y + z)$ represents the difference between $6$ and the actual sum.

A solution can be represented by placing three $+$ signs in a list of six ones. For instance, the solution $x = 2$, $y = 1$, $z = 0$, $w = 3$ of the equation $x + y + z + w = 6$ can be represented as

$$1 1 + 1 + + 1 1 1$$

Equivalently, it represents the solution $x = 2$, $y = 1$, $z = 0$ of the inequality $x + y + z \leq 6$.

Note that a plus sign before all the ones indicates that $x = 0$ and a plus sign after all the ones indicates that $w = 0$. Consecutive addition signs indicate that the variable that would go between the addition signs is equal to zero.

Each list contains nine symbols, the six ones and the three plus signs. The number of solutions to the inequality $x + y + z \leq 6$ or, equivalently, the equation $x + y + z + w = 6$ is the number of ways you can place three plus signs in a list of six ones and three plus signs, which is

$$\binom{9}{3} = \frac{9!}{3!(9 - 3)!} = \frac{9!}{3!6!} = \frac{9 \cdot 8 \cdot 7}{3 \cdot 2 \cdot 1} = 84$$