How many solutions exist for this equation?

64 Views Asked by At

How many integer solutions exist for $N,n,L_1,\ldots,L_n,$ $U_1,\ldots,U_n,x_1,\ldots,x_n\in\mathbb N$ $$\sum_{i=1}^nx_i=N$$ and $$ \forall i: L_i\le x_i\le U_i $$

?


A simpler version, without the $U_i$ parameters (or if $U_i\ge N$) is to use the stars and bars formula, which says that if $L=\sum_{i=1}^nL_i$ then there are $N+n-L-1\choose n-1$ solutions.

What about the general version? (I'm interested in a closed-form solution if possible).

Thanks :).

1

There are 1 best solutions below

4
On

For the general version. You should use the inclusion-exclusion principle.

Let $A$ be the collection of all nonnegative integer solutions to the formula and $A_i$ be the collection of all nonnegative integer solutions where $x_i>U_i$.

For each $I\subseteq\{1,2,\ldots,n\}$, we denote $$A_I=\begin{cases} \bigcap_{i\in I}{A_i}, & I\neq\emptyset; \\ A, & I=\emptyset.\end{cases}$$ Then $$|A_\emptyset|=|A|=\binom{N-L+n-1}{n-1},$$ where $L=\sum_{i=1}^n{L_i}$.

Otherwise, for each $i\in I$, we have $x_i>U_i$. We then set $U_I=\sum_{i\in I}{(U_i+1)}$ and $L_I=\sum_{i\notin I}{L_i}$. Applying the same counting scheme, we have $$|A_I|=\binom{N-U_I-L_I+n-1}{n-1}.$$ In particular, if $N<U_I+L_I$, then $|A_I|=0$.

Finally, the number of integer solutions with $L_i\leq x_i\leq U_i$ is $$\sum_{I\subseteq\{1,\ldots,n\}}{(-1)^{|I|}|A_I|}=|A_\emptyset|-\sum_{i=1}^{n}{|A_i|}+\sum_{i<j}{|A_i\cap A_j|}-\cdots.$$