How many positive integer solutions of $$\sum_{i=1}^{k}x_i = N$$ for some positive integer $N$ given the constraints $n_i\leq x_i\leq m_i$ for $i=1,\ldots,k$, where $n_i$ and $m_i$ are positive integers.

I know that it can be calculated by finding the coefficient of $y^N$ in the polynomial $\prod_{i=1}^{K}(y^{n_i}+\cdots,y^{m_{i}})$. Is there any compact formula or any upper bound to the number of the positive integer solutions?

  • $\begingroup$ Note that by taking $X_i = x_i - n_i$, you can reduce this to the case where all $n_i=0$. There are obvious upper bounds, e.g. $\prod_{i=1}^{k-1} (m_i-n_i+1)$. $\endgroup$ Aug 27, 2018 at 0:06

1 Answer 1


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} } $$ if the upper index is non-negative and zero otherwise.

In the formula above, $\binom{.}{.}$ stands for the generalized binomial coefficients.

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 \Leftrightarrow x_i\geq m_i+1 $$

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

... and generally:

  • $N(q_{i_1}q_{i_2}... q_{i_s})$, the number of solutions (provided by Prop. 1) satisfying all properties $q_{i_1}$, $q_{i_2}$, ..., $q_{i_s}$,

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

$$ {\small N(q_2 q_3)=\binom{N+(k-2)-1-n_1-m_2-m_3-n_4-...-n_k}{k-1} \ \ \ or \ \ \ N(q_2 q_3)=0} $$ ... and generally: $$ {\small N(q_{i_1}q_{i_2}... q_{i_s})=\binom{N+(k-s)-1-\sum_{i\notin I} n_i-\sum_{i\in I} m_i}{k-1} \ \ \ or \ \ \ N(q_{i_1}q_{i_2}... q_{i_s})=0 } $$ where $s$ is the number of properties, $I=\{i_1, i_2, ..., i_s\}\subseteq \{1,2,...,k\}$ and the $N(..)$ function takes zero values whenever the upper index becomes negative.

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_{i=1}^{k} N(q_i)+\sum_{k\ \geq j > i\geq 1} N(q_i q_j)-...+ \\ +(-1)^s\sum_{k\ \geq i_s>...>i_1\geq 1} N(q_{i_1}q_{i_2}... q_{i_s})+.... +(-1)^k N(q_{1}q_{2}... q_{k}) $$

where in the above formula $s$ is the number of properties and $$ \sum_{k\ \geq j > i \geq 1}=\sum_{i=1}^{k-1}\sum_{j=i+1}^{k} $$ ... etc.

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}+\binom{k}{4}\binom{N-4\alpha-1}{k-1}-\cdots } $$ where $\binom{..}{..}$ stands for the generalized binomial coefficients and the summation halts when zero terms appear.

  • $\begingroup$ Thank you for your comment. Actually, I have to compare the cardinality of the solutions set of this problem with that of some other set. Is it possible to get a sharp upper bound to the cardinality of this set? $\endgroup$ Aug 27, 2018 at 12:57
  • $\begingroup$ i am not sure what do you need the upper bound for: following the method decribed in the answer you can get the exact number of solutions and not just an upper bound. $\endgroup$ Aug 27, 2018 at 13:14
  • $\begingroup$ But if you need an upper bound, you can for example compute (applying the formula of the example) the number of solutions of the problem satisfying the constraints $1\leq x_i\leq m$, where $m=\max \{ m_i \}$. This will obviously be an upper bound but i am not sure if it will be sharp enough for your purposes. $\endgroup$ Aug 27, 2018 at 13:34
  • $\begingroup$ $(m_1,m_2,m_3) = (6,3,3)$, $(n_1,n_2,n_3) = (8,4,4)$ and $N = 13$. Then how to compute $N(q_2)$ ? $\endgroup$ Sep 2, 2018 at 13:53
  • $\begingroup$ Apply the formula given above to get: $N(q_2)=\binom{13+(3-1)-1-6-4-3}{3-1}=\binom{1}{2}=0$ $\endgroup$ Sep 2, 2018 at 21:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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