How many integer solutions does the following system have?

Question

$$y_1 + y_2 + y_3 = 20$$ $$1 \le y_1 \le 5$$ $$y_2 \ge 5$$ $$y_3 \ge 5$$

I know how to solve it if it were:

$$y_1 + y_2 + y_3 = 20$$ $$y_1 \ge 1$$ $$y_2 \ge 5$$ $$y_3 \ge 5$$

then I would do:

$$\begin{align} x_1 + x_2 + x_3 &= (y_1 - 1) + (y_2 - 5) + (y_3 - 5) \\[2ex] &= (y_1 + y_2 + y_3) - 11 \\[2ex] &= 20 - 11 \\[2ex] &= 9 \end{align}$$

and then the answer is $\binom{9+3-1}{3-1}=\binom{11}{2}$

but from here I don't understand how I can solve it when $(1 \le y_1 \le 5)$.

Answer 1

Since $5$ is a small number you can easily take 5 cases for $y_1=1, 2, 3, 4$ and $5$. So, you get $\dbinom{10}{1}+\dbinom{9}{1}+\dbinom{8}{1}+\dbinom{7}{1}+\dbinom{6}{1}=40$

Or you can use generating functions:

Observe that the number of required solutions is the coefficient of $x^{20}$ in $(x+x^2+ \cdots x^5)(x^5+x^6+ \cdots)^2$.

In cases where case work is not feasible(when bigger numbers are involvd) you can also use the principle of inclusion other than generating functions to solve this problem

Answer 2

Compute (by stars and bars) how many solutions are there with $x_1, x_2 = y_2 - 5, y_3 - 5 \ge 0$ to $x_1 + x_2 + x_3 = 20 - 5 - 5$, and then subtract the number of solutions with $x_1 \ge 6$ using a similar idea.

Answer 3

You wish to solve the equation $$y_1 + y_2 + y_3 = 20 \tag{1}$$ in the integers subject to the restrictions $1 \leq y_1 \leq 5$, $y_2 \geq 5$, $y_3 \geq 5$. By making the substitutions of $x_1 + 1$ for $y_1$, $x_2 + 5$ for $y_2$, and $x_3 + 5$ for $y_3$, you obtained $$x_1 + x_2 + x_3 = 9 \tag{2}$$ and correctly noted that if there were no restrictions, then equation 2 would have $$\binom{9 + 2}{2} = \binom{11}{2}$$ solutions. Note that the substitutions you made impose the restrictions that $0 \leq x_1 \leq 4$, $0 \leq x_2$, and $0 \leq x_3$. Thus, we must exclude those solutions of equation 2 in which $x_2 \geq 5$. To do so, let \begin{align*} w_1 & = x_1 - 5\\ w_2 & = x_2\\ w_3 & = x_3 \end{align*} Substituting for $w_1 + 5$ for $x_1$, $w_2$ for $x_2$, and $w_3$ for $x_3$ in equation 1 yields $$w_1 + w_2 + w_3 = 4$$ which is an equation in the nonnegative integers with $$\binom{4 + 2}{2} = \binom{6}{2}$$ solutions. Hence, the number of solutions of equation 1 subject to the restrictions $1 \leq y_1 \leq 6$, $y_2 \geq 5$, and $y_3 \geq 5$ is $$\binom{11}{2} - \binom{6}{2}$$

Answer 4

Firstly, pre-place $1$ in $y_1$ and $5$ each in the rest.
We now only need 9 more.

Applying stars and bars, we get $\dbinom{9+3-1}{3-1} = \dbinom{11}{2}$

To take care of the restriction on $y_1$, we deliberately put $5$ more in it, so that it violates restriction with $6$ in it, and exclude such solutions,

so final answer is $\dbinom{11}{2} - \dbinom{11-5}{2} = 40$

You can apply the same technique for more complex cases using inclusion-exclusion