8
$\begingroup$

The problem of counting the solutions $(a_1,a_2,\ldots,a_n)$ with integer $a_i\geq0$ for $i\in\{1,2,\ldots,n\}$ such that $$a_1+a_2+a_3+....a_n=N$$ can be solved with a stars-and-bars argument. What is the solution if one adds the constraint that $a_i\leq r_i$ for certain integers $r_1,\ldots,r_n$?

e.g. for $n=3$, $N=6$ and $(r_1,r_2,r_3)=(3,3,2)$, the tuple $(a_1,a_2,a_3)=(2,3,1)$ is a solution, but $(2,1,3)$ is not a solution because $a_3=3>2=r_3$.

$\endgroup$
  • $\begingroup$ If you limit each $a_i\leq1$, then you don't need stars and bars in the first place, as it just becomes counting combinations of $N$ (nonzero $a_i$) chosen from a set of$~r$. However if your imposed limit is larger than$~1$, then the problem is not quite as easy. I suggest that you choose a more representative example in the question. $\endgroup$ – Marc van Leeuwen Nov 6 '13 at 6:17
13
$\begingroup$

There is as far as I know no closed formula for this general problem, but there is a formula that allows the number of solutions to be computed in a number of operations independent of $N$. Consider first the case that all limits are equal $r_1=r_2=\cdots=r_n=r$. Then the number is the coefficient of $X^N$ in the polynomial $(1+X+\cdots+X^r)^n$. By writing this as a rational function of$~X$ $$ (1+X+\cdots+X^r)^n=\left(\frac{1-X^{r+1}}{1-X}\right)^n=\frac{(1-X^{r+1})^n}{(1-X)^n} $$ the coeffiecient of $X^k$ in the numerator is zero unless $k$ is a multiple $q(r+1)$ of $r+1$, in which case it is $(-1)^q\binom nq$, and the coefficient of $X^l$ in the inverse of the denominator is $(-1)^l\binom{-n}l=\binom{l+n-1}l$, which is zero unless $l\geq0$ and otherwise equal to $\binom{l+n-1}{n-1}$. It remains to sum over all $k+l=N$, which gives $$ \sum_{q=0}^{\min(n,N/(r+1))}(-1)^q\binom nq\binom{N-q(r+1)+n-1}{n-1}, $$ where the summation is truncated to ensure that $N-q(r+1)\geq0$ (the condition $l\geq0$). Although the summation looks complicated, it has at most $n+1$ easily computed terms, for any$~N$. Just to illustrate, the coefficient for $n=5$, $r=100$ and $N=243$ is easily computed to be $62018665$. An interesting point to remark is that if the summation had not been truncated, then the result would clearly have been a polynomial function of$~N$ of degree${}<n$ (because binomial coefficients $\binom xk$ are polynomial functions of$~x$ of degree$~k$). But on one hand that polynomial function gives the exact values of this problem for $N\geq n(r+1)$ where no truncation takes place, while on the other hand, given the original problem, those values are all$~0$; so the polynomial function will be identically zero! So an alternative formula for the result is to compute the negative of the truncated terms, which formula becomes after some massaging $$ \sum_{q=\lceil\frac{N+n}{r+1}\rceil}^n (-1)^{n-q}\binom nq\binom{q(r+1)-1-N}{n-1}, $$ which is easier to use for large$~N$. For instance in the above example this formula gives a single term $\binom{78}4=1426425$ for $N=426$; it is the same value as obtained for $N=74=500-426$ (from the first formula) which can be understood by the fact that the "remainders" $r_i-a_i$ add up to $nr-N$.

