5
$\begingroup$

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?

  • 0
    @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.2011-10-01

2 Answers 2

1

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

1

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\}$.

  • 0
    Doh! Of course. But it ranges over the subsets of $[n]$. Thanks.2011-10-02