# Simple combinatorics problem.

How can I compute the number of lists of the form $(a_1,\ldots,a_k)$, where $a_i \geq 0$ are integers and $\sum a_i \leq n$? What is the easiest way to derive the answer?

-
Well, I assume this is a simple problem for anyone who is good at combinatorics, since it looks very standard. This came up as a small side note for a research problem. – dst Jan 11 '14 at 18:42
Another comment: I expected this to be standard enough that there is a direct well-known formula for it. That is all I really need, but I didn't find it in the texts I have. – dst Jan 11 '14 at 18:45

imagine that there are $n$ points and $k-1$ walls. Any permutation of walls and points give you $(a_1, ..., a_k)$ that corresponds to number n and vice versa. So your answer is $\sum_{i=0}^n {{i+k-1}\choose{i}}$

-
Ah, it was this... Yes, my combinatorics is rusty. – dst Jan 11 '14 at 18:52
(Of course summing over the n...) – dst Jan 11 '14 at 18:54
Yes, thanks. Corrected – user68061 Jan 11 '14 at 18:57

I have an easier way to derive the answer:

The number of lists of the form $a_1+a_2+\dots+a_k\leq n$ and $a_1+a_2+\dots+a_k+b= n$, where b is a nonnegative integer are equivalent. Because the latter involves the cases where $b\,\in \{ 0,1,2,\dots,n \}$

Thus we have $n$ points and $k$ walls, which give us the answer $\Large\binom{n+k}{n}$

-

As we know that number of solution to equation $a_1 + a_2 + \cdots + a_r = n$ such that $a_i \ge 0$ is $${n+r-1 \choose r-1}$$ Now, Consider the equation $a_1 + a_2 + \cdots + a_k + a_{k+1} = n$, number of solution to this equation such that $a_i \ge 0$ is given by, $${n+k \choose k}$$ If we leave $a_{k+1}$ as slack variable, we have number of solution to $\sum_i a_i \le n$ as $${n+k \choose k}$$ which is the required answer.

-