# Determine the number of integer solutions for $x_1+x_2+x_3+x_4+x_5 < 40$

Determine the number of integer solutions for $x_1+x_2+x_3+x_4+x_5 < 40$

a) $x_i \geq 0, i = 1,2,\dots,5$.

b) $x_i \geq -3, i = 1,2,\dots,5$.

c) $-3 \leq x_i \leq 10, i = 1,2,\dots,5$.

My try is

a)$x_1+x_2+x_3+x_4+x_5+x_6=40$

${40+6-1 \choose 40}=1221759$

need help on b) an c)

• For b, let $y_i=x_i+3$, and so $x_i=y_i-3$, so $\sum_i (y_i-3)=40$, so $\sum_i y_i= 40+18$ where $y_i \geq 0$ and now you've reduced the problem to the type of part a. – usr0192 Nov 25 '15 at 23:53
• Be careful. In part (a), since $x_1, x_2, x_3, x_4, x_5$ are non-negative integers whose sum is less than $40$, $x_6 \geq 1$. Let $y_6 = x_6 - 1$. Then $y_6$ is a non-negative integer. If we substitute $y_6 + 1$ for $x_6$ in the equation $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 40$$ we obtain $$x_1 + x_2 + x_3 + x_4 + x_5 + y_6 = 39$$ which is an equation in the non-negative integers with $\binom{39 + 5}{5} = \binom{44}{5}$ solutions in the non-negative integers. – N. F. Taussig Nov 27 '15 at 1:32

## 1 Answer

For the first problem, observe that if $x_1, x_2, x_3, x_4, x_5$ are non-negative integers satisfying the inequality $$x_1 + x_2 + x_3 + x_4 + x_5 < 40 \tag{1}$$ then $x_1 + x_2 + x_3 + x_4 + x_5 \leq 39$. Let $x_6 = 39 - (x_1 + x_2 + x_3 + x_4 + x_5)$. Then $x_6$ is a non-negative integer. Moreover, the number of solutions of inequality 1 in the non-negative integers is equal to the number of solutions to the equation $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 39 \tag{2}$$ in the non-negative integers. A particular solution to equation 2 corresponds to a choice of where to insert five addition signs in a row of $39$ ones. Hence, the number of solutions of equation 2 in the non-negative integers is $$\binom{39 + 5}{5} = \binom{44}{5}$$ since we must select which five of the $44$ symbols ($39$ ones and five addition signs) are addition signs.

For the second problem, let $y_k = x_k + 3$ for $1 \leq k \leq 5$. Since each $x_k \geq -3$, each $y_k$ is a non-negative integer. Substituting $y_k - 3$ for $x_k$, $1 \leq k \leq 5$ in inequality 1 yields \begin{align*} y_1 - 3 + y_2 - 3 + y_3 - 3 + y_4 - 3 + y_5 - 3 & < 40\\ y_1 + y_2 + y_3 + y_5 + y_5 & < 55 \tag{3} \end{align*} Then $y_1 + y_2 + y_3 + y_4 + y_5 \leq 54$. Let $y_6 = 54 - (y_1 + y_2 + y_3 + y_4 + y_5)$. Then $y_6$ is a non-negative integer. The number of solutions of inequality 3 in the non-negative integers is equal to the number of solutions of the equation $$y_1 + y_2 + y_3 + y_4 + y_5 + y_6 = 54 \tag{4}$$ in the non-negative integers. The number of solutions of equation 4 in the non-negative integers is

$$\binom{54 + 5}{5} = \binom{59}{5}$$

For the third problem, we must exclude those solutions of the second problem in which at least one of the variables $x_1, x_2, x_3, x_4, x_5$ exceeds $10$. Since $y_k = x_k + 3$ for $1 \leq k \leq 5$, this is equivalent to excluding those solutions of equation 4 in which one or more of the variables $y_1, y_2, y_3, y_4, y_5$ exceeds $13$. Since $4 \cdot 14 = 56 > 54$, at most three of the variables $y_1, y_2, y_3, y_4, y_5$ can exceed $13$ simultaneously.

Suppose $y_1 > 13$. Then $z_1 = y_1 - 14$ is a non-negative integer. Substituting $z_1 + 14$ for $y_1$ in equation 4 yields $$z_1 + y_2 + y_3 + y_4 + y_5 + y_6 = 40 \tag{5}$$ Equation 5 has

$$\binom{40 + 5}{5} = \binom{45}{5}$$

solutions in the non-negative integers. Since there are $\binom{5}{1}$ ways for one of the variables $y_1, y_2, y_3, y_4, y_5$ to exceed $13$, the number of solutions of equation 4 in the non-negative integers in which one of the variables $y_1, y_2, y_3, y_4, y_5$ exceeds $13$ is

$$\binom{5}{1}\binom{45}{5}$$

Suppose $y_1, y_2 > 13$. Let $z_1 = y_1 - 14$; let $y_2 = z_2 - 14$. Then $z_1, z_2$ are non-negative integers. Substituting $z_1 + 14$ for $y_1$ and $z_2 + 14$ for $y_2$ in equation 4 yields

$$z_1 + z_2 + y_3 + y_4 + y_5 + y_6 = 26 \tag{6}$$

Equation 6 is an equation with

$$\binom{26 + 5}{5} = \binom{31}{5}$$

solutions in the non-negative integers. Since there are $\binom{5}{2}$ ways for two of the variables $y_1, y_2, y_3, y_4, y_5$ to exceed $13$, the number of solutions of equation 4 in the non-negative integers in which two of the variables $y_1, y_2, y_3, y_4, y_5$ exceed $13$ is

$$\binom{5}{2}\binom{31}{5}$$

By similar argument, the number of solutions of equation 4 in the non-negative integers in which three of the variables $y_1, y_2, y_3, y_4, y_5$ exceed $13$ is

$$\binom{5}{3}\binom{12 + 5}{5} = \binom{5}{3}\binom{17}{5}$$

By the Inclusion-Exclusion Principle, the number of solutions of the second problem in which $x_k \leq 10$ for $1 \leq k \leq 5$, is

$$\binom{59}{5} - \binom{5}{1}\binom{45}{5} + \binom{5}{2}\binom{31}{5} - \binom{5}{3}\binom{17}{5}$$

• What happened to the displays? – Mike Jones Feb 7 '16 at 13:21
• @MikeJones When I scroll over the displays, the hidden expressions or equations are revealed. What happens when you scroll over them? I hid the expressions or equations since I wanted the person who posted the question to think about the answers rather than passively reading them. – N. F. Taussig Feb 7 '16 at 15:39
• Cool! I simply didn't know about that feature / technique. – Mike Jones Feb 9 '16 at 15:09