# Number of integer solutions of a linear equation under constraints

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?

• 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)$. – Robert Israel Aug 27 '18 at 0:06

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.

• 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? – Satya Prakash Aug 27 '18 at 12:57
• 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. – Konstantinos Kanakoglou Aug 27 '18 at 13:14
• 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. – Konstantinos Kanakoglou Aug 27 '18 at 13:34
• $(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)$ ? – Satya Prakash Sep 2 '18 at 13:53
• Apply the formula given above to get: $N(q_2)=\binom{13+(3-1)-1-6-4-3}{3-1}=\binom{1}{2}=0$ – Konstantinos Kanakoglou Sep 2 '18 at 21:21