2
$\begingroup$

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?

$\endgroup$

3 Answers 3

2
$\begingroup$

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).$$

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

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.