5
$\begingroup$

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?

$\endgroup$
  • $\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$ – Robert Israel Aug 27 '18 at 0:06
5
$\begingroup$

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

$\endgroup$
  • $\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$ – Satya Prakash Aug 27 '18 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$ – Konstantinos Kanakoglou Aug 27 '18 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$ – Konstantinos Kanakoglou Aug 27 '18 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$ – Satya Prakash Sep 2 '18 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$ – Konstantinos Kanakoglou Sep 2 '18 at 21:21

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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