# Combinatorics question on number of integer solutions given different restrictions

How many nonnegative integer solutions are there to $$x_1 + x_2 + \ldots + x_5 = 20$$

(a) With $$x_i \leq 10$$?

(b) With $$x_i \leq 8$$?

(c) With $$x_1 = 2x_2$$?

Here is what I did:

(a) $${24\choose 4} - 5{14\choose 4}$$

I did this by assigning $$10$$ to an $$x_i$$ and then going from there. I subtracted this case from the total number of cases to get the number of desired cases.

I'm thinking this should rather be $${24\choose 4} - 5{13\choose 4}$$ but I am not sure...I think this because maybe I should have assigned $$11$$ to an $$x_i$$ rather than $$10$$ and then subtracted this from the total number of ways.

(b) $$5{15\choose 3} - 4{6\choose 3}$$

I'm also confused with my own work for this one. I originally assigned $$8$$ to an $$x_i$$ and got rid of this variable from consideration. Then I had $$12$$ remaining for $$n$$ and $$3$$ for $$m$$ so I had $${15\choose 3}$$ outcomes. Then I subtracted the case in which another variable received $$9$$ or more so I assigned $$9$$ to another variable. And then I had $$3$$ remaining for $$n$$ and $$3$$ for $$m$$, so I had $${6\choose 3}$$. Since there were $$4$$ candidates for the greater than $$8$$ votes I used $${4\choose 1}$$.

(c) I really need help with this part, I'm not even sure where to start...

• This is a great question! I'm stumped as well! – Parley Oct 10 '18 at 1:40

## 1 Answer

How many nonnegative integer solutions are there to the equation $$x_1 + x_2 + x_3 + x_4 + x_5 = 20$$ if $$x_i \leq 10$$ for $$1 \leq i \leq 5$$?

Without restrictions, the number of solutions of the equation $$x_1 + x_2 + x_3 + x_4 + x_5 = 20 \tag{1}$$ is $$\binom{20 + 5 - 1}{5 - 1} = \binom{24}{4}$$ as you found. The condition is violated if one of the five variables exceeds $$10$$. Note that at most one of the variables can exceed $$10$$ since $$2 \cdot 11 = 22 > 20$$.

Choose which of the five variables violates the condition. Since the equation is symmetric with respect to the variables, we may suppose it is $$x_1$$. Let $$x_1' = x_1 - 11$$. Then $$x_1'$$ is a nonnegative integer. Substituting $$x_1' + 11$$ for $$x_1$$ in equation 1 and simplifying yields $$x_1' + x_2 + x_3 + x_4 + x_5 = 9 \tag{2}$$ Equation 2 is an equation in the nonnegative integers with $$\binom{9 + 5 - 1}{5 - 1} = \binom{13}{4}$$ Hence, there are $$\binom{5}{1}\binom{13}{4}$$ solutions that violate the restrictions.

Hence, there are $$\binom{24}{4} - \binom{5}{1}\binom{13}{4}$$ admissible solutions, so your second attempt was right.

How many nonnegative integer solutions are there to the equation $$x_1 + x_2 + x_3 + x_4 + x_5 = 20$$ if $$x_i \leq 8$$ for $$1 \leq i \leq 5$$?

In this case, at most two of the variables could exceed the restrictions since $$2 \cdot 9 = 18 < 20 < 27 = 3 \cdot 9$$.

Choose which of the five variables exceeds the restriction. Since the equation is symmetric with respect to the variables, we may suppose it is $$x_1$$. Let $$x_1' = x_1 - 9$$. Then $$x_1'$$ is a nonnegative integer. Substituting $$x_1' + 9$$ for $$x_1$$ in equation 1 and simplifying yields $$x_1' + x_2 + x_3 + x_4 + x_5 = 11 \tag{3}$$ Equation 3 is an equation in the nonnegative integers with $$\binom{11 + 5 - 1}{5 - 1} = \binom{15}{4}$$ solutions. Hence, there are $$\binom{5}{1}\binom{15}{4}$$ cases in which one of the variables violates a restriction.

However, if we subtract this from the total, we will have subtracted too much since we have counted each case in which two of the variables violate a restriction twice, once for each way we could have designated one of the variables as the one that violates a restriction. Therefore, we need to add these cases back.

There are $$\binom{5}{2}$$ ways to select which two of the five variables violates a restriction. Since the equation is symmetric with respect to the variables, we may suppose they are $$x_1$$ and $$x_2$$. Let $$x_1' = x_1 - 9$$ and $$x_2' = x_2 - 9$$. Substituting $$x_1' + 9$$ for $$x_1$$ and $$x_2' + 9$$ for $$x_2$$ in equation 1 and simplifying yields $$x_1 + x_2 + x_3 + x_4 + x_5 = 2 \tag{4}$$ Equation 4 is an equation in the nonnegative integers with $$\binom{2 + 5 - 1}{5 - 1} = \binom{6}{4}$$ solutions. Thus, there are $$\binom{5}{2}\binom{6}{4}$$ cases in which two of the restrictions are violated.

By the Inclusion-Exclusion Principle, the number of admissible solutions is $$\binom{24}{4} - \binom{5}{1}\binom{15}{4} + \binom{5}{2}\binom{6}{4}$$

How many nonnegative integer solutions are there to the equation $$x_1 + x_2 + x_3 + x_4 + x_5 = 20$$ if $$x_i \leq 8$$ if $$x_1 = 2x_2$$?

Consider cases.

1. If $$x_1 = x_2 = 0$$, then $$x_3 + x_4 + x_5 = 20$$.
2. If $$x_1 = 2$$ and $$x_2 = 1$$, then $$x_3 + x_4 + x_5 = 17$$.
3. If $$x_1 = 4$$ and $$x_2 = 2$$, then $$x_3 + x_4 + x_5 = 14$$.
4. If $$x_1 = 6$$ and $$x_2 = 3$$, then $$x_3 + x_4 + x_5 = 11$$.
5. If $$x_1 = 8$$ and $$x_2 = 4$$, then $$x_3 + x_4 + x_5 = 8$$.
6. If $$x_1 = 10$$ and $$x_2 = 5$$, then $$x_3 + x_4 + x_5 = 5$$.
7. If $$x_1 = 12$$ and $$x_2 = 6$$, then $$x_3 + x_4 + x_5 = 2$$.