TITLE: How to compute the number of n-element combinations of non-negative integers with a given sum?
QUESTION [2 upvotes]: The title has the general form of the problem, but I'd also welcome insight into the following specific case: how many sets of five non-negative integers exist having a sum of 20?
I've tried breaking it down recursively, starting from the case of "How many collections of one non-negative integers summing to 20?" Only one such collection exists, containing only the number 20. I then find the number of 2 integer collections (11). But it quickly gets out of hand--I'm not certain how to go about finding the number of 3 integer collections.
Help would be greatly appreciated.
EDIT: The order of the numbers does not matter, and numbers may repeat. So {20,0,0,0,0} is a solution, and {0,20,0,0,0} is the same solution.

REPLY [0 votes]: Hint: Let $P(n,k)$ be the number of partitions of $n$ into $k$ parts, all $\ge 1$. Then (with $n=20$, $k=5$) you want $P(25,5)$. For there is in general a natural bijection between the divisions of $n$ into $k$ parts, some of which may be $0$, and the number of partitions of $n+k$ into $k$ parts, all $\ge 0$.
You can prove the following recurrence for $P(n,k)$:
$$P(n,k)=P(n-1,k-1)+P(n-k,k).$$
There is no pleasant closed form for $P(n,k)$.
{"set_name": "stack_exchange", "score": 2, "question_id": 688671}