How many tuples of {$a, b, c, \ldots$} satisfy $a+b+c+\ldots \leq n$?

Question

Let $n$ be a non-negative integer and $k$ be a positive integer.

Let $a, b, c, \ldots$ be $k$ non-negative integers such that $a+b+c+\ldots \leq n$.

How many tuples of {$a, b, c, \ldots$} satisfy the inequality?

Note that the tuples {$a=1, b=3$} and {$a=3, b=1$} are two different tuples.

For $k = 1$, the answer is $n+1$.

For $k = 2$, the answer is: $binomial(n+2,2) = \dfrac{(n+1)(n+2)}{2} = 1 + 2 + \ldots + n + n+1$

For any $k$, I conjecture that the answer is: $binomial(n+2,k) = \dfrac{(n+2)!}{k!(n+2-k)!}$

Answer 1

We wish to have $k$ numbers adding to at most $n$. This is equivalent to $k+1$ numbers adding to exactly $n$, since the difference between the sum of numbers and $n$ can be considered its own number.

Consider $k$ separators among $n$ objects. The number of objects before the first separator is the first number, the number between separators 1 and 2 are the second number, etc.

So we need to place $k$ separators in $n+k$ positions, and so there are ${n+k} \choose k$ ways to do so.

Answer 2

This is a well known problem - perhaps, you may want to have a look at Stars & Bars. In fact, the number of $k$-uples of non-negative integers $a_1,\ldots,a_k$ summing up to $n$ is $\binom{n+k-1}{n}.$ Then, to find out the numbers of $k$-uples of non-negative integers satisfying $a_1+\ldots+a_k\leqslant n,$ you can either use this binomial identity derived from the Hockey Stick Identity $$\sum\limits_{r=0}^n \binom{r+k-1}{r}=\binom{n+k}{n}$$ or the following more elementary method.

Let $d=n-(a_1+\ldots+a_k);$ notice that since $0\leqslant a_1+\ldots+a_k\leqslant n,$ we have that $0\leqslant d\leqslant n.$ In particular$,$ we see that $d$ is a non-negative integer, just like all the other variables $a_i.$ Thus$,$ we may solve instead the equation $$a_1+\ldots+a_k+d=n,$$ which by Stars & Bars has $\binom{n+k}{n}$ solutions, and this is also the number of solutions of $a_1+\ldots+a_k\leqslant n$ over the non-negative integers.