In the general case of distinct limits $r_i$, the approach is the same, but the formula becomes a bit messy. Instead of a numerator $(1-X^{r+1})^n$ one gets a product $P=(1-X^{r_1+1})\ldots(1-X^{r_n+1})$ which in general has more nonzero terms (the number of terms can be up to $\min(\Sigma r_i+n+1,2^n)$), but which can be computed once and for all. With $P=\sum_ic_iX^{e_i}$, the formula for the result becomes $$ \sum_ic_i\binom{N-e_i+n-1}{n-1}, $$ which still is a sum of a number of terms independent of$~N$. But of course computing the polynomial $\frac P{(1-X)^n}$ beforehand, and then for any $N$ just looking up the coefficient of $X^N$, is another essentially constant-time (in $N$) solution.

$\endgroup$
  • $\begingroup$ I posted a question a couple of days ago which appears to be essentially the same question as this one - at least I think it is. If they are the same problem, is the upshot of your post that the most effective way to calculate the numbers in the general case is to check the coefficients of the polynomial? I'm having a little trouble understanding what number the last formula in your post calculates. $\endgroup$ – Geoffrey Nov 7 '13 at 5:57
  • 1
    $\begingroup$ The last formula just computes the coefficient of $X^N$ in $(\sum_ic_iX^{e_i})(1-X)^{-n}$. It is interesting as a computational method only if the left factor $P$ (which was computed as a product of sparse polynomials) is still sparse. If it is dense, better compute the product polynomial right away, to get the answer for all $N$ at once. $\endgroup$ – Marc van Leeuwen Nov 7 '13 at 6:13
  • $\begingroup$ Nice answer. An alternative method for the case where all $r_i = r$ is to use inclusion exclusion. Also, a perhaps clearer way to arrive at the "remainder" formula is to just make the change of variables $a_i = r_i - b_i$. Then you simply need to count the number of solutions to $b_1 + \ldots + b_n = \left( \sum r_i \right) - N$ where each $b_i \leq r_i$. $\endgroup$ – Andrew Szymczak Feb 22 '15 at 1:31
3
$\begingroup$

For future reference, to people who are unfamiliar with generating functions, here is a solution using the principle of inclusion exclusion.


Ignoring the constraint $a_i\le r_i$, the number of solutions is $\binom{N+n-1}{n-1}$, by stars and bars. To incorporate these constraints, we subtract the "bad" solutions where some $a_i>r_i$. To count solutions where $a_1>r_1$, we instead count solutions to the equation $$ (a_1-r_1-1)+a_2+a_3+\dots+a_n=N-r_1-1 $$ Now, all summands on the left hand side are nonnegative integers, so the number of solutions is $\binom{N-r_1-1+n-1}{n-1}$. Therefore we subtract $\binom{N-r_i-1+n-1}{n-1}$ for each $i=1,2,\dots,n$.

However, solutions with two variable which were too large have now been subtracted twice, so these must be added back in. Solutions where $a_i>r_i$ and $a_j>r_j$ can be counted by subtracting $r_i+1$ from $a_i$ and $r_j+1$ from $a_j$, leaving a list of integers summing to $N-(r_i+1)-(r_j+1)$, the number of which is $\binom{N-(r_i+1)-(r_j+1)+n-1}{n-1}$.

We must then correct for the solutions with three variables which are too large, then four, and so on. This can be handled systematically using the principle of inclusion exclusion. The result is $$ \sum_{S\subseteq \{1,2,\dots,n\}}(-1)^{|S|}\binom{N+n-1-\sum_{i\in S}(r_i+1)}{n-1} $$ Here, we define $\binom{m}k=0$ whenever $m<0$.


For the special case $r_1=r_2=\dots=r_n=r$ where the upper limit is the same for each variable, the result is $$ \sum_{k=0}^{\lfloor N/(r+1) \rfloor}(-1)^k\binom{n}k\binom{N-k(r+1)+n-1}{n-1}. $$

$\endgroup$
  • $\begingroup$ Have not you forgot $(-1)^k $ in the last expression? $\endgroup$ – user Apr 14 at 23:34
  • $\begingroup$ @user Thanks for the heads up! $\endgroup$ – Mike Earnest Apr 14 at 23:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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