Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How many integer solutions are there to the following equation?

$x_1 + x_2 + x_3 = 17$

a) if $x_1 > 1, x_2 > 2, x_3 > 3$

b) if $x_1 < 6, x_3 > 5$ and $x_2$ can be any integer.

c) if $x_1 < 4, x_2 < 3, x_3 < 5$

What is a systematic way to approach and solve these types of problems?

share|improve this question

4 Answers 4

up vote 1 down vote accepted

For (a), substitute $x_1 = 2 + a$, $x_2 = 3 + b$, $x_3 = 4+c$, where $a,b,c \ge 0$. This resolves to

$$a + b + c = 8$$

which we can easily find solutions to: place 8 $0$'s in a string. Introduce two $1$'s to partition this string into three partitions. The number of $0$'s in each partition corresponds to the value of $a,b,c$ respectively. There are $\binom{10}{2}$ ways of permuting these 8 $0$'s and two $1$'s. Hence, there are $\binom{10}{2}$ non-negative integer solutions.

You can easily generalize this to show that there are $\binom{n+k-1}{k-1}$ non-negative integer solutions to the equation

$$x_1 + x_2 + \cdots + x_k = n$$

For (b), assuming $x_1$ can be negative, we see that there are infinitely many solutions, because any of the infinitely many valid pairs of $x_1, x_2$ will generate a valid integer $x_3$. To be more explicit, let $x_3 = 17 - x_1 - x_2$. Then both sides will always be equal.

For (c), this appears to be a trick question! There are no solutions, because $$x_1 + x_2 + x_3 < 4 + 3 + 5 < 17$$

Equality will never be reached.

share|improve this answer

One of the approaches is to use generating functions. E.g. generating function for first example if you can choose from any non-negative integer is $(\sum_{i=0}^{\infty} x_i)^3 = (\frac {1} {1 - x})^3$. You are interested in coefficient of $x^{17}$ which in this case is $19 \choose 17 $. For problems with constrains it is equally simple. "Applied Combinatorics" by Wiley has chapter devoted to this topic.

share|improve this answer

Use generating functions. I.e., the value of $x_1$ is represented by $z^2 + z^3 + \cdots = z^2 (1 - z)^{-1}$, and similarly the others. For all three variables it is in case (a): $$ [z^{17}] z^2 \cdot z^3 \cdot z^4 \cdot (1 - z)^{-3} = (-1)^{17} \binom{-3}{17} = [z^8] (1 - z)^{-3} = \binom{8 + 3 - 1}{3 - 1} = 45 $$

Case (b) gives $1 + \cdots + z^5 = (1 - z^6) / (1 - z)$ for $x_1$, $z^6 + z^7 + \cdots = z^6 (1 - z)^{-1}$ for $x_2$ and $(1 - z)^{-1}$ for $x_3$ (if we restrict $0 \le x_i$, that is; otherwise there are infinite solutions). Similar to before: $$ [z^{17}] z^6 \cdot (1 - z^6) \cdot (1 - z)^{-2} = [z^{11}] (1 - z^6) \sum_{r \ge 0} (-1)^r \binom{-2}{r} z^r = [z^{11}] (1 - z^6) \sum_{r \ge 0} \binom{r + 1}{1} z^r = \binom{11 + 1}{1} - \binom{6 + 1}{1} = 5 $$

Case (c) is the most interesting one. As before: \begin{align} [z^{17}] \frac{1 - z^4}{1 - z} \cdot &\frac{1 - z^3}{1 - z} \cdot \frac{1 - z^5}{1 - z} = (1 - z^3 - z^4 - z^5 + z^7 + z^8 + z^9 - z^{12}) \cdot \sum_{r \ge 0} (-1)^r \binom{-3}{r} z^r \\ &= (1 - z^3 - z^4 - z^5 + z^7 + z^8 + z^9 - z^{12}) \cdot \sum_{r \ge 0} \binom{r + 2}{2} z^r \\ &= \binom{19}{2} - \binom{16}{2} - \binom{15}{2} - \binom{14}{2} + \binom{12}{2} + \binom{11}{2} + \binom{10}{2} - \binom{7}{2} \end{align} The result is obviously 0, as $3 + 2 + 4 < 17$...

share|improve this answer

Under the condition $y_{i}\in\mathbb{Z}_{\geq0}$ there are $\binom{n+k-1}{k-1}$ solutions for $y_{1}+\cdots+y_{k}=n$.

This can be deduced on the way that Yiyuan is pointing out.

Condition a) can be interpreted as finding the number of solutions of $y_{1}+y_{2}+y_{3}=8$ under $y_{i}\in\mathbb{Z}_{\geq0}$ where $y_{1}=x_{1}-2$, $y_{2}=x_{2}-3$ and $y_{3}=x_{3}-4$ . So there are $\binom{10}{2}$ solutions.

See Yiyuan for an answer on the other cases.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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