On the nonnegative integer solutions that satisfy $\sum x_i \leq n$

Question

We have the following nice problem: Search for all vectors $(x_1,\ldots,x_r)$ with $x_i > 0$ that satisfy

$$ x_1+x_2+x_3+\cdots+x_r \leq n $$

$\textbf{discussion}$

One approach I have in mind is as follows: First, consider solutions to $\sum^r x_i = n$ and we know there are ${n-1 \choose r-1}$ such solutions by stars and bars argument. but, before we continue, for this argument to work we must have $n \geq r$. Now, we count how many vectors satisfy $\sum x_i = n-1$ and we know again there are ${n-2 \choose r-1}$ such vectors. If we keep this process down to $r$, that is, if we try to find solutions to $\sum x_i = r $, then we obtain just one $(1,1,1,\ldots,1)$ or ${r-1 \choose r-1}$. Therefore, in total we have

$$ {n-1 \choose r-1 } + {n-2 \choose r-1} + {n-3 \choose r-1} + \cdots + {r-1 \choose r-1} $$

such vectors. Is there a way to simplify this expression? Is there any other approach to tackle this problem?

Answer 1

Suppose that you want to count the subsets of $[n]=\{1,\ldots,n\}$ of size $r$. One way to count them is to divide them up according to the largest number in the subset. If $k$ is the largest number in the subset, there are $\binom{k-1}{r-1}$ ways to choose the $r-1$ smaller numbers in the subset, so there are $\binom{k-1}{r-1}$ subsets of $[n]$ of size $r$ whose largest element is $k$. The possible choices for $k$ range from $r$ through $n$, so $[n]$ has

$$\sum_{k=r}^n\binom{k-1}{r-1}$$

subsets of size $r$. Of course we know that it has $\binom{n}r$ subsets of size $r$, so

$$\sum_{k=r}^n\binom{k-1}{r-1}=\binom{n}r\,;$$

that’s your closed form. This is the hockey stick identity; it comes up a lot and is worth knowing.

Answer 2

I think you have a good idea in stars and bars, but a couple of modifications make it simpler. Add another bin for overflow, so that we when we distribute $n$ objects into the bins, there will be at most $n$ in the first $r$ bins. Also, since we want each of the first $r$ bins to have at least one object, put an object into each of the first $r$ bins to start with, then distribute the remaining $n-r$ objects into $r+1$ bins. Stars and bars gives the answer $$\binom nr$$

Answer 3

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \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{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#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}$ By definition, the answer is given by \begin{align} &\bbox[10px,#ffd]{\sum_{s = r}^{n}\braces{% \sum_{x_{1} = 1}^{\infty}\ldots\sum_{x_{r} = 1}^{\infty} \bracks{x_{1} + \cdots + x_{r} = s}}} \\[5mm] = &\ \sum_{s = 0}^{n - r}\sum_{x_{1} = 0}^{\infty}\ldots\sum_{x_{r} = 0}^{\infty} \bracks{z^{s}}z^{x_{1} + \cdots + x_{r}} = \sum_{s = 0}^{n - r}\bracks{z^{s}}\pars{\sum_{x = 0}^{\infty}z^{x}}^{r} = \sum_{s = 0}^{n - r}\bracks{z^{s}}\pars{1 \over 1 - z}^{r} \\[5mm] = &\ \bracks{z^{0}}\pars{1 - z}^{-r}\sum_{s = 0}^{n - r} \pars{1 \over z}^{s} = \bracks{z^{0}}\pars{1 - z}^{-r}\,{\pars{1/z}^{n - r + 1} - 1 \over 1/z - 1} \\[5mm] = &\ \bracks{z^{0}}\pars{1 - z}^{-r - 1}\pars{z^{r - n} - z} = \bracks{z^{n - r}}\pars{1 - z}^{-r - 1} = {-r - 1 \choose n - r}\pars{-1}^{n - r} \\[5mm] = &\ {n \choose n - r} = \bbox[10px,#ffd,border:1px groove navy]{n \choose r} \\ & \end{align}