Skip to main content
9 of 21
added 183 characters in body

Proposition 1: The number of integer solutions of the equation $$ \sum_{i=1}^{k}x_i = N $$ where $x_i\geq n_i$ for $i=1,\ldots,k$, is given by $$ {\small \binom{N+k-1-n_1-n_2-...-n_k}{k-1} } $$

Now, to tackle the problem as stated, you need to apply Proposition 1 and invoke the inclusion-exclusion principle, in the following sense:

For $i=1,...,k$, set as

$q_i$: the property of a solution of Proposition 1, to satisfy the condition $$ x_i> m_i $$

If we denote:

  • $N(q_i)$, the number of solutions (provided by Prop. 1) satisfying property $q_i$,
  • $N(q_i q_j)$, the number of solutions (provided by Prop. 1) satisfying both properties $q_i$, $q_j$,
  • .... etc

then we get -applying Prop. 1- that: $$ {\small N(q_1)=\binom{N-1-m_1-n_2-...-n_k}{k-1} } $$

$$ {\small N(q_2 q_3)=\binom{N-1-n_1-m_2-m_3-n_4-...-n_k}{k-1} } $$ ... etc

Now all you need to do to obtain a compact formula for the number of solutions satisfying your constraints, is to apply the inclusion-exclusion principle to determine the number of solutions produced by Proposition 1, which have none of the properties $q_i$ for $i=1,2,...,k$.
This is given by

$$ \binom{N+k-1-\sum n_i}{k-1}-\sum N(q_i)+\sum N(q_i q_j)-...+(-1)^s\sum N(q_{i_1}q_{i_2}... q_{i_s})+.... +(-1)^k N(q_{1}q_{2}... q_{k}) $$

Example: As an example of application of the previous method, consider the following special case of the OP:

Find the number of (positive) integer solutions of the equation $$\sum_{i=1}^{k}x_i = N$$ for some positive integer $N$, given the constraints $1\leq x_i\leq \alpha$ for $i=1,\ldots,k$

The method described above gives: $$ {\small \binom{N-1}{k-1}+\binom{k}{1}\binom{N-\alpha-1}{k-1}+\binom{k}{2}\binom{N-2\alpha-1}{k-1}+\binom{k}{3}\binom{N-3\alpha-1}{k-1}+\cdots } $$ where $\binom{..}{..}$ stands for the generalized binomial coefficients and the summation halts when zero terms appear.