Number of possible combinations that satisfy the constraints

Question

Let $x_{1}, x_{2}, x_{3} \in \mathbb{Z}^{++}$ (i.e., strictly positive integers).

Suppose the following (in)equalities are given: \begin{align} x_{1} &\geq x^{\min}_{1} \tag1\\ x_{2} &\geq x^{\min}_{2} \tag2\\ x_{3} &\geq x^{\min}_{3} \tag3\\ x_{1}+x_{2}+x_{3} &= N \tag4 \end{align}

where $x^{\min}_{1},x^{\min}_{2},x^{\min}_{3},N \in \mathbb{Z}^{++}$ are known and are such that at least one tuple of feasible $ \{ x_{1}, x_{2}, x_{3} \}$ can be found that satisfies [1-4].

My question is, how many possible $ \{ x_{1}, x_{2}, x_{3} \}$ can satisfy [1-4], as a function of $x^{\min}_{1},x^{\min}_{2},x^{\min}_{3},N$?

For context: I have an integer programming problem with the constraints given above. I want to quantify the number of trials to solve this problem by complete enumeration.

My attempt:

• We can discard one variable using [4] (e.g, $x_{3}= N - x_{1} - x_{2}$).

• Then using [3], $N - x_{1} - x_{2} \geq x^{\min}_{3} \Rightarrow N-x^{\min}_{3} \geq x_{1} + x_{2}$.

• Then using [1] and [2], $N-x^{\min}_{3} \geq x_{1} + x_{2} \geq x^{\min}_{1}+x^{\min}_{2}$

Then fixing $x_{1} = x^{\min}_{1}$, $x_{2}$ can take the integer values between $x^{\min}_{2}$ and $N-x^{\min}_{3}-x^{\min}_{1}$. Therefore, $N-x^{\min}_{3}-x^{\min}_{2}-x^{\min}_{1}+1$ many values. How to proceed after this?

Answer 1

You're on the right track, but we can simplify things a bit. I can't bring myself to use the superscript "max" for a lower bound, so I'll use $\underline{x}_i$ for the lower bound of $x_i$.

Let $\hat{x}_i = x_i - \underline{x}_i \ge 0$ and $\hat{N} = N - \underline{x}_1 - \underline{x}_2 - \underline{x}_3,$ and note that the number of nonnegative solutions to $\hat{x}_1 + \hat{x}_2 + \hat{x}_3 = \hat{N}$ is the same as the number of solutions to the original problem. Next, note that for a given nonnegative integer value $K$, the number of nonnegative integer solutions to $\hat{x}_2 + \hat{x}_3 = K$ is $K + 1$. So we can just substitute $\hat{N} - \hat{x}_1$ for $K$ to get the number of solutions having a particular value of $\hat{x}_1$ and sum the results:$$ (\hat{N} + 1) + \hat{N} + (\hat{N} - 1) + \dots + 1 + 0 = \frac{(\hat{N} + 1)(\hat{N} + 2)}{2}.$$

Answer 2

More generally, the number of integer solutions to $$\sum_{i=1}^k x_i = n$$ with $x_i \ge \ell_i$, where $k$, $n$, and $\ell_i \ge 0$ are fixed, is the same as the number of nonnegative integer solutions to $$\sum_{i=1}^k x_i = n - \sum_{i=1}^k \ell_i,$$ which (by "stars and bars") is $$\binom{n - \sum_{i=1}^k \ell_i+k-1}{k-1}.$$ Your case with $k=3$ reduces to @prubin's answer.