# Combinatorics for integer solutions

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?

-

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.

-

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.

-

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$...

-

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.

-