# Number of combinations with repetitions (Constrained)

I would like to calculate the number of integral solutions to the equation

$$x_1 + x_2 + \cdots + x_n = k$$

where

$$a_1 \le x_1 \le b_1, a_2 \le x_2 \le b_2, a_3 \le x_3 \le b_3$$

and so on.

How do we approach problems with variables constrained on both sides $(a_1 \le x_1 \le b_1)$ or with constraints like $x_1 \le b_1$?

I know that the same equation with constraints like $x_1 \ge a_1, x_2 \ge a_2$ and so on can be solved using a slight modification of the formula $\binom{n + k - 1}{ k}$. Is it possible to tweak the same formula to suit the given problem?

-

## migrated from stackoverflow.comOct 1 '11 at 12:07

This question came from our site for professional and enthusiast programmers.

possible duplicate of No. of possible solutions of given equation – Jyrki Lahtonen Oct 1 '11 at 13:27
@Jyrki: this was asked at 10:46:52 and the other was asked at 12:00:10, so I voted to close that one. – robjohn Oct 1 '11 at 17:12
@robjohn: Ok, but for some reason I saw the other one first. Is the time stamp of the migration available somewhere? – Jyrki Lahtonen Oct 1 '11 at 17:47
@Jyrki: hover over the time in the "migrated from..." It says 12:07:20. So it was migrated after the other was asked here (by 7 minutes). So the "time asked" here is the pre-migration time asked. – robjohn Oct 1 '11 at 18:57

Let $A=\sum_{i=1}^n a_i$.

If there were no upper bounds on the $x_i$, the number of solutions would be $N(k-A,n)$, where

$$N(k,n)\;=\;\binom{k+n-1}{n-1}$$

is the number of weak $n$-compositions of $k$.

Now, if we exclude solutions in which some collection of the $a_i>b_i$, inclusion-exclusion gives us the following for the fully constrained situation:

$$\sum_{S\subseteq [n]}(-1)^{|S|}\; N\left(k-A-\sum\nolimits_{i\in S}1+(b_i-a_i),\;n \right)$$

where $[n]=\{1,\dots ,n\}$.

-
Am I correct in interpreting that $S$ ranges over all the $n!$ subsets of $[n]$? – robjohn Oct 1 '11 at 16:21
@robjohn: $S$ ranges over all the $2^n$ subsets of $[n]$. – David Bevan Oct 2 '11 at 13:22
Doh! Of course. But it ranges over the subsets of $[n]$. Thanks. – robjohn Oct 2 '11 at 13:31

$x^{b_i}+x^{b_i-1}+x^{b_i-2}+\dots+x^{a_i}=\frac{x^{b_i+1}-x^{a_i}}{x-1}$ is the generating function for the number of ways to roll a $k$ on a die with faces consisting of $a_i\dots b_i$ pips. The generating function for the number of ways to roll a $k$ as the the sum of $n$ such dice is the product of their generating functions.

Thus, the answer is the coefficient of $x^k$ in $$\prod_{i=1}^n\frac{x^{b_i+1}-x^{a_i}}{x-1}$$

-