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?
 A: 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.
A: 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$...
A: 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.
A: 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.
