Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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 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 at 18:45

3 Answers 3

up vote 1 down vote accepted

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

share|improve this answer
    
Ah, it was this... Yes, my combinatorics is rusty. –  dst Jan 11 at 18:52
1  
(Of course summing over the n...) –  dst Jan 11 at 18:54
    
Yes, thanks. Corrected –  user68061 Jan 11 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}$

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.