The number of $n$-tuples of nonnegative integers $(x_1,\ldots,x_n)$ satisfying the equation $x_1+\cdots+x_n = r$

For given positive integers $r,v,n$ let $S(r,v,n)$ denote the number of $n$-tuples of nonnegative integers $(x_1,\ldots,x_n)$ satisfying the equation $x_1+\cdots+x_n = r$ and such that $x_i \leq v$ for $i = 1,\ldots,n$. Prove that $$S(r,v,n) = \sum_{k=0}^m (-1)^k \binom{n}{k} \binom{r-(v+1)k+n-1}{n-1},$$ where $m = \min\left\{n,\left[\frac{r}{v+1}\right]\right\}$.

If $v \geq r$, then we see that the sum is just $\binom{n+r-1}{n-1}$, which is the number of nonnegative integer solutions to $x_1+\cdots+x_n = r$. If $v < r$, then how do we get the formula? How is $v+1$ involved?

We have from first principles that this value is

$$[z^r] (1+z+z^2+z^3+\cdots+z^v)^n = [z^r] \frac{(1-z^{v+1})^n}{(1-z)^n}.$$

This is

$$[z^r] \frac{1}{(1-z)^n} \sum_{k=0}^n {n\choose k} (-1)^k z^{(v+1)k} \\ = \sum_{k=0}^n {n\choose k} (-1)^k [z^{r-(v+1)k}] \frac{1}{(1-z)^n} \\ = \sum_{k=0}^n {n\choose k} (-1)^k {n-1+r-(v+1)k\choose n-1}.$$

The claim now follows.

We get for the upper limit that we must have $n-1+r-(v+1)k \ge n-1$ or $r/(v+1)\ge k.$ The first binomial coefficient adds an upper limit of $n$ so that we obtain

$$\min(n, \lfloor r/(v+1) \rfloor).$$

• Nice answer (+1) Jul 23, 2016 at 22:13
• Thanks ever so much. This answer is even nicer. Unfortunately not many people will see it since it has been put on hold. Jul 23, 2016 at 22:18
• @MarkusScheuer Never mind my previous comment, it really is a duplicate. Jul 23, 2016 at 22:42


This is inclusion exclusion. The $k = 0$ term corresponds to all non-negative solutions to the equation, the $k = 1$ term corresponds to all non-negative solutions where at least 1 of the $x_i$ is larger than $v$, the $k = 2$ term corresponds to all non-negative solutions where at least 2 of the $x_i$ are larger than $v$, and so on.