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?
 A: 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).$$
A: $\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}}
 \newcommand{\ol}[1]{\overline{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
\begin{align}
&\color{#f00}{\sum_{x_{1}\ =\ 0}^{\nu}\cdots\sum_{x_{n}\ =\ 0}^{\nu}\,\,
\delta_{\ds{x_{1} + \cdots + x_{n},r}}} =
\sum_{x_{1}\ =\ 0}^{\nu}\cdots\sum_{x_{n}\ =\ 0}^{\nu}
\,\,\oint_{\verts{z}\ =\ 1^{-}}\,\,\,
{1 \over z^{r\ +\ 1\ -\ x_{1}\ -\ \cdots\ -\ x_{n}}}
\,\,\,\,\,{\dd z \over 2\pi\ic}
\\[4mm] = &\
\oint_{\verts{z} = 1^{-}}\,\,{1 \over z^{r + 1}}\,\,\,
\pars{\sum_{x\ =\ 0}^{\nu}z^{x}}^{n}\,{\dd z \over 2\pi\ic} =
\oint_{\verts{z} = 1^{-}}\,\,{1 \over z^{r + 1}}\,\,\,
\pars{z^{\nu + 1} - 1 \over z - 1}^{n}\,{\dd z \over 2\pi\ic}
\\[4mm] = &\
\oint_{\verts{z} = 1^{-}}\,\,\,{1 \over z^{r + 1}}\,\,\,
\sum_{\ell = 0}^{n}{n \choose \ell}\pars{-x^{\nu + 1}}^{\ell}
\sum_{\ell' = n}^{\infty}{n \choose \ell'}\pars{-z}^{\ell'}\,{\dd z \over 2\pi\ic}
\\[4mm] = &\
\sum_{\ell = 0}^{n}{n \choose \ell}\pars{-1}^{\ell}
\sum_{\ell' = 0}^{\infty}{n \choose \ell'}\pars{-1}^{\ell'}
\oint_{\verts{z} = 1^{-}}\,\,\,
{1 \over z^{r - \nu\ell -\ell -\ell '+ 1}}\,\,\,
\,{\dd z \over 2\pi\ic}
\\[4mm] = &\
\sum_{\ell = 0}^{n}{n \choose \ell}\pars{-1}^{\ell}\,\,\sum_{\ell' = 0}^{\infty}
\pars{-1}^{\ell'}{n \choose \ell'}\delta_{r - \nu\ell - \ell - \ell' + 1,1}
\\[4mm] = &\
\left.\sum_{\ell = 0}^{n}{n \choose \ell}\pars{-1}^{\ell}
\pars{-1}^{r - \nu\ell -\ell}\,\,{n \choose r - \nu\ell - \ell}
\,\right\vert_{\ r\ -\ \nu\ell\ -\ \ell\ \geq\ 0}
\\[4mm] = &\
\color{#f00}{\pars{-1}^{r}\sum_{\ell = 0}^{m}\pars{-1}^{\nu\ell}\,\,
{n \choose \ell}{n \choose r - \nu\ell - \ell}}\quad
\mbox{where}\quad \color{#f00}{m} \equiv
\color{#f00}{\min\braces{n,\left\lfloor{r \over \nu + 1}\right\rfloor}}
\end{align}
A: 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.
