Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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+\ldots+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$.
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.
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}. $$
